leetcode整理

目录

• 基础
• 分治
• 散列
• 数组
• 字符串
• 双指针
• 栈
• 堆
• 树
• 链表
• 图
• 动态规划
• 回溯
• BFS
• 数学
• 并发
• SQL

基础

频率

leetcode难度及面试频率

散列

• 选择散列函数

  • Division method

    • $h(k)=k \mod m$

  • Multiplication method

    • $m=2^r$，计算机有$w$位词

    • $h(k)=(A\cdot k\mod 2^w)\rm{rsh}(w-r)$
    • 模块轮 (Modular wheel)：将轮子旋转$k$个$A$，然后舍弃最后几位

  http://www.alloyteam.com/2017/05/hash-functions-introduction/

  加法、位运算、乘法、除法、查表、混合

  一个好的哈希函数应该具备以下三点：

  1. 抗碰撞性，尽量避免冲突。
  2. 抗篡改性，只要改动一个字节，其哈希值也会很大不同。
  3. 查找效率。

• 处理冲突

  • 拉链法

    填装因子$\alpha=表中记录数（键数）n/散列表长度（槽数）m$

    不成功搜索的期望时间$=\Theta(1+\alpha)$

  • 开放定址法：线性探查法、平方探查法、再散列法、伪随机序列法

    假设均匀散列，每个键等可能地将$m!$种排序之一作为其探查序列。

    定理：不成功搜索的期望探查次数 $E[$#$probes]\le1/(1-\alpha)$

B树和B+树

王道数据结构P243 B树和B+树

• B树

  一棵$m$阶B树或为空树，或为满足如下特征的$m$叉树：

  1. 树中每个结点至多有$m$棵子树（即至多含有$m-1$个关键字）。

  2. 若根节点不是终端结点，则至少有2棵子树。

  3. 除根结点外的所有非叶结点至少有$\lceil m/2\rceil$棵子树（即至少含有$\lceil m/2\rceil-1$个关键字）

  4. 所有的非叶结点的结构：$n,P_0,K_1,P_1,K_2,P_2,…,K_n,P_n$. 其中$K_i$为结点的关键字，且满足$K_1\lt K_2\lt…\lt K_n$; $P_i$所指子树中所有结点的关键字均大于$K_i$, $n$为结点中关键字的个数。

  5. 所有的叶节点都出现再同一层次上，并且不带信息。

  B树的插入：定位（找到最底层的某个非叶结点），插入（分裂上移）

  B树的删除：不在终端结点删除（删除合并），在终端结点删除（兄弟够借，兄弟不够借）

• B+树

  $m$阶B+树与$m$阶B树的主要差异在于：

  1. 在B+树中，具有$n$个关键字的结点只含有$n$棵子树，即每个关键字对应一棵子树；而在B树中，具有$n$个关键字的结点含有$(n+1)$棵子树。

  2. 在B+树中，每个结点（非根内部结点）关键字个数$n$的范围时$\lceil m/2\rceil \le n \le m$（根结点：$1\le n\le m-1$）；在B树中，每个结点（非根内部结点）关键字个数$n$的范围是$\lceil m/2\rceil-1 \le n \le m-1$（根结点：$1\le n\le m-1$）。

  3. 在B+树中，叶结点包含信息，所有非叶节点仅起到索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

  4. 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

布隆过滤器

什么是布隆过滤器

布隆过滤器（Bloom Filter）是一个叫做 Bloom 的老哥于1970年提出的。我们可以把它看作由二进制向量（或者说位数组）和一系列随机映射函数（哈希函数）两部分组成的数据结构。相比于我们平时常用的的 List、Map 、Set 等数据结构，它占用空间更少并且效率更高，但是缺点是其返回的结果是概率性的，而不是非常准确的。理论情况下添加到集合中的元素越多，误报的可能性就越大。并且，存放在布隆过滤器的数据不容易删除。

布隆过滤器的原理

当一个元素加入布隆过滤器中的时候，会进行如下操作：

1. 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。
2. 根据得到的哈希值，在位数组中把对应下标的值置为 1。

当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：

1. 对给定元素再次进行相同的哈希计算；
2. 得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。

布隆过滤器使用场景

1. 判断给定数据是否存在：比如判断一个数字是否在于包含大量数字的数字集中（数字集很大，5亿以上！）、 防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）、邮箱的垃圾邮件过滤、黑名单功能等等。
2. 去重：比如爬给定网址的时候对已经爬取过的 URL 去重。

https://www.zhihu.com/question/38573286

• 海量数据的TopK问题

  https://www.cnblogs.com/itxiaok/p/10385676.html

  • 找重复最多的TopK：散列成多个小数据集再统计
  • 找最大TopK：外排、优先队列、分治找最大
  • 去重：布隆过滤器

• 跳表

  https://blog.csdn.net/lusic01/article/details/92001898

主方法

CLRS

对于形式$T(n)=aT(n/b)+f(n)$的递归，分为3种情况：

1. $f(n)=O(n^{\log_ba-\varepsilon})$

   $f(n)$多项式地慢于$n^{\log_ba}$增长（相差$n^\varepsilon$）

   结论：$T(n)=\Theta(n^{\log_ba})$

2. $f(n)=\Theta(n^{\log_ba}\log^kn)$

   $f(n)$与$n^{\log_ba}$以相似速率增长

   结论：$T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$

3. $f(n)=\Omega(n^{\log_ba+\varepsilon})$

   $f(n)$多项式地快于$n^{\log_ba}$增长（相差$n^\varepsilon$）

   结论：$T(n)=\Theta(f(n))$

二分查找

• 一般的二分查找

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  int binarySearch(int n, int key) {
      int lo = 0;
      int hi = n - 1;
      while(lo <= hi) {
          int mid = (lo + hi) / 2;
          if(num[mid] < key) lo = mid + 1;
          else if(num[mid] > key) hi = mid - 1;
          else return mid;
      }
      return lo;
  }
  

• 找到第一个大于等于目标值的位置

  解释：如果目标值大于中间数，在右半边查找；如果目标值小于等于中间数，在左半边查找。当目标值等于中间数时，将会放弃中间数在左半边查找，最后一次循环lo == hi时，lo的值又会增1​，所以可以找到等于目标值的第一个数。

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  int binarySearch(int n, int key) {
      int lo = 0;
      int hi = n - 1;
      while(lo <= hi) {
          int mid = (lo + hi) / 2;
          if(num[mid] < key) lo = mid + 1;
          else hi = mid - 1;
      }
      return lo;
  }
  

排序

• 插入排序：时间$O(n^2)$，空间$O(1)$，稳定

  1
  2
  3
  4
  5
  6
  7
  void insetionSort(int[] a, int N) {
      for(int i = 1; i < N; i++) {
          for(int j = i; j > 0 && a[j] < a[j-1]; j--) {
              exch(a, j, j-1);
          }
      }
  }
  

• 选择排序：时间$O(n^2)$，空间$O(1)$，不稳定

  1
  2
  3
  4
  5
  6
  7
  8
  9
  void selectionSort(int[] a, int N) {
      for(int i = 0; i < N; i++) {
          int min = i;
          for(int j = i+1; j < N; j++) {
              if(a[j] < a[min]) min = j;
          }
          exch(a, i, min);
      }
  }
  

• 冒泡排序：时间$O(N^2)$，空间$O(1)$，稳定

  1
  2
  3
  4
  5
  6
  7
  void bubleSort(int[] a, int N) {
      for(int i = 0; i < N-1; i++) {
          for(int j = N-1; j > i; j--) {
              if(a[j-1] > a[j]) exch(a, j-1, j);
          }
      }
  }
  

• 希尔排序（对比插入排序）：时间$O(n^{1.3})$，最坏$O(n^2)$，空间$O(1)$，不稳定

  1
  2
  3
  4
  5
  6
  7
  8
  9
  void shellSort(int[] a, int N) {
      for(int h = N/2; h >= 1; h /= 2) {
          for(int i = h; i < N; i++) {
              for(int j = i; j >= h && a[j] < a[j-h]; j -= h) {
                  exch(a, j, j-h);
              }
          }
      }
  }
  

• 归并排序：时间$O(n\log n)$，空间$O(n)$，稳定

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  int[] aux = new int[N];
  
  void mergeSort(int[] a, int lo, int hi) {
      if(hi <= lo) return;
      int mid = (lo + hi) / 2;
      mergeSort(a, lo, mid);
      mergeSort(a, mid+1, hi);
      merge(a, lo, mid, hi);
  }
    
  void merge(int[] a, int lo, int mid, int hi) {
      int i = lo, j = mid + 1;
      for(int k = lo; k <= hi; k++) {
          aux[k] = a[k];
      }
      for(int k = lo; k <= hi; k++) {
          if(i > mid) a[k] = aux[j++];
          else if(j > hi) a[k] = aux[i++];
          else if(aux[j] < aux[i]) a[k] = aux[j++];
          else a[k] = aux[i++];
      }
  }
  

• 快速排序：时间$O(n\log n)$，最坏$O(n^2)$，空间$O(\log n)$，最坏$O(n)$，不稳定

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  void quickSort(int[] a, int lo, int hi) {
      if(hi <= lo) return;
      int j = partition(a, lo, hi);
      quickSort(a, lo, j-1);
      quickSort(a, j+1, hi);
  }
  
  int partition(int[] a, int lo, int hi) {
      int i = lo, j = hi+1;
      int pivot = a[lo];
      while(true) {
          while(a[++i] < pivot) if(i == hi) break;
          while(pivot < a[--j]) if(j == lo) break;
          if(i >= j) break;
          exch(a, i, j);
      }
      exch(a, lo, j);
      return j;
  }
  

• 堆排序（大根堆）

  删除堆顶元素：先将堆的最后一个元素与堆顶元素交换，再对此时的根结点进行sink操作。

  插入：先将新结点放在堆的末端，再对这个新结点进行swim操作。

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  void heapSort(int[] a, int N) {
      // 建堆
      for(int k = N/2; k >= 1; k--) {
          sink(a, k, N);
      }
      // 排序：不断删除堆顶元素，放到末尾
      while(N > 1) {
          exch(a, 1, N--);
          sink(a, 1, N);
      }
  }
  
  void swim(int[] a, int k) {
      while(k > 1 && a[k/2] < a[k]) {
          exch(a, k/2, k);
          k /= 2;
      }
  }
  
  void sink(int[] a, int k, int N) {
      while(2*k <= N) {
          int j = 2*k;
          if(j < N && a[j] < a[j+1]) j++;
          if(a[k] >= a[j]) break;
          exch(a, k, j);
          k = j;
      }
  }
  

• 回溯

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  // Backtracking pseudocode
  bool Solve(configuration conf) {
      if (no more choices) // BASE CASE
          return (conf is goal state);
      for (all available choices) {
          try one choice c;
          // solve from here, if works out, you're done
          if (Solve(conf with choice c made)) return true;
          unmake choice c;
      }
      return false; // tried all choices, no soln found
  }
  

• DFS

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  bool mark[];
  
  void dfs(Graph G, int v) {
      marked[v] = true;
      for(int w: G.adj(v)) {
          if(!marked[w]) {
              dfs(G, w);
          }
      }
  }
  
  int main() {
      for(int s = 0; s < G.V(); s++) {
          if(!mark[s]) {
              dfs(G, s);
          }
      }
  
      return 0;
  }
  

• BFS

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  void bfs(Graph G, int s) {
      queue<int> q;
  
      marked[s] = true;
      q.push(s);
      while(!q.empty()) {
          int v = q.front();
          q.pop();
          for(int w: G.adj(v)) {
              if(!marked[w]) {
                  marked[w] = true;
                  q.push(w);
              }
          }
      }
  }
  

• 并查集

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  #include <cstdio>
  
  int tree[];
  
  int findRoot(int x) {
      if(tree[x] == -1) return x;
      int ret = findRoot(tree[x]);
      tree[x] = ret;
      return ret;
  }
  
  int main() {
      for(int i = 1; i <= n; i++)
          tree[i] = -1;
      while(m--) {
          int a, b;
          scanf("%d%d", &a, &b);
          a = findRoot(a);
          b = findRoot(b);
          if(a != b) tree[a] = b;
      }
      int res = 0;
      for(int i = 1; i <= n; i++) {
          if(tree[i] == -1) res++;
      }
  
      return 0;
  }
  

• 最小生成树(MST) Kruskal

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  #include <cstdio>
  #include <algorithm>
  
  int tree[];
  struct Edge {
      int a, b;
      int cost;
  
      bool operator < (const Edge& b) const {
          return cost < b.cost;
      }
  } edge[];
  
  int findRoot(int x) {
      if(tree[x] == -1) return x;
      int ret = findRoot(tree[x]);
      tree[x] = ret;
      return ret;
  }
  
  int main() {
      for(int i = 0; i < n*(n-1)/2; i++) {
          scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].cost);
      }
      sort(edge, edge+n*(n-1)/2);
      for(int i = 1; i <= n; i++) {
          tree[i] = -1;
      }
      int res = 0;
      for(int i = 0; i < n*(n-1)/2; i++) {
          int a = findRoot(edge[i].a);
          int b = findRoot(edge[i].b);
          if(a != b) {
              tree[a] = b;
              res += edge[i].cost;
          }
      }
      printf("%d\n", res);
  
      return 0;
  }
  

• Dijkstra 邻接表

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  #include <cstdio>
  #include <algorithm>
  #include <vector>
  
  const int INF = 0x7fffffff;
  
  struct Edge {
      int to;
      int cost;
  };
  vector<Edge> edge[];
  bool mark[];
  int dist[];
  
  int main() {
      for(int i = 1; i <= n; i++) {
          edge[i].clear();
          mark[i] = false;
          dist[i] = -1;
      }
      for(int i = 1; i <= m; i++) {
          int a, b, c;
          scanf("%d%d%d", &a, &b, &c);
          Edge tmp;
          tmp.cost = c;
          tmp.to = b;
          edge[a].push_back(tmp);
          tmp.to = a;
          edge[b].push_back(tmp);
      }
      mark[1] = true;
      dist[1] = 0;
      int newPoint = 1;
      for(int i = 0; i < n-1; i++) {
          int len = edge[newPoint].size();
          for(int j = 0; j < len; j++) {
              int to = edge[newPoint][j].to;
              int cost = edge[newPoint][j].cost;
              if(mark[to]) continue;
              if(dist[to] == -1 || dist[to] > dist[newPoint] + cost)
                  dist[to] = dist[newPoint] + cost;
          }
          int min = INF;
          for(int j = 1; j <= n; j++) {
              if(mark[j]) continue;
              if(dist[j] == -1) continue;
              if(dist[j] < min) {
                  min = dist[j];
                  newPoint = j;
              }
          }
          mark[newPoint] = true;
      }
      return 0;
  }
  

• 拓扑排序

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  class Solution {
  public:
      vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
          vector<vector<int>> graph(numCourses, vector<int>());
          vector<int> indegree(numCourses, 0);
          for(vector<int> prerequisite: prerequisites) {
              int start = prerequisite[1];
              int end = prerequisite[0];
              graph[start].push_back(end);
              indegree[end]++;
          }
          vector<int> res;
          queue<int> q;
          for(int i = 0; i < numCourses; i++) {
              if(indegree[i] == 0) {
                  q.push(i);
              }
          }
          while(!q.empty()) {
              int node = q.front();
              res.push_back(node);
              q.pop();
              for(int neighbour: graph[node]) {
                  indegree[neighbour]--;
                  if(indegree[neighbour] == 0) {
                      q.push(neighbour);
                  }
              }
          }
          return res.size()==numCourses? res: vector<int>();
      }
  };
  

• 0-1背包

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  #include <cstdio>
  #include <algorithm>
  using namespace std;
  
  int dp[];
  
  struct List {
      int volume;
      int weight;
  } list[];
  
  int main() {
      int v, n;
      scanf("%d%d", &v, &n);
      for(int i = 1; i <= n; i++) {
          scanf("%d%d", &list[i].volume, &list[i].weight);
      }
      for(int j = 0; j <= v; j++) {
          dp[j] = 0;
      }
      for(int i = 1; i <= n; i++) {
          for(int j = v; j >= list[i].volume; j--) {
              dp[j] = max(dp[j-list[i].volume] + list[i].weight, dp[j]);
          }
      }
      printf("%d\n", dp[v]);
  
      return 0;
  }
  

  初始化分两种情况：

  1. 如果背包要求正好装满则初始化 f[0] = 0, f[1~w] = -INF;
  2. 如果不需要正好装满 f[0~v] = 0;

• 完全背包

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  #include <cstdio>
  #include <algorithm>
  using namespace std;
  
  const int INF = 0x7fffffff;
  int dp[];
  
  struct List {
      int volume;
      int weight;
  } list[];
  
  int main() {
      int t;
      scanf("%d", &t);
      while(t--) {
          int a, b, n;
          scanf("%d%d%d", &a, &b, &n);
          int v = b - a;
          for(int i = 1; i <= n; i++) {
              scanf("%d%d", &list[i].weight, &list[i].volume);
          }
          dp[0] = 0;
          for(int j = 1; j <= v; j++) {
              dp[j] = INF;
          }
          for(int i = 1; i <= n; i++) {
              for(int j = list[i].volume; j <= v; j++) {
                  if (dp[j-list[i].volume] != INF)
                      dp[j] = min(dp[j-list[i].volume] + list[i].weight, dp[j]);
              }
          }
          if(dp[v] == INF) printf("This is impossible.\n");
          else printf("The minimum amount of money in the piggy-bank is %d\n", dp[v]);
      }
  
      return 0;
  }
  

• 最大公共子序列、最大公共子串

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  int dp[][] = new int[s1.length()+1][s2.length()+1];
  for(int i = 1; i <= s1.length(); i++) {
      for(int j = 1; j <= s2.length(); j++) {
          if(s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
          //else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
          else dp[i][j] = 0;
      }
  }
  for(int i = 0; i <= s1.length(); i++) {
      for(int j = 0; j <= s2.length(); j++) {
          System.out.format("%d ", dp[i][j]);
      }
      System.out.println();
  }
  System.out.println(dp[s1.length()][s2.length()]);
  

• 哈夫曼树

  思路：将所有节点放到小顶堆里，每次拿出最小的两个节点，加起来放回堆里。

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  #include <cstdio>
  #include <queue>
  
  using namespace std;
  
  struct cmp {
      bool operator()(const int& a, const int& b) {
          return a > b;
      }
  };
  
  priority_queue<int, vector<int>, cmp> pq;
  
  int main() {
      int n;
      while(scanf("%d", &n) != EOF) {
          while(n--) {
              int node;
              scanf("%d", &node);
              pq.push(node);
          }
          int a, b, res = 0;
          a = pq.top();
          pq.pop();
          b = pq.top();
          pq.pop();
          res += (a+b);
          while(!pq.empty()) {
              a = a + b;
              b = pq.top();
              pq.pop();
              res += (a+b);
          }
          printf("%d\n", res);
      }
  
      return 0;
  }
  

分治

leetcode 74: 搜索二维矩阵

• 题意：矩阵中行有序，后面一行的第一个数比前一行最后一个数大。

• 方法1：两次二分查找

  • 思路：先二分查找到目标值可能在的那一行（比较方便的方法是找到最后一列大于等于目标值的那一行），然后二分查找那一行。

  • 时间：$O(\log m+\log n)=O(\log mn)$

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            // [] => 0
            // [[]] => 0
            if(matrix.size() == 0) return false;
            if(matrix[0].size() == 0) return false;
                
            // binary search row
            // <=
            int lo = 0;
            int hi = matrix.size() - 1;
            while(lo <= hi) {
                int mid = (lo + hi) / 2;
                if(matrix[mid][0] < target) lo = mid + 1;
                else  hi = mid - 1;
            }
            if(lo < matrix.size() && matrix[lo][0] == target) return true;
            if(lo == 0) return false;
            int row = lo - 1;
                
            // binary search col
            // >=
            lo = 0;
            hi = matrix[row].size() - 1;
            while(lo <= hi) {
                int mid = (lo + hi) / 2;
                if(matrix[row][mid] < target) lo = mid + 1;
                else  hi = mid - 1;
            }
            if(lo < matrix[row].size() && matrix[row][lo] == target) return true;
            return false;
        }
    };
    

• 方法2：一次二分查找

  • 思路：直接当成一维数组进行二分查找。

  • 时间：$O(\log mn)$

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            // [] => 0
            // [[]] => 0
            int rows = matrix.size();
            if(rows == 0) return false;
            int cols = matrix[0].size();
            if(cols == 0) return false;
                
            int lo = 0;
            int hi = rows * cols - 1;
            while(lo <= hi) {
                int mid = (lo + hi) / 2;
                if(matrix[mid/cols][mid%cols] < target) lo = mid + 1;
                else hi = mid - 1;
            }
            if(lo < rows * cols && matrix[lo/cols][lo%cols] == target) return true;
            return false;
        }
    };
    

leetcode 240: 搜索二维矩阵II

• 题意：矩阵中行有序列有序，查找目标值。

• 方法1：分治

  • 思路：第4象限的数一定比中间值大，第3象限的数一定比中间值小，所以比较中间值与目标值的大小，可以将问题转化为3个子问题。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
      zone 1      zone 2
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
    -----------------------
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
      zone 3      zone 4
    

  • 时间：$T(mn)=3T(mn/4)+O(1)$，根据主方法，$T(mn)=\Theta((mn)^{\log_43})$.
  • 参考

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if(matrix.empty()) return false;
            if(matrix[0].empty()) return false;
            int rows = matrix.size();
            int cols = matrix[0].size();
                
            return searchMatrix(matrix, target, 0, 0, rows-1, cols-1);
        }
        
    private:
        bool searchMatrix(vector<vector<int>>& matrix, int target, int loI, int loJ, int hiI, int hiJ) {
            cout << loI << " " << loJ << " " << hiI << " " << hiJ << endl;
            if(loI > hiI || loJ > hiJ) return false;
            if(loI == hiI && loJ == hiJ) return matrix[loI][loJ] == target;
                
            int midI = (loI + hiI) / 2;
            int midJ = (loJ + hiJ) / 2;
            if(matrix[midI][midJ] > target) {
                if(searchMatrix(matrix, target, loI, loJ, midI, midJ)) return true;       // 1st quadrant
                if(searchMatrix(matrix, target, loI, midJ+1, midI, hiJ)) return true;     // 2nd quadrant
                if(searchMatrix(matrix, target, midI+1, loJ, hiI, midJ)) return true;     // 3rd quadrant
            } else if(matrix[midI][midJ] < target) {
                if(searchMatrix(matrix, target, loI, midJ+1, midI, hiJ)) return true;     // 2nd quadrant
                if(searchMatrix(matrix, target, midI+1, loJ, hiI, midJ)) return true;     // 3rd quadrant
                if(searchMatrix(matrix, target, midI+1, midJ+1, hiI, hiJ)) return true;   // 4rd quadrant
            } else {
                return true;
            }
            return false;
        }
    };
    

• 方法2：二叉搜索树

  • 思路：将矩阵视为二叉搜索树，根节点为矩阵右上角或左下角的节点。

    

  • 时间：$O(m+n)$

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if(matrix.empty()) return false;
            if(matrix[0].empty()) return false;
            int rows = matrix.size();
            int cols = matrix[0].size();
                
            int i = 0;
            int j = cols - 1;
            while(i < rows && j >= 0) {
                if(matrix[i][j] == target) return true;
                else if(matrix[i][j] > target) j--;
                else i++;
            }
            return false;
        }
    };
    

leetcode 4: 寻找两个有序数组的中位数

时间：$O(\log (n+m))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def median(A, B):
    m, n = len(A), len(B)
    if m > n:
        A, B, m, n = B, A, n, m
    if n == 0:
        raise ValueError

    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if i < m and B[j-1] > A[i]:
            # i is too small, must increase it
            imin = i + 1
        elif i > 0 and A[i-1] > B[j]:
            # i is too big, must decrease it
            imax = i - 1
        else:
            # i is perfect

            if i == 0: max_of_left = B[j-1]
            elif j == 0: max_of_left = A[i-1]
            else: max_of_left = max(A[i-1], B[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = B[j]
            elif j == n: min_of_right = A[i]
            else: min_of_right = min(A[i], B[j])

            return (max_of_left + min_of_right) / 2.0

leetcode 33: 搜索旋转排序数组

• 题意：旋转数组无重复

• 思路：分为左半边有序和右半边有序两种情况，左半边有序看target是否落入左半边，右半边有序看target是否落入右半边。

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  class Solution {
  public:
      int search(vector<int>& nums, int target) {
          int lo = 0;
          int hi = nums.size() - 1;
  
          while(lo <= hi) {
              int mid = (lo + hi) / 2;
              if(nums[mid] == target) return mid;
  
              // first half in order
              if(nums[lo] <= nums[mid]) {
                  // nums[lo] <= target < nums[mid]
                  if(nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                  else lo = mid + 1;
              // first half not in order
              } else {
                  // nums[mid] < target <= nums[hi]
                  if(nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                  else hi = mid - 1;
              }
          }
          return -1;
      }
  };
  

leetcode 81: 搜索旋转排序数组II

• 题意：旋转数组有重复

• 思路：与33题类似，但是需要额外考虑旋转点有重复，造成lo, mid, hi相等的情况。

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  class Solution {
  public:
      int search(vector<int>& nums, int target) {
          int lo = 0;
          int hi = nums.size() - 1;
  
          while(lo <= hi) {
              int mid = (lo + hi) / 2;
              if(nums[mid] == target) return true;
  
              // nums[lo] == nums[mid] == nums[hi]
              // [3 1 2 3 3 3 3]
              if(nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
                  lo++;
                  hi--;
              // first half in order
              } else if(nums[lo] <= nums[mid]) {
                  // nums[lo] <= target < nums[mid]
                  if(nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                  else lo = mid + 1;
              // first half not in order
              } else {
                  // nums[mid] < target <= nums[hi]
                  if(nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                  else hi = mid - 1;
              }
          }
          return false;
      }
  };
  

leetcode 34: 在排序数组中查找元素的第一个和最后一个位置

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  class Solution {
  public:
      vector<int> searchRange(vector<int>& nums, int target) {
          vector<int> notFound;
          notFound.push_back(-1);
          notFound.push_back(-1);
          if(nums.size() == 0) return notFound;
            
          int lo = binarySearch(nums, target);
          int hi = binarySearch(nums, target + 1);
          if(lo < nums.size() && nums[lo] == target) {
              vector<int> result;
              result.push_back(lo);
              result.push_back(hi - 1);
              return result;
          }    
          return notFound;
      }
        
  private:
      int binarySearch(vector<int>& nums, int target) {
          int lo = 0;
          int hi = nums.size() - 1;
          while(lo <= hi) {
              int mid = (lo + hi) / 2;
              if(nums[mid] < target) lo = mid + 1;
              else hi = mid - 1;
          }
          return lo;
      }
  };
  

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  class Solution {
  public:
      vector<int> searchRange(vector<int>& nums, int target) {
          vector<int> notFound;
          notFound.push_back(-1);
          notFound.push_back(-1);
          if(nums.size() == 0) return notFound;
            
          int lo = binarySearch(nums, target);
          int hi = binarySearchRight(nums, target);
          if(lo < nums.size() && nums[lo] == target) {
              vector<int> result;
              result.push_back(lo);
              result.push_back(hi - 1);
              return result;
          }    
          return notFound;
      }
        
  private:
      int binarySearch(vector<int>& nums, int target) {
          int lo = 0;
          int hi = nums.size() - 1;
          while(lo <= hi) {
              int mid = (lo + hi) / 2;
              if(nums[mid] < target) lo = mid + 1;
              else hi = mid - 1;
          }
          return lo;
      }
  
      int binarySearchRight(vector<int>& nums, int target) {
          int lo = 0;
          int hi = nums.size() - 1;
          while(lo <= hi) {
              int mid = (lo + hi) / 2;
              if(nums[mid] <= target) lo = mid + 1;
              else hi = mid - 1;
          }
          return lo;
      }
  };
  

leetcode 35: 搜索插入位置

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  class Solution {
  public:
      int searchInsert(vector<int>& nums, int target) {
          int lo = 0;
          int hi = nums.size() - 1;
          while(lo <= hi) {
              int mid = (lo + hi) / 2;
              if (nums[mid] < target) lo = mid+1;
              else hi = mid-1;
          }
          return lo;
      }
  };
  

leetcode 540: 有序数组中的单一元素

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  class Solution {
      public int singleNonDuplicate(int[] nums) {
          int lo = 0;
          int hi = nums.length - 1;
          while(lo <= hi) {
              int mid = (lo + hi) / 2;
              if(mid >= 1 && nums[mid-1] == nums[mid]) {
                  if((mid-2-lo+1) % 2 == 1) hi = mid - 2;
                  else lo = mid + 1;
              } else if(mid < nums.length-1 && nums[mid+1] == nums[mid]) {
                  if((mid-1-lo+1) % 2 == 1) hi = mid - 1;
                  else lo = mid + 2;
              } else {
                  return nums[mid];
              }
          }
          return -1;
      }
  }
  

leetcode 162: 寻找峰值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int lo = 0;
        int hi = nums.size() - 1;

        while(lo < hi) {
            int mid1 = (lo + hi) / 2;
            int mid2 = mid1 + 1;
            if(nums[mid1] < nums[mid2]) lo = mid2;
            else hi = mid1;
        }
        return lo;
    }
};

散列

leetcode 1: 两数之和

• 题意：在数组中寻找两数之和等于目标值。

• 思路：用一个散列表记录数组中的值和索引的关系。

• 时间：$O(n)$

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  class Solution {
  public:
      vector<int> twoSum(vector<int>& nums, int target) {
          vector<int> result(2);
          unordered_map<int, int> hash;
          for(int i = 0; i < nums.size(); i++) {
              if(hash.find(target - nums[i]) != hash.end()) {
                  result[0] = hash[target - nums[i]];
                  result[1] = i;
                  return result;
              }
              hash[nums[i]] = i;
          }
          return result;
      }
  };
  

leetcode 128: 最长连续序列

• 思路：对于每个数x，如果x-1不在集合里，就一直增长看最大能到多少。

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  class Solution {
  public:
      int longestConsecutive(vector<int>& nums) {
          unordered_set<int> set;
          for(int x: nums) {
              set.insert(x);
          }
  
          int res = 0;
          for(int x: nums) {
              if(!set.count(x-1)) {
                  int y = x + 1;
                  while(set.count(y)) {
                      y++;
                  }
                  res = max(res, y-x);
              }
          }
          return res;
      }
  };
  

leetcode 217: 存在重复元素

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> set;
        for(int num: nums) {
            if(set.count(num)) return true;
            set.insert(num);
        }
        return false;
    }
};

leetcode 242: 有效的字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()) return false;

        unordered_map<char, int> map;
        for(int i = 0; i < s.length(); i++) {
            if(!map.count(s[i])) map[s[i]] = 0;
            map[s[i]]++;
        }
        for(int i = 0; i < t.length(); i++) {
            if(!map.count(t[i])) return false;
            if(--map[t[i]] < 0) return false; 
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()) return false;
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

leetcode 347: 前 K 个高频元素

排序：$O(n \log n)$

先利用散列表统计次数，然后对值排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for(int num: nums) {
            if(!map.count(num)) map[num] = 0;
            map[num]++;
        }
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp);

        vector<int> res;
        for(int i = 0; i < k; i++) {
            res.push_back(vec[i].first);
        }
        return res;
    }

private:
    static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    }
};

桶排序：$O(n)$

先利用散列表统计次数，交换散列表的键和值，进行桶排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for(int num: nums) {
            if(!freq.count(num)) freq[num] = 0;
            freq[num]++;
        }

        unordered_map<int, vector<int>> bucket;
        for(unordered_map<int, int>::iterator it = freq.begin(); it != freq.end(); it++) {
            if(!bucket.count(it->second)) bucket[it->second] = vector<int>();
            bucket[it->second].push_back(it->first);
            // cout << it->second << ' ' << it->first << endl;
        }

        vector<int> res;
        for(int i = nums.size(); i > 0 && res.size() < k; i--) {
            if(bucket.count(i)) {
                for(int num: bucket[i]) {
                    res.push_back(num);
                    if(res.size() == k) break;
                }
            }
        }
        return res;
    }
};

leetcode 350: 两个数组的交集II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        for(int num: nums1) {
            if(!map.count(num)) map[num] = 0;
            map[num]++;
        }

        vector<int> res;
        for(int num: nums2) {
            if(map.count(num)) {
                res.push_back(num);
                if(--map[num] == 0) map.erase(num);
            }
        }
        return res;
    }
};

leetcode 380: 常数时间插入、删除和获取随机元素

散列+数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class RandomizedSet {
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
        
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(map.count(val)) return false;
        vec.push_back(val);
        map[val] = vec.size() - 1;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(!map.count(val)) return false;
        // notice case when val == last
        int last = vec.back();
        map[last] = map[val];
        vec[map[val]] = last;
        vec.pop_back();
        map.erase(val);
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        return vec[rand() % vec.size()];
    }

private:
    unordered_map<int, int> map;
    vector<int> vec;
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

974. 和可被 K 整除的子数组

思路：散列前缀数组mod K的结果。

数组

leetcode 41: 缺失的第一个正数

• 思路：扫描一遍尽量将每个数归位，然后再扫描一遍找出结果。

• 时间：$O(n)$

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  class Solution {
  public:
      int firstMissingPositive(vector<int>& nums) {
          int i = 1;
          while(i <= nums.size()) {
              // [1,1]
              while(nums[i-1] > 0 && nums[i-1] <= nums.size() && nums[i-1] != i && nums[i-1] != nums[nums[i-1]-1]) {
                  swap(nums[i-1], nums[nums[i-1]-1]);
              }
              i++;
          }
          for(i = 1; i <= nums.size(); i++) {
              if(nums[i-1] != i) break;
          }
          return i;
      }
  };
  

leetcode 45: 跳跃游戏II

• 方法一：动态规划

  • 时间$O(n^2)$，超时

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int jump(vector<int>& nums) {
            vector<int> dp(nums.size(), -1);
            dp[0] = 0;
            for(int i = 0; i < nums.size(); i++) {
                for(int j = i+1; j < nums.size() && j <= i+nums[i]; j++) {
                    if(dp[i] != -1) {
                        if(dp[j] == -1) dp[j] = dp[i] + 1;
                        else dp[j] = min(dp[i] + 1, dp[j]);
                    }
                }
            }
            return dp[nums.size()-1];
        }
    };
    

• 方法2：greedy

  • 时间：$O(n)$

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int jump(vector<int>& nums) {
            int jumps = 0;
            int curEnd = 0;
            int curFarthest = 0;
            for(int i = 0; i < nums.size()-1; i++) {
                curFarthest = max(curFarthest, i+nums[i]);
                if(i == curEnd) {
                    curEnd = curFarthest;
                    jumps++;
                }
            }
            return jumps;
        }
    };
    

leetcode 55: 跳跃游戏

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  class Solution {
  public:
      bool canJump(vector<int>& nums) {
          int reach = 0;
          int i = 0;
          for(; i < nums.size() && i <= reach; i++) {
              reach = max(reach, i+nums[i]);
          }
          return i == nums.size();
      }
  };
  

leetcode 48: 旋转图像

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  /*
  * clockwise rotate
  * first reverse up to down, then swap the symmetry 
  * 1 2 3     7 8 9     7 4 1
  * 4 5 6  => 4 5 6  => 8 5 2
  * 7 8 9     1 2 3     9 6 3
  */
  void rotate(vector<vector<int> > &matrix) {
      reverse(matrix.begin(), matrix.end());
      for (int i = 0; i < matrix.size(); ++i) {
          for (int j = i + 1; j < matrix[i].size(); ++j)
              swap(matrix[i][j], matrix[j][i]);
      }
  }
  
  /*
  * anticlockwise rotate
  * first reverse left to right, then swap the symmetry
  * 1 2 3     3 2 1     3 6 9
  * 4 5 6  => 6 5 4  => 2 5 8
  * 7 8 9     9 8 7     1 4 7
  */
  void anti_rotate(vector<vector<int> > &matrix) {
      for (auto vi : matrix) reverse(vi.begin(), vi.end());
      for (int i = 0; i < matrix.size(); ++i) {
          for (int j = i + 1; j < matrix[i].size(); ++j)
              swap(matrix[i][j], matrix[j][i]);
      }
  }
  

leetcode 56: 合并分区

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  class Solution {
  public:
      vector<vector<int>> merge(vector<vector<int>>& intervals) {
          vector<vector<int>> res;
          if(intervals.empty()) return res;
          sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b){return a[0] < b[0];});
          res.push_back(intervals[0]);
          for(int i = 1; i < intervals.size(); i++) {
              if(intervals[i][0] <= res.back()[1]) {
                  res.back()[1] = max(intervals[i][1], res.back()[1]);
              } else {
                  res.push_back(intervals[i]);
              }
          }
          return res;
      }
  };
  

leetcode 57: 插入区间

• 代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  class Solution {
  public:
      vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
          vector<vector<int>> res;
          int i = 0;
          while(i < intervals.size() && intervals[i][1] < newInterval[0]) {
              res.push_back(intervals[i++]);
          }
          while(i < intervals.size() && intervals[i][0] <= newInterval[1]) {
              // newInterval = vector<int>{
              //     min(newInterval[0], intervals[i][0]), 
              //     max(newInterval[1], intervals[i][1])};
              newInterval[0] = min(newInterval[0], intervals[i][0]);
              newInterval[1] = max(newInterval[1], intervals[i][1]);
              i++;
          }
          res.push_back(newInterval);
          while(i < intervals.size()) {
              res.push_back(intervals[i++]);
          }
          return res;
      }
  };