算法--常见算法例题总结

算法相关的Leetcode题解见：
CS-Notes/notes/Leetcode 题解 - 目录.md

1. 贪心思想

在对问题求解时，总是做出在当前看来是最好的选择。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
参考例题：452. 用最少数量的箭引爆气球

2. 二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，前提是数据结构必须先排好序，可以在数据规模的对数时间复杂度内（O(logn)）完成查找。但是，二分查找要求线性表具有有随机访问的特点（例如数组），也要求线性表能够根据中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果。
参考例题：153. 寻找旋转排序数组中的最小值

3. 分治算法

字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治算法通常以数学归纳法来验证。而它的计算成本则多数以解递归关系式来判定。
参考例题：241. 为运算表达式加括号

4. 搜索

4.1 广度优先搜索BFS

广度优先搜索一层一层地进行遍历，每层遍历都以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点。需要注意的是，遍历过的节点不能再次被遍历。
应该注意的是，使用 BFS 只能求解无权图的最短路径，无权图是指从一个节点到另一个节点的代价都记为 1。（有权图可以用动态规划）
当每一次都可以判断出多种情况，有多次的时候就适合用BFS，在程序实现 BFS 时需要考虑以下问题：

队列：用来存储每一轮遍历得到的节点；
标记：对于遍历过的节点，应该将它标记，防止重复遍历。

参考例题：279. 完全平方数(组成整数的最小平方数数量 )

4.2 深度优先遍历DFS

广度优先搜索一层一层遍历，每一层得到的所有新节点，要用队列存储起来以备下一层遍历的时候再遍历。而深度优先搜索在得到一个新节点时立即对新节点进行遍历。
从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种可达性问题。
在程序实现 DFS 时需要考虑以下问题：

栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。

参考例题：200. 岛屿数量(矩阵中的连通分量数目 )

4.3 回溯Backtracking

回溯属于DFS。

普通 DFS 主要用在可达性问题，这种问题只需要执行到特点的位置然后返回即可。
而 Backtracking 主要用于求解排列组合问题，例如有 { ‘a’,’b’,’c’ } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。

回溯算法事实上就是在一个树形问题上做深度优先遍历，因此首先需要把问题转换为树形问题。
因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：

在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

参考例题：
17. 电话号码的字母组合
 46. 全排列
 77. 组合
 78. 子集

5. 动态规划

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）等方式去解决。
一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的：

每个阶段只有一个状态（斐波那契数列问题）->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的（棋盘左上角到右下角问题）->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的（迷宫里的最短路径问题）->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

5.1 动态规划题目特点：

计数 -> 有多少种方式走到右下角
求最值 -> 最长上升子序列，零钱兑换（最少硬币个数）
求存在性 -> 能不能选出k个数使得和为sum

5.2 动态规四个组成部分

5.2.1 确定状态

定义dp数组，注意最后一步和子问题。其中最后一步是指最优策略中的最后一个决策，子问题是规模更小的最优子策略

5.2.2 转移方程

根据子问题定义得到

5.2.3 初始条件和边界情况

初始条件定义表示的是转移方程无法计算的初始值

5.2.4 计算顺序

不论从小到大还是从大到小，一个原则是转移方程计算时，等号右边的值必须是已经计算过的。

参考例题：
62. 不同路径的数量
 1143. 最长公共子序列
 416. 分割等和子集(0-1背包问题)
309. 最佳买卖股票时机含冷冻期

6. 数学相关

6.1 素数（质数）

一个数只能被1或它本身整除就是质数，否则就是合数。
参考例题：204. 计数质数

6.2 最大公约数，最小公倍数

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
//最小公倍数为两数的乘积除以最大公约数。
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

6.3 进制转换

注意处理负数和零的情况。
参考例题：
405. 数字转换为十六进制数(栈)
405. 数字转换为十六进制数(转成无符号整型unsigned int处理)

6.4 阶乘

参考例题：
172. 阶乘后的零
如果统计的是 N! 的二进制表示中最低位 1 的位置，也是同样的道理，只要统计有多少个 2 即可。

6.5 字符串加减法

参考例题：
67. 二进制字符串求和

6.6 相遇问题，多数投票问题

找中位数！
参考例题：
462. 最少移动次数使数组元素相等 II

6.7 其他

6.7.1 平方数

平方序列：1,4,9,16,..
间隔：3,5,7,…
间隔为等差数列，使用这个特性可以得到从 1 开始的平方序列。
参考例题：367. 有效的完全平方数

6.7.2 乘积数组

参考例题：238. 除自身以外数组的乘积(乘积数组)

6.7.3 二项式定理+快速幂

阿里2.23笔试题第一道：N个人，任意选k个，再从k个里任选1个当队长，不同的队长算不同的组合,求总组合数。
思路：

参考链接：阿里笔试讨论（3.23场)（附两道题AC的方法或代码）

总数S = 0*C(N,0) + 1*C(N,1) + … + i*C(N,i) + N*C(N,N)
倒着加，由二项式定理：S + S = N*(C(N,0) + … + C(N,N)) = N*2^(N)
所以 S = N*2^(N-1)
接下来只需要考虑计算2^(N-1)的快速计算方法就好了（简单2分递归即可）
时间复杂度O(logN)。
代码实现：

//递归快速求幂
int MyPow(int m, int n) {  //m^n
    if (n == 1) return m;
    int temp = MyPow(m, n / 2);
    return (long long)(n%2==0 ? 1 : m) * temp * temp % 1000000007;  //n为奇数时，需要额外乘m
}
int main() {
    int n;
    while (cin >> n) {
        int res = 0;
        res = (long long)n * MyPow(2, n - 1) % 1000000007;
        cout << res << endl;
    }
    return 0;
}

// n比较小时可以这么算，n比较大时，递归过深会导致栈溢出，此时应使用二项式公式+快速幂的方式
// 由n个人里选k个人的组合数 = 由n-1个人里选k个人的组合数 + 由n-1个人里选k-1个人的组合数
int Comm(int n, int k) {
    if (k > n)
        return 0;
    else if (n == k || k == 0)
        return 1;
    else return Comm(n - 1, k) + Comm(n - 1, k - 1);
}
int main() {
    int n;
    while (cin >> n) {
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res += i * (Comm(n, i));
        }
        cout << res << endl;
    }
    return 0;
}