1、二分查找
二分查找思想简单，但是在实现时有一些需要注意的细节：
1、在计算 mid 时不能使用 mid = (l + h) / 2 这种方式，因为 l + h 可能会导致加法溢出，应该使用 mid = l + (h - l) / 2。
2、对 h 的赋值和循环条件有关，当循环条件为 l <= h 时，h = mid - 1；当循环条件为 l < h 时，h = mid。解释如下：在循环条件为 l <= h 时，如果 h = mid，会出现循环无法退出的情况，例如 l = 1，h = 1，此时 mid 也等于 1，如果此时继续执行 h = mid，那么就会无限循环；在循环条件为 l < h，如果 h = mid - 1，会错误跳过查找的数，例如对于数组 [1,2,3]，要查找 1，最开始 l = 0，h = 2，mid = 1，判断 key < arr[mid] 执行 h = mid - 1 = 0，此时循环退出，直接把查找的数跳过了。
3、l 的赋值一般都为 l = mid + 1。
public int search(int key, int[] arr) {
int l=0, h=arr.length-1;
while(l<=h) {
int mid=l+(h-l)/2;
if(key==arr[mid]) return mid;
if(key<arr[mid]) h=mid-1;
else l=mid+1;
}
return-1;
}
求开方
一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt 。可以利用二分查找在 0 ~ x 之间查找 sqrt。
摆硬币
题目描述：第 i 行摆 i 个，统计能够摆的行数。
返回 h 而不是 l，因为摆的硬币最后一行不能算进去。
有序数组的 Single Element
题目描述：一个有序数组只有一个数不出现两次，找出这个数。
2、贪心思想
贪心思想保证每次操作都是局部最优的，并且最后得到的结果是全局最优的。
分配饼干
Leetcode : 455. Assign Cookies (Easy)
题目描述：每个孩子都有一个满足度，每个饼干都有一个大小，只有饼干的大小大于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。
因为最小的孩子最容易得到满足，因此先满足最小孩子。给一个孩子的饼干应当尽量小又能满足该孩子，这样大饼干就能拿来给满足度比较大的孩子。
证明：假设在某次选择中，贪心策略选择给第 i 个孩子分配第 m 个饼干，并且第 i 个孩子满足度最小，第 m 个饼干为可以满足第 i 个孩子的最小饼干，利用贪心策略最终可以满足 k 个孩子。假设最优策略在这次选择中给 i 个孩子分配第 n 个饼干，并且这个饼干大于第 m 个饼干。我们发现使用第 m 个饼干去替代第 n 个饼干完全不影响后续的结果，因此不存在比贪心策略更优的策略，即贪心策略就是最优策略。
判断是否为子串
分隔字符串使同种字符出现在一起
3、双指针
双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。
从一个已经排序的数组中查找出两个数，使它们的和为 0
使用双指针，一个指针指向元素较小的值，一个指针指向元素较大的值。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
如果两个指针指向元素的和 sum == target，那么得到要求的结果；如果 sum > target，移动较大的元素，使 sum 变小一些；如果 sum < target，移动较小的元素，使 sum 变大一些。
4、排序
快速选择
一般用于求解 Kth Element 问题，可以在 O(n) 时间复杂度，O(1) 空间复杂度完成求解工作。
与快速排序一样，快速选择一般需要先打乱数组，否则最坏情况下时间复杂度为 O(n2)。
堆排序
堆排序用于求解 TopK Elements 问题，通过维护一个大小为 K 的堆，堆中的元素就是 TopK Elements。当然它也可以用于求解 Kth Element 问题，因为最后出堆的那个元素就是 Kth Element。快速选择也可以求解 TopK Elements 问题，因为找到 Kth Element 之后，再遍历一次数组，所有小于等于 Kth Element 的元素都是 TopK Elements。可以看到，快速选择和堆排序都可以求解 Kth Element 和 TopK Elements 问题。
桶排序
找出出现频率最多的 k 个数（频率为0的，频率为1的，...）
5、搜索
（1）BFS
广度优先搜索的搜索过程有点像一层一层地进行遍历：从节点 0 出发，遍历到 6、2、1 和 5 这四个新节点。
继续从 6 开始遍历，得到节点 4 ；从 2 开始遍历，没有下一个节点；从 1 开始遍历，没有下一个节点；从 5 开始遍历，得到 3 和 4 节点。这一轮总共得到两个新节点：4 和 3 。
反复从新节点出发进行上述的遍历操作。
可以看到，每一轮遍历的节点都与根节点路径长度相同。设 di 表示第 i 个节点与根节点的路径长度，推导出一个结论：对于先遍历的节点 i 与后遍历的节点 j，有 di<=dj。利用这个结论，可以求解最短路径 最优解 问题：第一次遍历到目的节点，其所经过的路径为最短路径，如果继续遍历，之后再遍历到目的节点，所经过的路径就不是最短路径。
在程序实现 BFS 时需要考虑以下问题：
队列：用来存储每一轮遍历的节点
标记：对于遍历过得节点，应该将它标记，防止重复遍历；
计算在网格中从原点到特定点的最短路径长度
[[1,1,0,1],
[1,0,1,0],
[1,1,1,1],
[1,0,1,1]]
（2）DFS
广度优先搜索一层一层遍历，每一层遍历到的所有新节点，要用队列先存储起来以备下一层遍历的时候再遍历；而深度优先搜索在遍历到一个新节点时立马对新节点进行遍历：从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。
从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种 可达性 问题。
在程序实现 DFS 时需要考虑以下问题：
栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。也可以使用递归栈。
标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。
查找最大的连通面积
输出二叉树中所有从根到叶子的路径
（3）回溯
回溯是 DFS 的一种，它不是用在遍历图的节点上，而是用于求解 排列组合 问题，例如有 { 'a','b','c' } 三个字符，求解所有由这三个字符排列得到的字符串。
在程序实现时，回溯需要注意对元素进行标记的问题。使用递归实现的回溯，在访问一个新元素进入新的递归调用，此时需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；但是在递归返回时，需要将该元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，而在不同的递归链是可以访问已经访问过但是不在当前递归链中的元素。
在矩阵中寻找字符串
IP地址划分
6、分治
动态规划
递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解。
（1）分割整数
分割整数构成字母字符串
（2）矩阵路径
（3）斐波那契数列
爬楼梯
（4）最长递增子序列、最长公共子序列
（5）0-1背包(无法使用贪心算法)
有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。
定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示体积不超过 j 的情况下，前 i 件物品能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：
① 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。
② 第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。
第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。
因此：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
空间优化:在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅由前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，d[j] = max(dp[j], dp[j-w]+v)
划分数组为和相等的两部分（注意从后往前动态规划）
找零钱
（6）数组区间
数学
（1）素数
素数分解
每一个数都可以分解成素数的乘积
整除
令 x = 2^m0 * 3^m1 * 5^m2 * 7^m3 * 11^m4 * …令 y = 2^n0 * 3^n1 * 5^n2 * 7^n3 * 11^n4 * …
如果 x 整除 y（y mod x == 0），则对于所有 i，mi <= ni。
x 和 y 的 最大公约数 为：gcd(x,y) = 2^min(m0,n0) * 3^min(m1,n1) * 5^min(m2,n2) * ...
x 和 y 的 最小公倍数 为：lcm(x,y) = 2^max(m0,n0) * 3^max(m1,n1) * 5^max(m2,n2) * ...
（2）最大公约数
最小公倍数为两数的乘积除以最大公约数。
对于 a 和 b 的最大公约数 f(a, b)，有：
1. 如果 a 和 b 均为偶数，f(a, b) = 2*f(a/2, b/2);2. 如果 a 是偶数 b 是奇数，f(a, b) = f(a/2, b);3. 如果 b 是偶数 a 是奇数，f(a, b) = f(a, b/2);4. 如果 a 和 b 均为奇数，f(a, b) = f(a, a-b);
乘 2 和除 2 都可以转换为移位操作。
（3）进制转换
（4）阶乘
（5）字符串加法减法
二进制加法
字符串加法
（6）相遇问题
移动数组元素使所有的数组元素都相等
题目描述：每次可以对一个数组元素加一或者减一，求最小的改变次数。
这是个典型的相遇问题，移动距离最小的方式是所有元素都移动到中位数。理由如下：
设 m 为中位数。a 和 b 是 m 两边的两个元素，且 b > a。要使 a 和 b 相等，它们总共移动的次数为 b - a，这个值等于 (b - m) + (m - a)，也就是把这两个数移动到中位数的移动次数。
设数组长度为 N，则可以找到 N/2 对 a 和 b 的组合，使它们都移动到 m 的位置。
利用快速排序找到中位数：首先确立基准值privot=nums[(l+r)/2]，然后分别从数组的左-右、右-左遍历数组，分别找到比privot大/小的值nums[l]、nums[r]，交换这两个值。到l>r时停止，接着分别对大于privot的右半部分和小于privot的左半部分做递归。
数据结构相关
（1）栈和队列
用栈实现队列
用队列实现栈
最小值栈(用两个栈实现，一个存储数据，一个存储最小值)
（2）哈希表
利用 Hash Table 可以快速查找一个元素是否存在等问题，但是需要一定的空间来存储。在优先考虑时间复杂度的情况下，可以利用 Hash Table 这种空间换取时间的做法。
（3）字符串
两个字符串包含的字符是否完全相同——记录每个字符串出现的次数
判断一个整数是否是回文数
字符串中单词的翻转
（4）数组与矩阵
（5）链表
判断两个链表的交点——从后往前访问两个链表
链表反转——头插法，获取最后一个节点并赋值给new，temp为head，tmp为head->next，赋temp->next为new->next，new->next为temp。循环。
归并两个有序的链表——递归
（6）树
递归
一棵树要么是空树，要么有两个指针，每个指针指向一棵树。树是一种递归结构，很多树的问题可以使用递归来处理。
树的高度 递归计算每个节点的高度（左右子树高度取最大值+1）
翻转树——返回子节点的翻转后的节点
归并两棵树
最近公共祖先（二叉搜索树、普通二叉树）
层次遍历
使用 BFS，不需要使用两个队列来分别存储当前层的节点和下一层的节点， 因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。
计算一棵树每层节点的平均数
前中后序遍历
① 前序
void dfs(TreeNoderoot){
visit(root);
dfs(root.left);
dfs(root.right);}
② 中序
void dfs(TreeNoderoot){
dfs(root.left);
visit(root);
dfs(root.right);}
③ 后序
void dfs(TreeNoderoot){
dfs(root.left);
dfs(root.right);
visit(root);}
BST（二叉搜索树）
主要利用 BST 中序遍历有序的特点。
在BST中寻找两个节点，使它们的和成为一个给定值。
Trie（前缀树、字典树）用于判断字符串是否存在或者是否具有某种字符串前缀
（7）图的位运算
1. 基本原理
0s 表示 一串 0 ，1s 表示一串 1。
x ^0s= x x &0s=0x |0s= x
x ^1s= \~x x &1s= x x |1s=1s
x ^ x =0x & x = x x | x = x
① 利用 x ^ 1s = ~x 的特点，可以将位级表示翻转；利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数；② 利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。一个数 num 与 mask ：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位；③ 利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设置操作。一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1 。
>> n 为算术右移，相当于除以 2n；>>> n 为无符号右移，左边会补上 0。<< n 为算术左移，相当于乘以 2n。
n&(n-1) 该位运算是去除 n 的位级表示中最低的那一位。例如对于二进制表示 10110100，减去 1 得到 10110011，这两个数相与得到 10110000。
n-n&(~n+1) 概运算是去除 n 的位级表示中最高的那一位。
n&(-n) 该运算得到 n 的位级表示中最低的那一位。-n 得到 n 的反码加 1，对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100
2. mask 计算
3. 位操作举例
① 获取第 i 位
num & 00010000 != 0
(num&(1<<i))!=0;
② 将第 i 位设置为 1
num | 00010000
num|(1<<i);
③ 将第 i 位清除为 0
num & 11101111
num&(\~(1<<i))
④ 将最高位到第 i 位清除为 0
num & 00001111
num&((1<<i)-1);
⑤ 将第 0 位到第 i 位清除为 0
num & 11110000
num&(\~((1<<(i+1))-1));
⑥ 将第 i 位设置为 0 或者 1
先将第 i 位清零，然后将 v 左移 i 位，执行“位或”运算。
(num&(1<<i))|(v<<i);
