数据结构与算法之美
王争
前Google工程师
立即订阅
71328 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

春节7天练 | Day 4:散列表和字符串

王争 2019-02-08
你好,我是王争。初四好!
为了帮你巩固所学,真正掌握数据结构和算法,我整理了数据结构和算法中,必知必会的 30 个代码实现,分 7 天发布出来,供你复习巩固所用。今天是第四篇。
和昨天一样,你可以花一点时间,来完成测验。测验完成后,你可以根据结果,回到相应章节,有针对性地进行复习。
前几天的内容。如果你错过了,点击文末的“上一篇”,即可进入测试。

关于散列表和字符串的 4 个必知必会的代码实现

散列表

实现一个基于链表法解决冲突问题的散列表
实现一个 LRU 缓存淘汰算法

字符串

实现一个字符集,只包含 a~z 这 26 个英文字母的 Trie 树
实现朴素的字符串匹配算法

对应的 LeetCode 练习题(@Smallfly 整理)

字符串

Reverse String (反转字符串)
Reverse Words in a String(翻转字符串里的单词)
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(19)

  • 李皮皮皮皮皮
    散列表的核心是散列函数和冲突解决算法,以及装载因子过大时如何扩容。散列函数的设计较为复杂,一般使用现有的函数,如murmur散列。冲突解决一般有开放寻址法和链表法。查看开源项目的源码实现很有意思,例如lua的table实现,是结合了两个方法的非常优雅的实现。根据装载因子扩容一般保持在2,在占用空间较大时慢慢缩减为1.5,1.25……如golang的实现。为了避免rehash时的延迟,可以使用先分配,后逐步散列的方法,redis就是使用这个方法的。
    字符串是编程中一定会出现的问题,变种非常多,反转,反转单词,字串,最长字串,最长子序列等等,有时解决问题需要多种数据结构与算法的结合。
    2019-02-08
    3
  • kai
    实现一个 LRU 缓存淘汰算法:

    import java.util.HashMap;
    import java.util.Iterator;

    public class LRU<K,V> {
        
        private Node head;
        private Node tail;
        private HashMap<K, Node> map;
        private int maxSize;

        private class Node {
            Node pre;
            Node next;
            K k;
            V v;
            public Node(K k, V v) {
                this.k = k;
                this.v = v;
            }
        }

        public LRU(int maxSize) {
            this.maxSize = maxSize;
            this.map = new HashMap<>(maxSize * 4 / 3);
            head = new Node(null, null);
            tail = new Node(null, null);
            head.next = tail;
            tail.pre = head;
        }

        public V get(K key) {
            if (!map.containsKey(key)) {
                return null;
            }
            Node node = map.get(key);
            unlink(node);
            appendToHead(node);
            return node.v;
        }
        public void put(K key, V value) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                unlink(node);
            }
            Node node = new Node(key, value);
            appendToHead(node);
            map.put(key, node);
            if (map.size() > maxSize) {
                Node toRemove = removeTail();
                map.remove(toRemove.k);
            }
        }
        private Node removeTail() {
            Node node = tail.pre;
            Node pre = node.pre;
            tail.pre = pre;
            pre.next = tail;
            node.next = null;
            node.pre = null;
            return node;
        }
        private void appendToHead(Node node) {
            Node next = head.next;
            node.next = next;
            node.pre = head;
    next.pre = node;
            head.next = node;
        }
        private void unlink(Node node) {
            Node pre = node.pre;
            Node next = node.next;
            pre.next = next;
            next.pre = pre;
            node.pre = null;
            node.next = null;
        }
        
    }
    2019-02-11
    2
  • hopeful
    #朴素字符串匹配算法
    def nmatching(t, p):
    # t代表主串,p代表模式串
        i = 0
        j = 0
        n = len(t)
        m = len(p)
        while i < n and j < m:
            if t[i] == p[j]:
                i = i+1
                j = j+1
            else:
                i = i-j+1
                j = 0 #i-j+1是关键,遇字符不等时将模式串t右移一个字符
        if j == m:
            return i-j #找到一个匹配,返回索引值
        return -1 #未找到,返回-1
    2019-03-11
    1
  • 黄丹
    王争老师,新年的第四天快乐,已经很晚了,祝您好梦!
    关于基于链表法解决冲突的散列表,就是使用一个数组,将值散列到数组下标上,但数组的每个值又是一个链表的头结点,当遇到冲突时就遍历该头结点后链表。其实java中hashmap底层的实现原理就是一个基于链表解决冲突的动态扩容的数组。大家有兴趣可以自己实现一下hashmap的底层数据结构,还是很有收获的。
    今天leetcode上的三题都是关于字符串的,下面是我的解题思路和代码
    1. Reverse String (反转字符串)
    解题思路:这一题要求使用O(1)的空间将字符串进行反转,就是原地反转字符串,对字符串s[0…n-1]来说当i<n/2;将i与n-1-i位置的字符进行互换就行.
    代码: https://github.com/yyxd/leetcode/blob/master/src/leetcode/strings/Problem344_ReverseString.java
    2. Reverse Words in a String (翻转字符串里的单词)
    解题思路:这一题我用的是java中的StringBuilder处理字符串,先用split函数将字符串按空格分开,但是当有多个连续空格时,一定要注意这种不能当做单词处理,要检查一下。
    代码: https://github.com/yyxd/leetcode/blob/master/src/leetcode/strings/Problem151_ReverseWordsInString.java
    3. String to Integer (atoi) 字符串转换整数 (atoi))
    解题思路:将字符串转化为整数,首先是对数字前面的+/-进行处理,遍历字符串,如果不是数字字符就break,自己不懂得地方在于如何将大于INT.MAX 的值转化为 INT.MAX,将INT.MIN的值化为 INT.MIN,我自己想到的解法是用更高精度的long去保存,然后转化成int类型的值
    代码: https://github.com/yyxd/leetcode/blob/master/src/leetcode/strings/Problem8_atoi.java
    2019-02-08
    1
  • kai
    哇塞,老师太牛了,过年都在更新,一直在跟着老师的课程在总结归纳,同时找来题目在练习,这个专栏很牛~
    2019-02-08
    1
  • hopeful
    #字符串转整数
    class Solution:
        def myAtoi(self, str: str) :
            pattern = r"[\s]*[+-]?[\d]+"
            match = re.match(pattern, str)
            if match:
                res = int(match.group(0))
                if res > 2 ** 31 - 1:
                    res = 2 ** 31 -1
                if res < - 2 ** 31:
                    res = - 2 ** 31
            else:
                res = 0
            return res
    2019-03-11
  • hopeful
    #反转字符串
    class Solution:
        def reverseString(self, s):
            low = 0
            high = len(s)-1
            while low <= high:
                s[low] , s[high] = s[high] , s[low]
                low+=1
                high-=1
            return s
    2019-02-19
  • 你看起来很好吃
    字符串转换整数python实现:
    import math

    class Solution:
        def myAtoi(self, str: 'str') -> 'int':
            result = 0

            i, N, former = 0, len(str), 1

            while i < N:
                if str[i] != ' ':
                    break
                i += 1
                
            if i < N and (str[i] == '-' or str[i] == '+'):
                former = -1 if str[i] == '-' else 1
                i += 1
                
            while i < N:
                if str[i].isdigit():
                    result = result * 10 + int(str[i])
                    i += 1
                else:
                    break

            result = result * former
            if result > (math.pow(2, 31) * -1) and result < (math.pow(2,31) - 1):
                return result
            elif former > 0 :
                return int(math.pow(2,31) - 1)
            else:
                return int(math.pow(2,31) * -1)
    2019-02-10
  • 纯洁的憎恶
    1.从两端向中间两两对调,时间复杂度O(n)。

    2.先去空格,O(n^2)。从两端向中间查找单词,找到一对单词s、t(s在前t在后),保存这两个单词,如果s长t短,把它们之间的字符串整体左移长度差个字符,反之整体右移长度差个字符,再把s和t按调整后位置向原数组赋值,O(n^2)。

    3.如果字符串全为空、全为空格、首个非空格字符非法,则返回0。若首个合法字符位“-”则记录。int num=0;逐个读取数字部分字符a,若a合法,则num*=10,然后num+=a-‘0’,直到读取结束或者读到非法字符,此时如果记录的首个合法字符为“-”返回num*(-1),否则返回num。不知int型运算过程中结果值溢出,是否自动将值设置为边界值。如果不能就要在每次乘10的时候结合“-”考察一下是否越界。

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-09
  • 你看起来很好吃
    反转字符串python实现:
    class Solution:
        def reverseString(self, s: 'List[str]') -> 'None':
            """
            Do not return anything, modify s in-place instead.
            """
            i, N = 0, len(s)
            while i < N//2:
                s[i], s[N-1-i] = s[N-1-i], s[i]
                i += 1
                
            print(s)
    2019-02-09
  • molybdenum
    老师新年好,这是我第四天的作业
    https://blog.csdn.net/github_38313296/article/details/86818634

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-09
  • ext4
    反转字符串
    class Solution {
    public:
        string reverseString(string s) {
            int length = s.length();
            if (length < 2) {
                return s;
            }
            int i = 0, j = length - 1;
            char temp;
            while (i < j) {
                temp = s[i];
                s[i] = s[j];
                s[j] = temp;
                i++;
                j--;
            }
            return s;
        }
    };
    2019-02-09
  • 虎虎❤️
    itoa

    public class Solution {
    public int myAtoi(String str) {
    if (str.isEmpty())
    return 0;
    str = str.trim();
    int i = 0, ans = 0, sign = 1, len = str.length();
    if (str.charAt(i) == '-' || str.charAt(i) == '+')
    sign = str.charAt(i++) == '+' ? 1 : -1;
    for (; i < len; ++i) {
    int tmp = str.charAt(i) - '0';
    if (tmp < 0 || tmp > 9)
    break;
    if (ans > Integer.MAX_VALUE / 10
    || (ans == Integer.MAX_VALUE / 10 && Integer.MAX_VALUE % 10 < tmp))
    return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
    else
    ans = ans * 10 + tmp;
    }
    return sign * ans;
    }
    }
    2019-02-08
  • _CountingStars
    反转字符串 go 语言实现
    package main

    import "fmt"

    func reverseString(s []byte) {
    length := len(s)
    for i := 0; i < length/2; i++ {
    s[i], s[length-i-1] = s[length-i-1], s[i]
    }
    }

    func main() {
    testString := []byte{'h', 'e', 'l', 'l', 'o'}
    fmt.Println(string(testString[:]))
    reverseString(testString)
    fmt.Println(string(testString[:]))
    }
    2019-02-08
  • 失火的夏天
    LRU缓存淘汰算法
        private class Node{
            private Node prev;
            private Node next;
            private int key;
            private int value;

            Node(int key,int value){
                this.key = key;
                this.value = value;
            }
        }

        private Node head;// 最近最少使用,类似列队的头,出队
        private Node tail;// 最近最多使用,类似队列的尾,入队
        private Map<Integer,Node> cache;
        private int capacity;

        public LRUCache(int capacity) {
            this.cache = new HashMap<>();
            this.capacity = capacity;
        }

        public int get(int key) {
            Node node = cache.get(key);
            if(node == null){
                return -1;
            }else{
                moveNode(node);
                return node.value;
            }
        }

        public void put(int key, int value) {
            Node node = cache.get(key);
            if (node != null){
                node.value = value;
                moveNode(node);
            }else {
                removeHead();
                addNode(new Node(key,value));
            }
            cache.put(key,node);
        }

        private void removeHead(){
            if (cache.size() == capacity){
                Node tempNode = head;
                cache.remove(head.key);
                head = head.next;
                tempNode.next = null;
                if (head != null)
                    head.prev = null;
            }
        }

        private void addNode(Node node){
            if (head == null)
                head = tail = node;
            else
                addNodeToTail(node);
        }

        private void addNodeToTail(Node node){
            node.prev = tail;
            tail.next = node;
            tail = node;
        }

        private void moveNode(Node node){
            if(head == node && node != tail){
                head = node.next;
                head.prev = null;
                node.next = null;
                addNodeToTail(node);
            }else if (tail == node){
            }else {
                node.prev.next = node.next;
                node.next.prev = node.prev;
                node.next = null;
                addNodeToTail(node);
            }
        }
    }
    2019-02-08
  • 反转字符串
    class Solution {
        public void reverseString(char[] s) {
            int start = 0;
            int end = s.length - 1;
            while(start < end){
                swap(s,start,end);
                start++;
                end--;
            }
        }
        
        public void swap(char[] array,int a,int b){
            char tmp = array[a];
            array[a] = array[b];
            array[b] = tmp;
        }
        
        
    }
    2019-02-08
  • 老杨同志
    //字符串转换整数
    package com.jxyang.test.geek.day4.Solution;

    class Solution2 {
        public int myAtoi(String str) {
            if(str==null){
                return 0;
            }
            char[] arr= str.toCharArray();
            boolean flag = false;
            boolean numBegin = false;
            int result = 0;
            for(int i =0;i<arr.length;i++){
                if(numBegin && (arr[i]=='-'||arr[i]=='+'||arr[i]==' ')){
                    break;
                }else if(arr[i]==' ') {
                    continue;
                }else if(arr[i]=='+'){
                    numBegin = true;
                    continue;
                }else if(arr[i]=='-'){
                    flag = true;
                    numBegin = true;
                    continue;
                }else if(arr[i]>='0'&&arr[i]<='9'){
                    numBegin = true;
                    if(result==0){
                        result = flag?('0'-arr[i]):(arr[i]-'0');
                    }else{
                        try{
                            result = Math.multiplyExact(result,10);
                            result = Math.addExact(result,flag?('0'-arr[i]):(arr[i]-'0'));
                        }catch (Exception e){
                            if(flag){
                                return Integer.MIN_VALUE;
                            }else{
                                return Integer.MAX_VALUE;
                            }
                        }
                    }
                }else{
                    break;
                }
            }
            return result;
        }
        public static void main(String[] args) {
            Solution2 solution2 = new Solution2();
            System.out.println(solution2.myAtoi("42"));
            System.out.println(solution2.myAtoi(" +0 123"));//期望123
            System.out.println(solution2.myAtoi(" -42"));
            System.out.println(solution2.myAtoi("4193 with words"));
            System.out.println(solution2.myAtoi("words and 987"));
            System.out.println(solution2.myAtoi("-91283472332"));//期望-2147483648
            System.out.println(solution2.myAtoi("+1"));//期望-2147483648
        }
    }

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-08
  • 老杨同志
    class Solution {
    //反转字符串
        public void reverseString(char[] s) {
            if(s==null||s.length<2){
                return;
            }
            int l=0;
            int r=s.length-1;
            while (l<r){
                char tmp = s[l];
                s[l] = s[r];
                s[r] = tmp;
                l++;
                r--;
            }
        }
    }
    2019-02-08
  • C_love
    Reverse Words in a String

    public class Solution {
        public String reverseWords(String s) {
            final List<String> words = new ArrayList<>();
            final char[] charArray = s.toCharArray();
            
            int start = 0;
            int end = 0;
            while (end < s.length()) {
                if (' ' == charArray[end]) {
                    if (start != end) {
                        words.add(getWord(charArray, start, end));
                        start = end;
                    }
                    start++;
                    end++;
                } else {
                    end++;
                }
            }
            
            if (start != end) {
                words.add(getWord(charArray, start, end));
            }
            
            Collections.reverse(words);
            return String.join(" ", words);
        }
        
        private String getWord(final char[] charArray, final int start, final int end) {
            char[] tmp = new char[end - start];
            int pos = 0;
            for(int i = start; i < end; i++) {
                tmp[pos++] = charArray[i];
            }
            return new String(tmp);
        }
    }
    2019-02-08
收起评论
19
返回
顶部