• 穷举
  • 无遗漏
  • 无冗余
  • 如何穷举
  • 如何聪明穷举

  • 技巧大概就是，把大的问题细化到一个点，先研究在这个小的点上如何解决问题，然后再通过递归/迭代的方式扩展到整个问题

    排序

  • 归并、快排都使用了分治的思想

  • 稳定的排序算法：冒泡、插入、归并、计数、桶、基数
  • 不稳定：选择、希尔、快速、堆

image.png

快速排序

  • 什么时候最差（退化成冒泡排序）

    • 已排序
    • 数值全部相等（1的特殊情况）
      1. void quickSort

      加密算法

      区别：
      1、对称加密中加密和解密使用的秘钥是同一个；非对称加密中采用两个密钥，一般使用公钥进行加密，私钥进行解密
      2、对称加密解密的速度比较快，非对称加密和解密花费的时间长、速度相对较慢
      3、对称加密的安全性相对较低，非对称加密的安全性较高。

      非对称加密算法

  • RSA

  • DSA
  • ECDSA
  • ECC
  • DH
  • DSS

  • ELGamal

    对称加密算法

  • AES

  • DES

  • 3DES

    国密算法

    即国家商用密码算法。是由国家密码管理局认定和公布的密码算法标准及其应用规范，其中部分密码算法已经成为国际标准。如SM系列密码

    贪心算法

    一般用来求最值
    需要满足贪心选择性质: 局部最优—>全局最优
    这就是贪心思路的本质，如果找不到重复计算，那就通过问题中一些隐藏较深的规律，来减少冗余计算。
    一般找规律
    要有贪心选择性质

    动态规划

  • 问题性质

    • 具备最优子结构
      • 一个问题的最优解可以由其子问题的最优解有效地构造出来
    • 存在重叠子问题
      • 果一个问题可以被分解成若干个子问题，且这些子问题会重复出现
    • 一般用来求最值

  • 正确的状态转移方程（问题不同规模的关系）
  • 解法
    • 明确base case -> 明确状态 -> 明确选择 -> 定义dp数组/函数
    • 遍历顺序应该是以base case 为起点向结果靠近
  • 最后一步优化，如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试缩小 DP table 的大小，只记录必要的数据，从而降低空间复杂度
  • 状态是什么？在问题分解（状态转移）的过程中变化的，就是状态。变化量
  • 动态规划算法本质上就是穷举「状态」，然后在「选择」中选择最优解。
  • 选择, 也就是导致状态产生变化的行为
  • 一般用到数学归纳法
  • 根据 dp 数组的定义，运用数学归纳法的思想，假设 dp[0…i-1] 都已知，想办法求出 dp[i]，一旦这一步完成，整个题目基本就解决了。
  • 但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组
  • 1、遍历的过程中，所需的状态必须是已经计算出来的。
  • 2、遍历结束后，存储结果的那个位置必须已经被计算出来。

image.png

数组技巧

前缀和

前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。
前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和
image.png

差分数组

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减
image.png

递归

不要跳进递归，而是利用明确的定义来实现算法逻辑

1、这个函数是干嘛的？
2、这个函数参数中的变量是什么的是什么？
3、得到函数的递归结果，你应该干什么？

当数据结构和算法是递归时,适合使用
写递归算法的一个技巧就是不要试图跳进递归细节，而是从递归框架上思考，从函数定义去理解递归函数到底该怎么实现
PS：但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。
递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。

双指针

链表, 数组 字符串, 回文串,常用

快慢双指针,首尾双指针,滑动窗口等等,image.png

滑动窗口

子串/子数组问题

二分

对于有单调性的可以二分

回溯

怎么做选择
解决一个回溯问题，实际上就是一个决策树的遍历过程

站在回溯树的一个节点上，你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。

defbacktrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return//相当于多叉树的遍历，i的个数从2变成了n，并且写成了for循环的形式
for 选择 in 选择列表:
路径.add(选择)
backtrack(路径, 选择列表) //将数值改回成原来的状态 路径.remove(选择)

我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。image.png

BFS

  1. // 计算从起点 start 到终点 target 的最近距离
  2. int BFS(Node start, Node target) {
  3.     Queue<Node> q; // 核心数据结构
  4.     Set<Node> visited; // 避免走回头路
  6.     q.offer(start); // 将起点加入队列
  7.     visited.add(start);
  8.     int step = 0; // 记录扩散的步数
  10.     while (q not empty) {
  11.         int sz = q.size();
  12.         /* 将当前队列中的所有节点向四周扩散 */
  13.         for (int i = 0; i < sz; i++) {
  14.             Node cur = q.poll();
  15.             /* 划重点：这里判断是否到达终点 */
  16.             if (cur is target)
  17.                 return step;
  18.             /* 将 cur 的相邻节点加入队列 */
  19.             for (Node x : cur.adj()) {
  20.                 if (x not in visited) {
  21.                     q.offer(x);
  22.                     visited.add(x);
  23.                 }
  24.             }
  25.         }
  26.         /* 划重点：更新步数在这里 */
  27.         step++;
  28.     }
  29. }

位运算

利用或操作 | 和空格将英文字符转换为小写
利用与操作 & 和下划线将英文字符转换为大写
利用异或操作 ^ 和空格进行英文字符大小写互换

判断两个数是否异号

  1. int x =-1, y =2;boolean f =((x ^ y)<0);// true

不用临时变量交换两个数

  1.     int a = 1, b = 2;
  2.     a ^= b;
  3.     b ^= a;
  4.     a ^= b;

加一

  1.     int n = 1;
  2.     n = -~n;

减一

  1.     int n = 1;
  2.     n = ~-n;

n & (n-1) 这个操作是算法中常见的，作用是消除数字 n 的二进制表示中的最后一个 1
一个数和它本身做异或运算结果为 0，即 a ^ a = 0；一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a。异或运算满足交换律和结合律

i = i & (i-1)，统计i二进制中有多少个1
i = i | (i+1)，统计i二进制中有多少个0

并查集

顾名思义，并查集是来解决图的连通性问题

  • Union — 连接两个节点

  • Find — 查找所属的连通分量 ```cpp class UnionFind { private:

    1.   vector<int> parents;
    2.   vector<int> rank;

    public:

    1.   int unionCount = 0;
    2.   UnionFind(vector<vector<int>>& isConnected) {
    3.       int n = isConnected.size();
    4.       parents.resize(n);
    5.       rank.resize(n, 0);
    6.       for (int i = 0; i < n; ++i) {
    7.           parents[i] = i;
    8.       }
    9.   }
    11.   void _union(int x, int y) {
    12.       int rootX = find(x);
    13.       int rootY = find(y);
    15.       if (rootX != rootY) {
    16.           if (rank[rootX] > rank[rootY]) {
    17.               parents[rootY] = rootX;
    18.           } else if (rank[rootX] < rank[rootY]) {
    19.               parents[rootX] = rootY;
    20.           } else {
    21.               parents[rootY] = rootX;
    22.               rank[rootX] += 1;
    23.           }
    24.           ++unionCount;
    25.       }
    26.   }
    28.   int find(int x) {
    29.       if (parents[x] == x) {
    30.           return x;
    31.       }
    32.       int p = parents[x];
    33.       parents[x] = find(p);
    34.       return parents[x];
    35.   }

    };

// 按照大小的 class UnionFind { private: vector parents; vector size;

  1. public:
  2.     int ans = 0;
  4.     UnionFind(vector<vector<int>>& grid) {
  5.         int m = grid.size();
  6.         int n = grid[0].size();
  7.         parents.resize(m * n);
  8.         size.resize(m * n);
  10.         for (int i = 0; i < m; ++i) {
  11.             for (int j = 0; j < n; ++j) {
  12.                 if (grid[i][j] == 1) {
  13.                     int k = i * n + j;
  14.                     parents[k] = k;
  15.                     size[k] = 1;
  16.                     if (ans != 1) {
  17.                         ans = 1;
  18.                     }
  19.                 }
  20.             }
  21.         }
  22.     }
  24.     void _union(int x, int y) {
  25.         int xRoot = find(x);
  26.         int yRoot = find(y);
  28.         if (xRoot != yRoot) {
  29.             if (size[yRoot] <= size[xRoot]) {
  30.                 parents[yRoot] = xRoot;
  31.                 size[xRoot] += size[yRoot];
  32.                 ans = max(size[xRoot], ans);
  33.             } else {
  34.                 parents[xRoot] = yRoot;
  35.                 size[yRoot] += size[xRoot];
  36.                 ans = max(size[yRoot], ans);
  37.             }
  38.         }
  39.     }
  41.     // 带压缩路径的查找
  42.     int find(int x) {
  43.         if (x == parents[x]) {
  44.             return x;
  45.         }
  46.         int p = parents[x];
  47.         parents[x] = find(p);
  48.         return parents[x];
  49.     }

};

  1. ```java
  2. class UnionFind{
  3.     private int[] parent;
  4.     private int[] rank; // 实际代码中，按秩求并和按大小求并选择其中一种即可
  5.     private int[] size; // 实际代码中，按秩求并和按大小求并选择其中一种即可
  7.     public UnionFind(int[] parent) {
  8.         this.parent = parent;
  9.         this.rank = new int[parent.length];
  10.         this.size = new int[parent.length];
  11.         for (int i = 0; i < parent.length; i++) {
  12.             this.rank[i] = 1;
  13.             this.size[i] = 1;
  14.         }
  15.     }
  17.     // 直接求并
  18.     public void unionDirect(int x, int y) {
  19.         if(find(x) != find(y)){
  20.             parent[find(y)] = find(x);
  21.         }
  22.     }
  24.     // 按大小求并
  25.     public void unionBySize(int x, int y){
  26.         int xRoot = find(x), yRoot = find(y);
  28.         if(xRoot != yRoot) { // 根节点不同才求并
  29.             if(size[yRoot] <= size[xRoot]){
  30.                 parent[yRoot] = xRoot;
  31.                 size[xRoot] += size[yRoot];
  32.             } else {
  33.                 parent[xRoot] = yRoot;
  34.                 size[yRoot] += size[xRoot];
  35.             }
  36.         }
  37.     }
  39.     // 按秩求并
  40.     public void union(int x, int y){
  41.         int xRoot = find(x), yRoot = find(y);
  42.         if( xRoot != yRoot){
  43.             if(rank[yRoot] <= rank[xRoot]) parent[yRoot] = xRoot;
  44.             else parent[xRoot] = yRoot;
  45.             if(rank[xRoot] == rank[yRoot]) rank[xRoot]++; 
  46.         }
  47.     }
  49.     // 直接查找
  50.     public int findDirect(int x) {
  51.         if(parent[x] == x) return x;
  52.         return findDirect(parent[x]);  
  53.     }
  55.     // 带路径压缩的查找
  56.     public int find(int x) {
  57.         if(parent[x] == x) return x;
  58.         return parent[x] = find(parent[x]); 
  59.     }
  60. }
  1. class UnionFind2{
  2.     private int[] parent;
  4.     public UnionFind2(int[] parent) {
  5.         this.parent = parent;
  6.     }
  8.     // 直接求并
  9.     public void unionDirect(int x, int y) {
  10.         if(find(x) != find(y)){
  11.             parent[find(y)] = find(x);
  12.         }
  13.     }
  15.     // 按大小求并
  16.     public void unionBySize(int x, int y){
  17.         int xRoot = find(x), yRoot = find(y);
  19.         if(xRoot != yRoot) { // 根节点不同才求并
  20.             if(parent[xRoot] <= parent[yRoot]){ // 负数比较，较小者树较大
  21.                 parent[xRoot] += parent[yRoot];
  22.                 parent[yRoot] = xRoot;
  23.             } else {
  24.                 parent[yRoot] += parent[xRoot];
  25.                 parent[xRoot] = yRoot;
  26.             }
  27.         }
  28.     }
  30.     // 按秩求并
  31.     public void union(int x, int y){
  32.         int xRoot = find(x), yRoot = find(y);
  33.         if(xRoot != yRoot) {
  34.             if(parent[xRoot] <= parent[yRoot]){
  35.                 parent[yRoot] = xRoot;
  36.             } else {
  37.                 parent[xRoot] = yRoot;
  38.             }
  39.             // 当两棵树秩相等根节点不同时，新树的高度增高1（负数表示，减1）
  40.             if(parent[xRoot] == parent[yRoot]){
  41.                 parent[xRoot]--; 
  42.             }
  43.         }
  44.     }
  46.     // 直接查找
  47.     public int findDirect(int x) {
  48.         if(parent[x] < 0) return x; // 只有代表元满足 parent[x] < 0
  49.         return findDirect(parent[x]); 
  50.     }
  52.     // 带路径压缩的查找
  53.     public int find(int x) {
  54.         if(parent[x] < 0) return x;
  55.         return parent[x] = find(parent[x]; 
  56.     }
  57. }

数学

(a b) % k = (a % k) (b % k) % k
换句话说，对乘法的结果求模，等价于先对每个因子都求模，然后对因子相乘的结果再求模。
求质数只要求到sqrt(n)

  1. int mypow(int a, int k)
  2. {
  3.     if (k == 0)
  4.         return 1;
  5.     if (k % 2 == 1)
  6.     {
  7.         return (a * mypow(a, k - 1));
  8.     }
  9.     else
  10.     {   
  11.         int sub = mypow(a, k / 2);
  12.         return sub * sub;
  13.     }
  14. }

概率::
原则一、计算概率一定要有一个参照系，称作「样本空间」，即随机事件可能出现的所有结果。事件 A 发生的概率 = A 包含的样本点 / 样本空间的样本总数。
原则二、计算概率一定要明白，概率是一个连续的整体，不可以把连续的概率分割开，也就是所谓的条件概率。
https://labuladong.gitee.io/algo/4/30/121/

十进制—>n进制 除基取余法

n —> 十直接转换

tips

注意数据的范围

使用合理的数据类型, 防止溢出和下表越界
4.11 微众银行实习岗血的教训
C++ longlong
java biginteger 或者直接python

a + b == c 时可以写成 a==c-b，防止溢出

需要多次扩容的话,可以在第一次多分配点空间来降低之后的时间消耗
image.png
位运算 >> 1 ： 除二
<<1 ：乘二
l +（r -L）/ 2防溢出

注意边界: 确定每个变量的定义和区间的开闭情况

O(nlogn)想到排序

画图

恰好可能有猫腻

对于这种数组问题，关键点在于元素和索引是成对儿出现的，常用的方法是排序、异或、映射。

PS：向上取整是一个常用的算法技巧。大部分编程语言中，如果你想计算 M 除以 N，M / N 会向下取整，你想向上取整的话，可以改成 (M+(N-1)) / N。

不会写的可以找找规律

对于一些比较困难的问题，其解法并不是一蹴而就的，而是步步推进，螺旋上升的
退而求其次是一种很聪明策略。
多次用到的信息可以存起来

x+=y; y=x-y; x-=y;可以交换数据

有序的

需要最值或者一些动态的时候
一般是二叉堆构建的优先队列
或是二叉搜索树，比如set这种