数据结构和算法的一些基本概念

最近面试，发现所有大厂和一定规模的公司都会问数据结构和算法相关的问题。而我基本的一些概念也没有。现在通过习题学习下数据结构的算法的一些基本概念。对未来刷题有一定帮助。

不是计算机专业出身的前端工程师，数据结构和算法一直是我的弱项，之前有刷题的计划，但是每次都是无脑刷，很打击自信，也没坚持下去。
也买了算法导论和数据结构相关的书籍。但是各方面原因，比如懒，或者看不懂，或者感觉前端学习这个没有用就，一直没有看。本文档大多来自jk时间算法训练营

01 如何学习数据结构和算法

• 精通一个领域
  • Chunk it up 切碎知识点
  • Deliberate Practicing 刻意练习
  • Feedback 反馈
• 数据结构
  • • 一维:
    • • 基础:数组 array (string), 链表 linked list
    • • 高级:栈 stack, 队列 queue, 双端队列 deque, 集合 set, 映射 map (hash or map), etc
  • • 二维:
    • • 基础:树 tree, 图 graph
    • • 高级:二叉搜索树 binary search tree (red-black tree, AVL), 堆 heap, 并查集 disjoint set, 字典树 Trie, etc
  • • 特殊:
    • • 位运算 Bitwise, 布隆过滤器 BloomFilter • LRU Cache
  • 注意:了解每个数据结构的原理和代码框架
• 算法

  • • If-else, switch —> branch

  • • for, while loop —> Iteration

  • • 递归 Recursion (Divide & Conquer, Backtrace)

  • • 搜索 Search: 深度优先搜索 Depth first search, 广度优先搜索 Breadth first search, A*, etc

  • • 动态规划 Dynamic Programming

  • • 二分查找 Binary Search

  • • 贪心 Greedy

  • • 数学 Math , 几何 Geometry

  • 注意:在头脑中回忆上面每种算法的思想和代码模板

• 相关脑图
  • 算法脑图 (opens new window)
  • 数据结构脑图 (opens new window)
• 五步刷题法
• 切题四件套
  • • Clarification
  • • Possible solutions
    • • compare (time/space)
    • • optimal(加强)
  • • Coding(多写)
  • • Test cases

02 复杂度分析

• Big O notation
  • O(n^3): N square Complexity ⽴立⽅方
  • O(log n): Logarithmic Complexity 对数复杂度 O(n): Linear Complexity 线性时间复杂度 O(n^2): N square Complexity 平⽅方
  • O(1): Constant Complexity 常数复杂度
  • O(2^n): Exponential Growth 指数
  • O(n!): Factorial 阶乘

-注意:只看最⾼高复杂度的运算

03 数组、链表、跳表

• Array 数组
  • 基本写法
    • Java, C++: int a[100];
    • Python : list = []
    • JavaScript: let arr =[]
  • api及时间复杂度
    • prepend O(1)
    • append O(1)
    • lookup O(1)
    • insert O(n)
    • delete O(n)
• Linked List 链表
  • api及时间复杂度
    • prepend O(1)
    • append O(1)
    • lookup O(n)
    • insert O(1)
    • delete O(1)
• 跳表
  • 给链表加速，多级索引，加速查找
  • 跳表：升维思想 + 空间换时间
  • api及时间复杂度 / 空间复杂度
    • lookup O(logn) / O(n)
• 工程中的应用
• LRU Cache - Linked list
  • https://www.jianshu.com/p/b1ab4a170c3c https://leetcode-cn.com/problems/lru-cache
• Redis - Skip List
  • https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
  • https://www.zhihu.com/question/20202931
• 习题

1. https://leetcode-cn.com/problems/container-with-most-water/
2. https://leetcode-cn.com/problems/move-zeroes/
3. https://leetcode-cn.com/problems/climbing-stairs/
4. https://leetcode-cn.com/problems/3sum/ (高频老题)
5. https://leetcode-cn.com/problems/reverse-linked-list/
6. https://leetcode-cn.com/problems/swap-nodes-in-pairs
7. https://leetcode-cn.com/problems/linked-list-cycle
8. https://leetcode-cn.com/problems/linked-list-cycle-ii
9. https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
10. https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
11. https://leetcode-cn.com/problems/rotate-array/
12. https://leetcode-cn.com/problems/merge-two-sorted-lists/
13. https://leetcode-cn.com/problems/merge-sorted-array/
14. https://leetcode-cn.com/problems/two-sum/
15. https://leetcode-cn.com/problems/move-zeroes/
16. https://leetcode-cn.com/problems/plus-one/

04 栈、队列、双端队列、优先队列

• Stack
  • FILO
  • 先入后出;添加、删除皆为 O(1)
• Queue
  • FIFO
  • 先入先出;添加、删除皆为 O(1)
• Deque:Double-End Queue
  • 简单理解:两端可以进出的 Queue Deque - double ended queue
  • 插入和删除都是 O(1) 操作
• Stack、Queue、Deque工程实现
• Java、Python、C++ 等已有基础实现
• 查询接口信息
• 示例代码
  • Stack

    Stack<Integer> stack = new Stack<>(); stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4); System.out.println(stack); System.out.println(stack.search(4));
    stack.pop();
    stack.pop();
    Integer topElement = stack.peek(); System.out.println(topElement);
    System.out.println(" 3的位置 " + stack.search(3));
    

  • Queue

    Queue<String> queue = new LinkedList<String>(); queue.offer("one");
    queue.offer("two");
    queue.offer("three");
    queue.offer("four"); System.out.println(queue);
    String polledElement = queue.poll(); System.out.println(polledElement); System.out.println(queue);
    String peekedElement = queue.peek(); System.out.println(peekedElement); System.out.println(queue);
    while(queue.size() > 0) { System.out.println(queue.poll());
    }
    

  • Deque

    Deque<String> deque = new LinkedList<String>();
    deque.push("a"); deque.push("b"); deque.push("c"); System.out.println(deque);
    String str = deque.peek(); System.out.println(str); System.out.println(deque);
    while (deque.size() > 0) {
    System.out.println(deque.pop()); }
    System.out.println(deque);
    

• Priority Queue 优先队列
  1. 插入操作:O(1)
  2. 取出操作:O(logN) - 按照元素的优先级取出
  3. 底层具体实现的数据结构较为多样和复杂:heap、bst、treap
  4. Java 的 PriorityQueue https://docs.oracle.com/javase/10/docs/api/java/util/ PriorityQueue.html
• 实战题目
  1. https://leetcode-cn.com/problems/largest-rectangle-in- histogram
  2. https://leetcode-cn.com/problems/sliding-window-maximum
  3. https://leetcode.com/problems/design-circular-deque
  4. https://leetcode.com/problems/trapping-rain-water/

05 哈希表、映射、集合

哈希表 Hash Table

• 哈希表(Hash table)，也叫散列表，是根据关键码值(Key value)而直接进行访问的数据结构。 它通过把关键码值映射到表中一个位置来访问记录，以加快查找的 速度。
• 这个映射函数叫作散列函数(Hash Function)，存放记录的数组 叫作哈希表(或散列表)。

06 树、二叉树、二叉搜索树

Linked List 是特殊化的 Tree ，Tree 是特殊化的 Graph

07 泛型递归、树的递归

• 递归模版

  # java
  public void recur(int level, int param) {
      // terminator
  if (level > MAX_LEVEL) { // process result
  return; }
      // process current logic
      process(level, param);
      // drill down
      recur( level: level + 1, newParam);
      // restore current status
  }
  

  # python
  def recursion(level, param1, param2, ...): # recursion terminator
  if level > MAX_LEVEL:
        process_result
  return
      # process logic in current level
  process(level, data...) # drill down
  self.recursion(level + 1, p1, ...)
  # reverse the current level status if needed
  

08 分治、回溯

• 分治 Divide & Conquer
  • 分治代码模版

    def divide_conquer(problem, param1, param2, ...): # recursion terminator
      if problem is None:
          print_result
          return
        # prepare data
      data = prepare_data(problem)
      subproblems = split_problem(problem, data)
      # conquer subproblems
      subresult1 = self.divide_conquer(subproblems[0], p1, ...)
      subresult2 = self.divide_conquer(subproblems[1], p1, ...) 
      subresult3 = self.divide_conquer(subproblems[2], p1, ...)
      ...
      # process and generate the final result
      result = process_result(subresult1, subresult2, subresult3, ...)
        # revert the current level states
    

• 回溯 Backtracking ： 递归 + 分治：试错
  • 概念
    • 回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程 中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将 取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问 题的答案。
    • 回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种 情况:
      • 找到一个可能存在的正确的答案;
      • 在尝试了所有可能的分步方法后宣告该问题没有答案。
    • 在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。
• 相关习题：
  • https://leetcode-cn.com/problems/powx-n/
  • https://leetcode-cn.com/problems/subsets/
  • https://leetcode-cn.com/problems/majority-element/ description/ (简单、但是高频)
  • https://leetcode-cn.com/problems/letter-combinations-of-a- phone-number/
  • https://leetcode-cn.com/problems/n-queens/

09 深度优先搜索和广度优先搜索

• 概念：
  • 深度优先 DFS depth first search
  • 广度优先 BFS breath first search
• 树的代码
  • Python

  class TreeNode:
    def __init__(self, val):
      self.val = val
      self.left, self.right = None, None
  

  • Java

    public class TreeNode {
      public int val;
      public TreeNode left, right;
      public TreeNode(int val) {
        this.val = val; 
        this.left = null; 
        this.right = null;
      } 
    }
    

  • C++

    struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    }
    

• 搜索-遍历
  • • 每个节点都要访问一次
  • • 每个节点仅仅要访问一次
  • • 对于节点的访问顺序不限
    • 深度优先:depth first search
    • 广度优先:breadth first search
• 代码展示
  • DFS-递归写法

    visited = set()
    def dfs(node, visited):
      if node in visited: # terminator
          # already visited
          return
      visited.add(node)
      # process current node here.
      # ...
      for next_node in node.children():
        if not next_node in visited:
              dfs(next node, visited)
    

  • DFS-非递归写法

    def DFS(self, tree):
      if tree.root is None:
        return []
      visited, stack = [], [tree.root]
      while stack:
        node = stack.pop() 
        visited.add(node)
    
        process (node)
        nodes = generate_related_nodes(node)
         stack.push(nodes)
        # other processing work
    

  • BFC

    def BFS(graph, start, end):
      queue = [] 
      queue.append([start]) 
      visited.add(start)
      while queue:
        node = queue.pop() 
        visited.add(node)
    
        process(node)
        nodes = generate_related_nodes(node)
        queue.push(nodes)
      # other processing work
      #...
    

• 实战题目
  1. https://leetcode-cn.com/problems/binary-tree-level-order- traversal/#/description
  2. https://leetcode-cn.com/problems/minimum-genetic- mutation/#/description
  3. https://leetcode-cn.com/problems/generate-parentheses/#/ description
  4. https://leetcode-cn.com/problems/find-largest-value-in-each- tree-row/#/description
  5. https://leetcode-cn.com/problems/word-ladder/description/
  6. https://leetcode-cn.com/problems/word-ladder-ii/description/
  7. https://leetcode-cn.com/problems/number-of-islands/
  8. https://leetcode-cn.com/problems/minesweeper/description/

10 贪心算法 Greedy

• 概念
  • 每一步都采取当前状态最好或者最优即最有利的选择，从而导致全局都是最优解
  • 贪心算法和动态规划比较，它对每个问题解决方案都做出选择，不能回退。动态规划会保存以前的运算结果，并根据以前的结果对当前作出选择，有回退功能。
  • 比较
    • 贪心：当下做局部最优解
    • 回溯：可回退
    • 动规：保存之前状态，可回退
• 代码模版
• 应用及不足
  • 解决一些最优化的问题：
  • 高效但是可能全局一定是最优解，做辅助算法
  • 适用贪心算法的场景
    • 最优子结构：问题能够分解成子问题来解决，子问的最优解能够递推到最终问题的最优解。最优子结构
  • 难点就是如何证明贪心算法是最优解

11 二分查找

• 前提
  • 目标函数单调性（有序）
  • 存在上下界 bounded
  • 能索引访问
• 代码模版

  left, right = 0, len(array) - 1 while left <= right:
    mid = (left + right) / 2
    if array[mid] == target:
        # find the target!!
        break or return result
    elif array[mid] < target:
        left = mid + 1
    else:
  right = mid - 1
  

12 动态规划 DP Dynamic Programming

• 回顾
  • 分治、回溯、递归 + 动态规划
  • right clean code
  • 思考
    • 人肉递归很累
    • 将复杂问题简化，拆解为可重复的问题
    • 属性归纳法思维
  • 本质：寻找重复性 -》 计算机指令集
• 概念
  • 1.Wiki 定义: https://en.wikipedia.org/wiki/Dynamic_programming
  • 2.“Simplifying a complicated problem by breaking it down into simpler sub-problems” (in a recursive manner)
  • 3.Divide & Conquer + Optimal substructure 分治 + 最优子结构
  • 将每一步的最优解存储，需要缓存；求证局部最优是否是全局最优
  • 自顶：递归 + 记忆化搜索
• 关键点：
  • 动态规划 和 递归或者分治 没有根本上的区别(关键看有无最优的子结构)
  • 共性:找到重复子问题
  • 差异性:最优子结构、中途可以淘汰次优解
• 实战：
  • fibonacci
  • 路径计数
  • 最长公共子序列：https://leetcode-cn.com/problems/longest-common-subsequence/
• 相关习题：
  1. https://leetcode-cn.com/problems/perfect-squares/
  2. https://leetcode-cn.com/problems/edit-distance/ (重点)
  3. https://leetcode-cn.com/problems/jump-game/
  4. https://leetcode-cn.com/problems/jump-game-ii/
  5. https://leetcode-cn.com/problems/unique-paths/
  6. https://leetcode-cn.com/problems/unique-paths-ii/
  7. https://leetcode-cn.com/problems/unique-paths-iii/
  8. https://leetcode-cn.com/problems/coin-change/
  9. https://leetcode-cn.com/problems/coin-change-2/
  10. 1.https://leetcode-cn.com/problems/longest-valid-parentheses/
  11. 2.https://leetcode-cn.com/problems/minimum-path-sum/
  12. 3.https://leetcode-cn.com/problems/edit-distance/
  13. 4.https://leetcode-cn.com/problems/decode-ways
  14. 5.https://leetcode-cn.com/problems/maximal-square/
  15. 6.https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/
  16. 7.https://leetcode-cn.com/problems/frog-jump/
  17. 8.https://leetcode-cn.com/problems/split-array-largest-sum
  18. 9.https://leetcode-cn.com/problems/student-attendance-record-ii/
  19. 10.https://leetcode-cn.com/problems/task-scheduler/
  20. 11.https://leetcode-cn.com/problems/palindromic-substrings/
  21. 12.https://leetcode-cn.com/problems/minimum-window-substring/
  22. 13.https://leetcode-cn.com/problems/burst-balloons/

13 字典树Tire 、并查集Disjoint Set

• 字典树 Tire

  • 数据结构

    • 字典树，即 Trie 树，又称单词 查找树或键树，是一种树形结 构。典型应用是用于统计和排 序大量的字符串(但不仅限于 字符串)，所以经常被搜索引 擎系统用于文本词频统计。
    • 它的优点是:最大限度地减少 无谓的字符串比较，查询效率 比哈希表高。

  • 核心思想

    • 空间换时间

  • 基本性质

    1. 结点本身不存完整单词;
    2. 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的 字符串;
    3. 每个结点的所有子结点路径代表的字符都不相同。

  • 应用搜索引擎

  • Python实现代码字典树

     class Trie(object):
        def __init__(self):
          self.root = {} 
        self.end_of_word = "#"
      
        def insert(self, word): 
          node = self.root
          for char in word:
            node = node.setdefault(char, {})
        node[self.end_of_word] = self.end_of_word
      
        def search(self, word):
          node = self.root
          for char in word:
            if char not in node:
              return False
            node = node[char]
        return self.end_of_word in node
      
        def startsWith(self, prefix):
          node = self.root
          for char in prefix:
            if char not in node:
              return False
            node = node[char]
          return True
    

  • 题目

    1. https://leetcode-cn.com/problems/implement-trie-prefix-tree/#/ description
    2. https://leetcode-cn.com/problems/word-search-ii/
    3. Search suggestion - system design
• 并查集Disjoint Set
  • 使用场景
    • 组团、配对问题：a和b是否是朋友，是否是在一个群组，何必群组等
    • Grop or not
  • 基本操作
    • • makeSet(s):建立一个新的并查集，其中包含 s 个单元素集合。
    • • unionSet(x, y):把元素 x 和元素 y 所在的集合合并，要求 x 和 y 所在的集合不相交，如果相交则不合并。
    • • find(x):找到元素 x 所在的集合的代表，该操作也可以用于判断两个元 素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。
  • 代码实现
    • 思路
      • 初始化（领头元素，自己指向自己）
      • 查询、合并（找到所有集合的领头元素，串联起来）
      • 路径压缩
    • java

      class UnionFind {
        private int count = 0;
        private int[] parent;
        public UnionFind(int n) {
          count = n;
          parent = new int[n];
          for (int i = 0; i < n; i++) {
            parent[i] = i;
          }
        }
        public int find(int p) {
          while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
          }
          return p; 
        }
        public void union(int p, int q) {
          int rootP = find(p);
          int rootQ = find(q);
          if (rootP == rootQ) return;
          parent[rootP] = rootQ;
          count--; 
        }
      }
      

    • python

      def init(p):
        # for i = 0 .. n: p[i] = i;
        p = [i for i in range(n)]
      def union(self, p, i, j):
         p1 = self.parent(p, i) 
         p2 = self.parent(p, j) 
         p[p1] = p2
      def parent(self, p, i):
        root = i
        while p[root] != root:
          root = p[root]
        while p[i] != i: # 路径压缩 ?
          x = i; i = p[i]; p[x] = root
        return root
      

  • 实战题目
    • • https://leetcode-cn.com/problems/friend-circles 朋友圈
    • • https://leetcode-cn.com/problems/number-of-islands/
    • • https://leetcode-cn.com/problems/surrounded-regions/

14 高级搜索

• 回顾：初级搜索
  • 朴素搜索
  • 优化方式：不重复（fibonacci）、剪枝（生产括号问题）
  • 搜索方向：
    • DFS：递归 / stack
    • BFS：queue
    • 双向搜索
    • 启发式搜索：优先队列
  • Coin Change 零钱置换 的状态树
• 剪枝
  • 状态树某个指已经处理过，缓存下；或者一些不好的分支进行剪掉
  • 机器人下象棋：朴素搜索 + 剪枝
  • 数独
• 双向 BFS
• 实战题目
  1. https://leetcode-cn.com/problems/word-ladder/
  2. https://leetcode-cn.com/problems/minimum-genetic- mutation/
• 启发式搜索（A*）
  • 基于BFS
  • A* search

    def AstarSearch(graph, start, end):
    
      pq = collections.priority_queue() # 优先级 —> 估价函数
      pq.append([start]) 
      visited.add(start)
      while pq:
        node = pq.pop() # can we add more intelligence here ? visited.add(node)
        process(node)
    
        nodes = generate_related_nodes(node)
        unvisited = [node for node in nodes if node not in visited]
        pq.push(unvisited)
    

    • 估价函数
      • 启发式函数: h(n)，它用来评价哪些结点最有希望的是一个我们要找的结 点，h(n) 会返回一个非负实数,也可以认为是从结点n的目标结点路径的估 计成本。
      • 启发式函数是一种告知搜索方向的方法。它提供了一种明智的方法来猜测 哪个邻居结点会导向一个目标。
    • 实战题
      1. https://leetcode-cn.com/problems/shortest-path-in-binary- matrix/
      2. https://leetcode-cn.com/problems/sliding-puzzle/
      3. https://leetcode-cn.com/problems/sudoku-solver/

18 排序算法

• 排序算法

  • 1. 比较类排序:
    • 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
    • 分类：
      • 交换排序：
        • 冒泡排序
        • 快速排序
      • 插入排序
        • 简单插入排序
        • 希尔排序
      • 选择排序
        • 简单选择排序
        • 堆排序
      • 归并排序
        • 二路归并排序
        • 多路归并排序
  • 2. 非比较类排序:
    • 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时 间下界，以线性时间运行，因此也称为线性时间非比较类排序。
    • 只能用于整形，额外的空间
    • 分类：
      • 计数排序
      • 桶排序
      • 基数排序

• 排序的复杂度：

• 快速排序 Quick Sort

  • 数组取标杆 pivot，将小元素放 pivot左边，大元素放右侧，然后依次 对右边和右边的子数组继续快排;以达到整个序列有序。

  public static void quickSort(int[] array, int begin, int end) { 
      if (end <= begin) return;
      int pivot = partition(array, begin, end);
      quickSort(array, begin, pivot - 1);
      quickSort(array, pivot + 1, end);
  }
  static int partition(int[] a, int begin, int end) { 
      // pivot: 标杆位置，counter: 小于pivot的元素的个数
      int pivot = end, counter = begin; 
      for (int i = begin; i < end; i++) {
          if (a[i] < a[pivot]) {
            int temp = a[counter]; a[counter] = a[i]; a[i] = temp;
            counter++;
          } 
      }
      int temp = a[pivot]; a[pivot] = a[counter]; a[counter] = temp;
      return counter;
  }
  

• 归并排序 Merge Sort

  • 1. 把长度为n的输入序列分成两个长度为n/2的子序列;
  • 2. 对这两个子序列分别采用归并排序;
  • 3. 将两个排序好的子序列合并成一个最终的排序序列。

  public static void mergeSort(int[] array, int left, int right) { 
      if (right <= left) return;
      int mid = (left + right) >> 1; // (left + right) / 2
  
      mergeSort(array, left, mid);
      mergeSort(array, mid + 1, right);
      merge(array, left, mid, right);
  }
  

  merge

  public static void merge(int[] arr, int left, int mid, int right) { 
    int[] temp = new int[right - left + 1]; // 中间数组
    int i = left, j = mid + 1, k = 0;
  
    while (i <= mid && j <= right) {
      temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
  
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
  
    for (int p = 0; p < temp.length; p++) {
      arr[left + p] = temp[p];
    }
    // 也可以用 System.arraycopy(a, start1, b, start2, length) 
  }
  

• 高级排序

  • 归并 和 快排 具有相似性，但步骤顺序相反
    • 归并:先排序左右子数组，然后合并两个有序子数组
    • 快排:先调配出左右子数组，然后对于左右子数组进行排序

• 堆排序 Heap Sort — 堆插入 O(logN)，取最大/小值 O(1)

  1. 数组元素依次建立小顶堆
  2. 依次取堆顶元素，并删除

• 排序动画

  • https://www.cnblogs.com/onepixel/p/7674659.html
  • https://www.bilibili.com/video/av25136272
  • https://www.bilibili.com/video/av63851336

• 题目

  • • https://leetcode-cn.com/problems/relative-sort-array/
  • • https://leetcode-cn.com/problems/valid-anagram/
  • • https://leetcode-cn.com/problems/design-a-leaderboard/
  • • https://leetcode-cn.com/problems/merge-intervals/
  • • https://leetcode-cn.com/problems/reverse-pairs/

20 字符串算法

• 字符串

  • python：
    • x ='abc'
    • x = "abc"
  • Java:
    • String x= "abbc"
  • C++:
    • string x("abbc)
  • string immutable: (opens new window)

• 遍历字符串

• 字符串比较

• 字符串相关的算法

  • 回文串
  • 最长子串、子序列
  • 字符串 + 递归 or DP
  • 字符串匹配算法
    • 暴力法
    • Rabin-Karp算法
    • KNP算法

• 基础算法

  1. https://leetcode-cn.com/problems/to-lower-case/
  2. https://leetcode-cn.com/problems/length-of-last-word/
  3. https://leetcode-cn.com/problems/jewels-and-stones/
  4. https://leetcode-cn.com/problems/first-unique-character-in- a-string/
  5. https://leetcode-cn.com/problems/string-to-integer-atoi/

• 字符串操作问题

  1. https://leetcode-cn.com/problems/longest-common-prefix/ description/
  2. https://leetcode-cn.com/problems/reverse-string https://leetcode-cn.com/problems/reverse-string-ii/
  3. https://leetcode-cn.com/problems/reverse-words-in-a-string/ https://leetcode-cn.com/problems/reverse-words-in-a-string- iii/
  4. https://leetcode-cn.com/problems/reverse-only-letters/

• Anagram异位词问题

  1. https://leetcode-cn.com/problems/valid-anagram/
  2. https://leetcode-cn.com/problems/group-anagrams/
  3. https://leetcode-cn.com/problems/find-all-anagrams-in-a- string/

• Palindrome 回文串问题

  1. https://leetcode-cn.com/problems/valid-palindrome/
  2. https://leetcode-cn.com/problems/valid-palindrome-ii/
  3. https://leetcode-cn.com/problems/longest-palindromic- substring/

• 最长子串、子序列

  1. Longest common sequence(最长子序列) https://leetcode-cn.com/problems/longest-common-subsequence/ dp[i][j] = dp[i-1][j-1] + 1 (if s1[i-1] == s2[j-1]) else dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  2. Longest common substring (最长子串)dp[i][j] = dp[i-1][j-1] + 1 (if s1[i-1] == s2[j-1]) else dp[i][j] = 0
  3. Edit distance(编辑距离) https://leetcode-cn.com/problems/edit-distance/

• 字符串 + 递归 or DP

  1. https://leetcode-cn.com/problems/regular-expression- matching/
  2. https://leetcode-cn.com/problems/regular-expression-matching/solution/ji-yu-guan-fang-ti-jie-gen-xiang-xi-de-jiang- jie-b/
  3. https://leetcode-cn.com/problems/wildcard-matching/

• 练习题

  1. https://leetcode-cn.com/problems/first-unique-character-in-a-string/
  2. https://leetcode-cn.com/problems/string-to-integer-atoi/
  3. https://leetcode-cn.com/problems/reverse-string-ii/
  4. https://leetcode-cn.com/problems/reverse-words-in-a-string/
  5. https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
  6. https://leetcode-cn.com/problems/reverse-only-letters/
  7. https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
  8. https://leetcode-cn.com/problems/longest-palindromic-substring/
  9. https://leetcode-cn.com/problems/isomorphic-strings/
  10. https://leetcode-cn.com/problems/valid-palindrome-ii/
  11. https://leetcode-cn.com/problems/wildcard-matching
  12. https://leetcode-cn.com/problems/longest-valid-parentheses
  13. https://leetcode-cn.com/problems/distinct-subsequences/