LeetCodeNote

立志欲坚不欲锐，成功在久不在速

leetcode

原地算法基本就是：双指针加反转。

数组

二维数组用的时候不能直接push_back()一个元素，要往某一维上push一个元素先要往这个二维数组里push一个一维数组，like this:
ret.push_back(vector <int> ());
或者先建立一维数组来存放值，再push进二维数组。
或者动态resize二维数组的大小。

n数之和

经典题，用哈希表会非常难写，虽然也可以做到O(n^2)的时间复杂度，但是很难去重。

这题比较好的解法是排序加双指针，排序后的双指针非常好用。

912 排序数组

经典排序题

复习基础排序算法
这篇题解写的非常好，将排序算法讲的很通透。

二分查找

来一波二分查找的总结吧。

二分查找有两种题（目前做到的）
第一种：你的目标一定存在，你一定能找到唯一一个数符合你的目标，比如374. 猜数字大小 这种题随便写，可以用我后面重点说的通用解法，也可以用在循环里分(<、>、 ==)三种情况，都很好些。
第二种题：你的目标不一定存在，你可能要找你的理论目标最近的一个数，可能是 小于等于target的最大数 或 大于等于target的最小数。比如35. 搜索插入位置、278. 第一个错误的版本、 69. x 的平方根、（注：这种平方题可以用二分迭代法做）367. 有效的完全平方数 等都是要找离目标最近的数，并且大多数不止要让你返回 true or false，还要你返回索引。

接下来重点介绍通用二分模板：
以367. 有效的完全平方数 为例：

long low = 0, high = 1<<16, mid = 0;
while(low<high) {
    mid = (high-low)/2+low;
    if(mid*mid>=num) high = mid;
    else if(mid*mid<num) low = mid+1;
}
return high*high==num;

首先，用 mid=(low+high)/2 可以，但是用 (low-high)/2+low 更好（这俩是一模一样的），因为 (low+high) 可能超出 int 的范围。

其次，用 while(low<high) 更好。根据这里我们可以找第一个平方大于等于目标数的数（当然也可以找最后一个平方小于等于目标数的数），并且注意到(mid*mid>=num) high = mid 也就是说high始终有可能就是第一个平方大于等于目标数的数，而(mid*mid<num)是mid很明显不是我们想要的，所以我们让low = mid+1，能不能让low=mid也不动，绝对不行！因为这里的mid已经确定不符合题意，一定要有一个逼近的过程，即使逼近程度只有1，否则等low high很接近的时候一定会死循环。
这样有什么好处？我的目标就是，始终让第一个平方大于等于目标数的数就在[low,high]中间，这里是闭区间，那么当low==high的时候左右两区间重合就可以自动退出循环，并且low or high就是我们想要的，后续所有的判断都可以根据这两个数来。这里又体现一个好处，退出循环的时候一定是low==high（因为两个数加起来一次循环也只会变化1），如果用的是 while(low<=high)退出的时候还要去想诶，到底low or high or mid哪个是有价值的数据，很折磨的。

还有一个很重要的问题，如果我找最后一个平方小于等于目标数的数，是不是只需要修改以下两个关键语句就可以呢？

错误！为什么？
细想，当low high 只差1的时候，mid是不是恒等于low，如果此时的low*low<=num是不是死循环了，high还没判断呢，万一high才是最后一个平方小于等于目标数的数呢。
所以关键就是：low可能不动，所以要让mid去等于high（当然是low high 只差1的情况），也就是

while(low<high) {
    mid = (high-low+1)/2+low;
    if(mid*mid>num) high = mid-1;
    else if(mid*mid<=num) low = mid;
}

总结下来：low和high中一个不动，mid的结果一定要等于另一个，不然low high相邻的时候就会死循环。

目前来看，所有二分查找都可以用这个模板，灵活变通吧。

多数元素

169. 多数元素
被简单题薄纱(加进阶是真难)
这题有很多解法：随机化（第一次见这种抽象解法）、分治、Boyer-Moore 投票算法

分治的关键在于：将数组分成两个子数组之后，数组的主要元素一定是两个子数组主要元素之中的一个，因为如果数组的主要元素不是两个子数组主要元素之一，那这个主要元素出现次数一定小于数组一半(反证法)。
分治法还要考虑到最小子问题才能成型，也就是长度为1的数组的主要元素就是其中唯一的数。
分支法还能解决问题：数组中出现次数最多的数字，不会受到题目中的限制（超过半数）。
merge过程中都是要再遍历一次数组的，两个子问题加上n，总的时间复杂度就是O(nlgn)。

Boyer-Moore 投票算法：同归于尽消杀法

448. 找到所有数组中消失的数字

448. 找到所有数组中消失的数字
利用数组当哈希表（原地），巧妙利用数据的宽度，结合取模在保有原数据信息的同时加入了新的信息。

数学

计数质数

埃氏筛

位运算

位运算很重要，有些题很有技巧性

注意观察规律，A 到 Z 的低六位是 1 到 26，也就是 000001 到 011010。
而 a 到 z 的 低六位 是 33 到 58，也就是 100001 到 111010。
相差刚好是 倒数第六位的二进制 1 ，也就是 32（97-65），应该ascii码就是这么设计的，这样的话 (A |= 1<<5)==a，| 运算在这里等效于加法。
并且 A 到 Z 、a 到 z 的 低六位各不一样，分布在 1 到 64内，可以直接用 一个64bit 的long型整数压缩存储A 到 Z 、a 到 z，如：771. 宝石与石头

char ch;
long mask = 1 << (ch&63);

这样每个 A 到 Z 、a 到 z 都可以用 mask 的 1 bit 来存储。
上面提到的两种用法都是在题里面见到过的。

只出现一次的数字

只出现一次的数字

对于这道题，可使用异或运算 ^。异或运算有以下三个性质。
任何数和 0 做异或运算，结果仍然是原来的数。
任何数和其自身做异或运算，结果是 0。
异或运算满足交换律和结合律。

137. 只出现一次的数字 II
这题是真难。
其实关键就是：数电的方法优化在利用位运算的并行性，直接使用32个状态机（每个二进制位都当作一个状态机），而方法二只使用了一个状态机，所以时间复杂度多了一个logC。

二进制求和

二进制求和

两个二进制数 异或^ 可以视作忽略进位的求和，但之后要补上进位。
怎么补呢？用 与& ，&完之后还需要左移一位（能理解吧），之后迭代重复以上步骤知道进位变为0。

同时注意：java里数字异或不需要转为二进制数，用十进制数来异或是正确的。
Integer.parseInt(String 2)将字符串a按二进制解析其内容(解析成10进制数)，Integer.toBinaryString(int n)将十进制数转为二进制字符串。

颠倒二进制位

190. 颠倒二进制位
这个分治解法太骚了，翻转一个二进制串，可以将其均分成左右两部分，对每部分递归执行翻转操作，然后将左半部分拼在右半部分的后面，即完成了翻转。
上面的是正常解法，是自顶向下的。
但是，注意到位运算的特殊性，并且左右两边的计算方法相同，并且已知是32位的二进制数，所以我们可以直接自底向上（到这里总算开始理解了自底向上，其实自底向上并不总是用在递归中，用在这里或者用在动态规划就像作弊一样，关键点就在你要知道底在哪里，并且向上的过程要很清楚）。
这里直接定义4个常数M1234，他们的意思分别就是最后一层(只颠倒奇偶)、倒数第二层(将颠倒奇偶之后的按两位一组分成奇偶组，接着颠倒奇偶组)、倒数第三层、倒数第四层。

另外注意的是，在某些语言（如Java）中，没有无符号整数类型，因此对 n 的右移操作应使用逻辑右移 >>>。

同样的分治解法还有数1的个数191. 位1的个数

4的幂

342. 4的幂
n & (n - 1)==0 判断 n 是否是 2 的幂，==0就是2的幂，2 的幂是一个很严格的条件。5*2^6并不是2的幂，2的幂和4的幂真的就差一点，补充条件即可。

2的幂

2的幂

一个数 n 是 2 的幂，当且仅当 n 是正整数，并且 n 的二进制表示中仅包含 1 个 1。

因此我们可以考虑使用位运算，将 n 的二进制表示中最低位的那个 1 提取出来，再判断剩余的数值是否为 0 即可。下面介绍两种常见的与「二进制表示中最低位」相关的位运算技巧。

关键就是只管最低位的1。

n & (n - 1)==0 注意，n = n & (n - 1)操作可以将任意整数 n 的最后一位1变为0，由于2的幂只有一位1，所以最后一位1变为0之后结果如果是0则n为2的幂。

n & (-n)==n 能够直接提取最低位的1，其他位都变为0。

那么 n 就是 2 的幂。

还有剑招：用2的最大幂除n，能整除则true。

比特位计数

338. 比特位计数 有库函数法(Integer.bitCount())、动态规划解法，也可以用Brian Kernighan 算法，原理就是利用前面说过的n = n & (n - 1)操作可以将任意整数 n 的最后一位二进制 1 变为 0 ，那么对 x 重复该操作，直到 x变成 0，则操作次数即为 x 的「一比特数」。

错误的集合

645. 错误的集合

这个位运算解法还不错，

链表

环形链表2

哈希表
unordered_set<ListNode *> visited;
unordered_set可以用 ListNode * 数据类型

快慢指针一定在环内相遇，根据数学来找到开始入环的第一个节点。

Floyd 判圈算法
Floyd判圈算法（Floyd Cycle Detection Algorithm），又称龟兔赛跑算法（Tortoise and Hare Algorithm），是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，以及判断环的起点与长度的算法。

160. 相交链表

被简单题薄纱（没有题感说实话）
相交链表

哈希

在字符匹配的题里尽量用数组代替哈希表。这个很重要很重要

哈希表的 value 可以是一个数组，见697. 数组的度
这个用法真的很重要。如java：
Map<Integer, int[]> map = new HashMap<Integer, int[]>();

在实际代码中，我们使用哈希表实现该功能，每一个数映射到一个长度为 3 的数组，数组中的三个元素分别代表这个数出现的次数、这个数在原数组中第一次出现的位置和这个数在原数组中最后一次出现的位置。

202 快乐数

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

要找是否存在环(循环)的题都可以用 快慢指针 这种思想。
本题还可以使用哈希表unordered_set。

设计哈希集合

705. 设计哈希集合

为了实现哈希集合这一数据结构，有以下几个关键问题需要解决：

哈希函数：能够将集合中任意可能的元素映射到一个固定范围的整数值，并将该元素存储到整数值对应的地址上。
冲突处理：由于不同元素可能映射到相同的整数值，因此需要在整数值出现「冲突」时，需要进行冲突处理。总的来说，有以下几种策略解决冲突：

• 链地址法：为每个哈希值维护一个链表，并将具有相同哈希值的元素都放入这一链表当中。
• 开放地址法：当发现哈希值 h 处产生冲突时，根据某种策略，从 h 出发找到下一个不冲突的位置。例如，一种最简单的策略是，不断地检查 h+1,h+2,h+3,… 这些整数对应的位置。
• 再哈希法：当发现哈希冲突后，使用另一个哈希函数产生一个新的地址。

扩容：当哈希表元素过多时，冲突的概率将越来越大，而在哈希表中查询一个元素的效率也会越来越低。因此，需要开辟一块更大的空间，来缓解哈希表中发生的冲突。

质数取模，其实是利用了同余的概念：当元素是个有规律的等差数列时，并且和基数（数组大小）最大公约数不为1时，就会造成哈希映射时冲突变高（数组某些位置永远不会有值）。比如数列0,6,12,18,24,30…，

base为10，取模(0,6,2,8,4,0…)后，放入哈希表中位置将只能在0,2,4,6,8这几个数组位置上；
但我们如果把base取7（数组大小甚至比10小），同样数列取模后(0,6,5,4,3,2,1,0,…)，可以分布在哈希表中的0,1,2,3,4,5,6所有位置上；
后续：若x和y的最大公约为z，x和y的最小公倍数就为(xy)/z，很明显，若z为1，也就是俩数的最大公约数为1的时候，那么俩数的最小公倍数就为xy。

那么当一个数为质数时，除了其自身的倍数外，其余数和其的最大公约数都将是1，这时，步长选任何数（除了倍数）都可以满足桶的均匀分布。

所以，以取模计算哈希值在桶中的位置是，用一个质数当作基数时可以使得哈希表中每个位置都“有用武之地”。

Hash表为什么需要使用mod素数？

从素数定理出发，我们可以知道素数有如下性质 素数定理：在初等数学中有一个基本定理，任意一个大于1的自然数，要么本身就是质数，要么可以分解为几个质数之积，这种分解本身，具有唯一性

在知道素数的性质后，回过头来看Hash表，我们将元素放在Hash表当中，需要解决的一个问题就是尽量解决冲突。

给出一份实验，结论表明：模数的因子会影响数列的冲突，而且因子越多，冲突的可能性就越大。而素数的因子恰好只有1和其本身,就非常适合用于解决冲突。
比如 2 4 6 8 10 12这6个数，如果对 6 取余 得到 2 4 0 2 4 0 只会得到3种HASH值，6的因子有1，2，6。冲突会很多。如果对 7 取余 得到 2 4 6 1 3 5 得到6种HASH值，而7的因子只有1，7。

由3可知，即使1的因子最小，但是在实际中并不用，因为mod1相当于不解决冲突。而初始化的的数组就会非常大。

Rabin-Karp 算法

有一题字符串的题也用的这个解法，哪题我忘记了，好像是快乐字符串什么的困难题，还有另一题也用这个，所以这是第三次遇到这个解法。

718. 最长重复子数组

Rabin-Karp 算法将一个序列 S 计算为哈希值，首先指定基数 base（最好是个质数），将序列 S 看作 base 进制的数求得哈希值，为防哈希冲突可以再哈希等等，不过也够用了。由于这个值一般会非常大，因此会将它对另一个素数 mod 取模。

字符串

字符串匹配问题可以多尝试再复制一份母串，可能会有奇效， 如796. 旋转字符串

C++ 中的 String 类
C++ 标准库提供了 string 类类型。

string类提供了一系列成员函数，比如：

1. append() -- 在字符串的末尾添加字符(单字符也可以) // 也可以使用+和+=运算符对 string 对象执行字符串的连接操作
append()相比于+和push_back()有更强的功能，可以加入一个string对象的子串，如下;
string s1("123"), s2("abc");
s1.append(s2);  // s1 = "123abc"
s1.append(s2, 1, 2);  // s1 = "123abcbc"
s1.append(3, 'K');  // s1 = "123abcbcKKK"
s1.append("ABCDE", 2, 3);  // s1 = "123abcbcKKKCDE"，添加 "ABCDE" 的子串(2, 3)
这里子串(n, m)是指从原字符串下标 n 开始、长度为 m 的字符串
2. find() -- 在字符串中查找字符串
3. insert() -- 插入字符
4. length() -- 返回字符串的长度 // 用size()也可以
5. replace() -- 替换字符串
6. substr(pos, n) -- 返回s中从pos(索引)开始的n个字符的拷贝，可以只有pos，这时返回从pos开始的剩余的所有字符
7. erase() -- 删除zi
string s1("Real Steel");
s1.erase(1, 3);  //删除子串(1, 3)，此后 s1 = "R Steel"
s1.erase(5);  //删除下标5及其后面的所有字符，此后 s1 = "R Ste"

std::string 类本身就提供了类似「入栈」和「出栈」的接口，因此我们可以直接将字符串作为栈使用。类似的成员函数有：
1. empty()
2. back()  // 相当于top()  取出最后一个元素
3. pop_back() // 相当于pop()
4. push_back()

5. front()  // 取出第一个元素
string类重载了[]运算符像数组一样直接访问元素

判断相等直接用==就可以了，但是！要注意string对象不能和'单字符'比较，一定要和"字符串"比较。
和单字符比较时也一定要用双引号""。

string数字怎么转换为真正的数字，如"-123"->-123
string str;
int num = atoi( str.c_str() ) // C风格
int num = stoi( str )              // C++风格 直接用就完事

atoi 可以将字符数组转换为数字，并且可以加号和负号一同变为数字。
string str = "-100";
int num = atoi(str); // 这样是不行的，因为atoi不支持直接把c++的字符串改为数字，只能先变为字符数组才行
通过c_str将string变为字符数组，再用atoi来变为数字
int num = atoi(str.c_str());

algorithm库中的reverse()函数可以直接反转字符串, 对vector也适用
void reverse(s.begin(),s.end());  
void swap(s[i]m s[j])；swap方法可以交换两个元素

151 翻转字符串里的单词

真的好题，确实难双指针的极致应用

想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。

O(1)空间复杂度的解法确实想不出来。
整个字符串翻转，再翻转各个单词。思路太难想了吧。
其实想不出来也应该把删除所有多余空格这一步弄出来，一步步做题。之后没准就想出来了。其实还是字符串不熟，没用过erase()；
但是erase()是O(n)的时间复杂度，所以不能用。
用前后快慢指针删除vector/string的某一种元素，如果是相向指针会改变顺序，所以得用前后快慢指针来删除空格。

28. 实现 strStr()

KMP算法经典问题， 找字串

void getNext(vector<int>& next, const string& s) {
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            int k = next[i-1];
            // 找到子对称字符串为止
            while( s[i] != s[k] && k>0 ) {
                k = next[k - 1];
            }
            // 下面这段代码有更常见的形式，其实是一模一样的
            // if( s[i]==s[k] ){
            //     next[i] = k + 1;
            // }
            // else
            //     next[i] = 0;
            // 退出循环只有两种情况
            if( s[i]==s[k] ){
                k++;
            }
            next[i] = k;
        }
    }

KMP算法的前缀next数组最通俗的解释 这篇文章讲的不错。

很重要的一点就是，匹配失败的时候要找已经匹配的字符串内部对称的子字符串，这也是KMP的内核，当一个字符串的对称程度越高，KMP算法效果越好。这里的对称不是指一次对称，而是像这样的:
01234567891011
abtab gabtabt3
00012012345
t无法继承（如果这个字符没有失配，配哪个呢，索引就是前一个字符的next值，那它的next就是前一个字符的next加一）前一个字符的next对应值因为这里失配了，即t=s[i]，这时候s[i]不等于s[(k=next[i-1]=next[b]=5)]=g。
那这时候t的next值怎么看，开始找匹配好的字符串里面的子对称字符串，并且t一定要和那个子对称的下一个字符相同。
更新k = next[k - 1]=next[4]=2;这时候的k代表已经匹配好的字符串里的子对称的长度，你看abtab里面的ab。ab就是我们要找的子对称字符串，它的下一个字符是不是t，这时候就匹配了可以退出循环，next[t]=k+1；
那为什么更新k = next[k - 1]呢，这一步挺关键的。
原来的k是5，是什么意思？这个5=next[t-1]是t前一个字符b的next，表示这个字符和它前四个字符也就是长度为5的后缀与长度为5的前缀相同。
那我要找这个匹配好的长为5的字符串的子对称字符串怎么找，那当然是next[4](索引是长度-1)直接查前缀就行。
有更复杂的情况
abtababtab g abtababtabt
00012123450123456789103
这种才是真正的对称
更新k = next[k - 1]你要更新两次才能找到，找到什么？匹配好的字符串里面的子对称字符串，并且t一定要和那个子对称的下一个字符相同。
刚开始：k = 10；
更新：k=next[k-1]=next[9]=5
这不是找到abtababtab长为5的对称子串了吗？但是，这个字串的下一个字符是a，不等于t就，也就是while循环里的判断条件，还得更新。
更新：k=next[k-1]=next[4]=2
这时候终于找到了，所以next[t]=k+1=3;
k=0当然就没意思了，说明没有对称子串了，因为k即next代表相同的前后缀的长度，零的话我直接比较s[i]和s[0](也是s[k])不就好了。

时间复杂度O(m+n)，空间复杂度O(m) n是主串长度，m是模式串长度

字符串匹配算法: kmp和bm算法

459.重复的子字符串

上限很高的简单题

要理解一个关键原理:
长度为 n 的字符串 s 是字符串 t=s+s 的子串，并且 s 在 t 中的起始位置不为 0 或 n，当且仅当 s 满足题目的要求(给定一个非空的字符串s，可以通过由它的一个子串重复多次构成。)，即为充要条件。
可以用string类自带的find函数查找索引，之所以要求索引不为0或n，是因为第一个删除了s+s的第一个和最后一个”子串”，两个s都不完整，由于子串长度至少大于1，所以删除前后各一个字符。
当然也可以用KMP实现自己的查找函数。

这题还能进一步优化。
符合要求的字符串，最后一位的next值=n-i;
其中n为字符串长度，i为重复的子串的长度。
所以 i = n-next[n-1]
又有gcd(n,i) = i n肯定整除i，并且i为最小的起始位置。
所以只要判断n是否能整除i(n-next[n-1])即可，能整除则true。

队列与栈

匹配问题都是栈的强项。

232 用栈实现队列

就差一点就能更优化，应该再多想想不要急。画个图就能发现，用来输出的第二个栈的元素不用再倒回去。
基本就是输入输出栈完全分开了。

150. 逆波兰表达式求值

这不仅仅是一道好题，也展现出计算机的思考方式

为什么要将看似简单的中缀表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

239. 滑动窗口最大值

我用的哈希表加剪枝，以临界时间通过，如果题目数据大一点就不容易通过了。

很难很好的题。
学到很多：优先队列(堆)，单调队列(由deque实现，满足单调性的双端队列)，通常并不是单独使用的，还有分块加预处理(很有意思的解法)。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

解法

数据流中的第 K 大元素 优先队列

703. 数据流中的第 K 大元素

小顶堆
直接当普通队列使用即可：

// java
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.offer(val);
pq.poll();
pq.peek();

347. 前 K 个高频元素 优先队列

好题。
优先队列 ，要知道堆的操作时间复杂度是和堆总元素数有关的，如果堆大小至多为k，则每次堆操作需要O(logk)的时间，操作N次的话就是O(Nlogk) 的时间。
还学到了自定义排序规则：
注意定义优先队列的排序时是反过来的，比如>号是小根堆，<号是大根堆。以下的例子都是小根堆，默认创建时为大根堆。
并且注意调用时候的用法

bool cmp(const pair<int, int>& a, const pair<int, int>&b){
    //自定义的比较函数，按第一个元素从小到大排序，如果第一个元素相同，则按第二个元素从小到大排序
    if(a.first == b.first){
        return a.second > b.second;
    }
    return a.first > b.first;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> pq(cmp);

// 优先队列常用成员函数
q.emplace(a,b); // pair<int,int>
q.top();
q.pop();


static bool cmp(pair<int, int>& m, pair<int, int>& n) {
        return m.second > n.second;
    }

// 用内置greater函数就是小根堆，默认的less是大根堆；
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > q;

priority_queue 对象的第一个模板参数是 pair<int, int>，表示队列中的元素类型为 pair。第二个模板参数是 vector<pair<int, int>>，表示使用 vector 作为底层容器。第三个模板参数是自定义的比较函数 cmp 的类型，使用 decltype(&cmp) 来获取函数指针的类型。

读者需要掌握自己实现堆的方法，包括「建堆」、「调整」和「删除」的过程。
可以再看看912排序数组，用了堆排序。

// 大根堆  堆就是完美二叉树并且存储在数组中

// 这个函数的作用是调整 O(lgn)
void maxHeapify(vector<int>& a, int i, int heapSize) {
         // 左右子节点
        int l = i * 2 + 1；
        int r = i * 2 + 2;
        int largest = i;
        // 找到两个子节点的较大值 将其与父节点交换，换完之后要对这个父节点往下递归，也就是下沉，因为有可能这个父节点很小(至少比换位置后新的子节点小)，要一直往下沉
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    /**
    其实是调整前半个堆，为什么？因为堆是一个完美二叉树，而且只对所有父节点有要求，要求每个父节点大于其所有子节点，
    而所有树的父节点数(非叶子节点)不会超过树总结点数的一半，而且在maxHeapify里会判断子节点是否存在，所以这样写没有问题。
    也就是说，建堆过程是至多调整前半个堆，也就是前半个数组，循环调用maxHeapify来把nums[i]调整到合适的位置
    O(n*lgn)
    */
    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize); // 建好了整个大根堆 准备pop K-1次，堆顶的值就是第K最大

        /*删除操作的完成是这样的：
        1. 将堆顶(nums[0])与堆最后一个节点(nums[heap.size()-1])交换，令记录的堆大小减一，实际上并没有改变vector的大小，相当于删除当前的堆尾，也就是刚刚pop的堆首；
        2. 调整当前的堆，也就是对调整新堆首到合适的位置，由于maxHeapify中的递归，能将整个堆调整好。
        */
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

还有快速选择法(基于快速排序的选择方法)，通过每次都只在其中一个分支进行递归，能够将算法的平均复杂度降低到O(N)。
快排可以通过在每次递归的开始随机选取中枢元素来降低出现最坏情况的概率。还可以使用双指针的方法，这种方法可以较好的应对各种数据。
再做一题K大数：

215. 数组中的第K个最大元素

字节真的考过这个，还是得实现O(n)的时间复杂度，所以用堆是不行的。得用快速选择：

根据快排的原理我们知道，在递归一次的时候我们一定可以确定一个元素的最终位置，即 x 的最终位置为 q，并且保证 a[l⋯q−1]中的每个元素小于等于 a[q]，且 a[q] 小于等于 a[q+1⋯r]中的每个元素。所以只要某次划分的 q 为倒数第 k 个下标的时候，我们就已经找到了答案。 我们只关心这一点，至于 a[l⋯q−1]和 a[q+1⋯r]是否是有序的，我们不关心。

因此我们可以改进快速排序算法来解决这个问题：在分解的过程当中，我们会对子数组进行划分，如果划分得到的 q 正好就是我们需要的下标，就直接返回 a[q]；否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是「快速选择」算法。

基于快速排序的选择方法
只讨论大量相同的数据的情况，如果只是选择随机数的话是无效选择，基本就是快排的最坏情况即冒泡排序。用双指针版快排则可以有O(nlgn)的时间复杂度因为每次都可以跑到最中间，（顺便说一下，快排有三指针的优化）

int quickselect(vector<int> &nums, int l, int r, int k) {
        if (l == r)
            return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < partition);
            do j--; while (nums[j] > partition);
            if (i < j)
                swap(nums[i], nums[j]);
        }
        if (k <= j)return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }

注意，双指针是应对大量重复数据的，这也是为什么用 do while ，如果很多数据，则 i j 索引指的数据都相同，这时候 i j 交换完数据后会同时减，这样 i j 碰头的时候基本就在中间，后面只递归一次的时候基本可以少递归一半的重复数组。

树

好难的二叉树( 迭代 递归 都难 )

树的种类

满二叉树

完全二叉树

完全二叉树的定义如下：在完全二叉树中，除了最后一层其它层全部填满，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。

优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树
  （严格递增）

如：

平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树(红黑树)，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_set，因为它们的底层实现是哈希表。

二叉树的存储方式

链式存储与顺序存储

链式存储方式就用指针， 顺序存储的方式就是用数组。

顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

用数组来存储二叉树如何遍历的呢？

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树的遍历

二叉树主要有两种遍历方式：

1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
2. 广度优先遍历：一层一层的去遍历。

DFS

深度优先遍历

• 前序遍历（递归法，迭代法）
• 中序遍历（递归法，迭代法）
• 后序遍历（递归法，迭代法）

前中后序遍历的前中后，其实指的就是中间节点的遍历顺序，只要记住 前中后序 指的就是中间节点的位置就可以了。

中间节点的顺序就是所谓的遍历方式（左子树一定在右子树之前）

• 前序遍历：中左右
• 中序遍历：左中右
• 后序遍历：左右中
  这里的左右理解为左右子树更好，同时左右子树也要保持相同的遍历顺序。

做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。
讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。

而广度优先遍历一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

// 节点定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

DFS 递归

//  递归  前序遍历  中序后序同理，修改顺序即可
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

DFS 迭代

二叉树

// 官解的迭代写的真的好
// 中序
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode *> stk;
        TreeNode* node = root;
        
        while( !stk.empty() || node ) {
            while(node) {
                stk.push(node);
                node = node->left;
            }
            node = stk.top();
            stk.pop();
            res.push_back(node->val);
            node = node->right;
        }
        return res;
    }
};

// 前序
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode *> stk;
        vector<int> res;
        TreeNode *node = root;
        while(!stk.empty()||node) {
            while(node) {
                res.push_back(node->val);
                stk.push(node);
                node = node->left;
            }
            node = stk.top();
            stk.pop();
            node = node->right;
        }
        return res;
    }
};

//后序
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode *> stk;
        vector<int> res;
        TreeNode *node = root;
        TreeNode *prev = nullptr;

        while(!stk.empty()||node) {
            while(node) {
                stk.push(node);
                node = node->left;
            }
            node = stk.top();
            if( node->right==nullptr||node->right==prev ) {
                res.push_back(node->val);
                stk.pop();
                prev = node;
            }
        
            node = node->right;
            if(prev&&(node==prev->right))
                node = nullptr;
        }
        return res;
    }
};

// 官解后序
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode *> stk;
        TreeNode *prev = nullptr;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.emplace(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            if (root->right == nullptr || root->right == prev) {
                res.emplace_back(root->val);
                prev = root;
                root = nullptr;
            } else {
                stk.emplace(root);
                root = root->right;
            }
        }
        return res;
    }
};

// 官解后序
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}

N叉树

589. N 叉树的前序遍历

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<Node> stack = new ArrayDeque<Node>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            res.add(node.val);
            for (int i = node.children.size() - 1; i >= 0; --i) {
                stack.push(node.children.get(i));
            }
        }
        return res;
    }
}

590. N 叉树的后序遍历

// 用 HashSet 标记是否把子节点放进来了，第二次访问才能读取它的 val
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        Set<Node> hset = new HashSet<Node>();
        Stack<Node> stk = new Stack<Node>();
        stk.push(root);
        Node node = new Node();
        while(!stk.empty()) {
            node = stk.peek();
            if(node.children.size() == 0 || hset.contains(node)) {
                list.add(node.val);
                hset.remove(node);
                stk.pop();
            }
            else {
                hset.add(node);
                for(int i = node.children.size()-1; i>=0; i--) {
                    stk.push(node.children.get(i));
                }
            }
        }
        return list;
    }
}

BFS

广度优先一定要想到队列

二叉树层序遍历 也即 广度优先遍历，图的广度优先也是要用队列，出队入队等。

• 层次遍历（迭代法）

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        TreeNode *idx = new TreeNode();
        int cnt = 0;

        if(root)
            que.push(root);

        while(!que.empty()){
            int i = que.size(); // 每次new一个一位vector，存完之后再push进res里比较好
            res.resize(res.size() + 1);
            for (; i > 0; i--){
                idx = que.front();
                que.pop();
                res[cnt].push_back(idx->val); 
                if(idx->left) que.push(idx->left);
                if(idx->right) que.push(idx->right);
            }
            cnt++;
        }
        return res;
    }
};

二叉树的最近公共祖先

体会递归的自顶向下和自底向上
本题时间复杂度是自顶向下(n^2)和自底向上(n)。

自底向上是这样的：要求出当前的值，我先去求子值也即缩小问题规模，不断缩小，再有得出来的一个个小问题的解来构建当前的值并根据题意做出相应的操作。实际上是怎么实现的？那便是二话不说直接往下递归，当然子问题的解你肯定要保留下来，得到了子问题的解边进行你要的操作。放在本题就是：

bool  Verify(TreeNode *root, TreeNode* p, TreeNode* q) {
        if(!root)
            return false;
        bool flag1 = Verify(root->left, p, q);
        bool flag2 = Verify(root->right, p, q);
        // if(((root==q||root==p)&&(flag1||flag2))||(flag1&&flag2))
        //     node =  root;
        // if(root==p||root==q)
        //     return true;
        // return flag1||flag2;
    }

除了第一句判断root存在否以外，直接就往下递归并保留下子问题的解。

而自顶向下是我往下递归，如果我需要当前问题的解来进行后序的操作，那我一定要现在立刻马上获得，比如这里为了获得flag1 2，我甚至用了Verify这个递归的函数来求解，那肯定带了许多重复运算。那便是O(n^2)。

class Solution {
public:
    bool Verify(TreeNode *root, TreeNode* p, TreeNode* q) {
        if(!root)
            return false;
        if(root==p||root==q)
            return true;
        return Verify(root->left, p, q) || Verify(root->right, p, q);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)
            return nullptr;
        bool flag1 = Verify(root->left, p, q);
        bool flag2 = Verify(root->right, p, q);

        // if((root==q||root==p)&&(flag1||flag2))
        //     return root;

        // if(flag1&&flag2)
        //     return root;
        // else if(flag1)
        //     return lowestCommonAncestor(root->left, p, q);
        // else 
        //     return lowestCommonAncestor(root->right, p, q);
        // return nullptr;
    }
};

我认为自顶向下和自底向上最核心的区别就是自底向上一定先会递归到底再求解问题。而自顶向下不一定会到底(这里考虑的肯定是递归的主函数，而不是Verify)，通过在每个节点都立刻算出当前的值，只要问题的解存在，那想必在递归的过程中就已经把问题解决了。

还有一个原因是我没想到可以用全局变量，没必要让递归来返回TreeNode*。

两数之和 IV - 输入二叉搜索树

653. 两数之和 IV - 输入二叉搜索树

这题的方法四还是挺厉害的。

具体地，我们对于每个指针新建一个栈。初始，我们让左指针移动到树的最左端点，并将路径保存在栈中，接下来我们可以依据栈来 O(1) 地计算出左指针的下一个位置。右指针也是同理。

计算下一个位置时，我们首先将位于栈顶的当前节点从栈中弹出，此时首先判断当前节点是否存在右子节点，如果存在，那么我们将右子节点的最左子树加入到栈中；否则我们就完成了当前层的遍历，无需进一步修改栈的内容，直接回溯到上一层即可。

实现起来有点像 头尾双指针 遍历 树。
在很多题都可以用，记得在对称二叉树那里也可以用。

两个栈

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        TreeNode left = root, right = root;
        Deque<TreeNode> leftStack = new ArrayDeque<TreeNode>();
        Deque<TreeNode> rightStack = new ArrayDeque<TreeNode>();
        leftStack.push(left);
        while (left.left != null) {
            leftStack.push(left.left);
            left = left.left;
        }
        rightStack.push(right);
        while (right.right != null) {
            rightStack.push(right.right);
            right = right.right;
        }
        while (left != right) {
            if (left.val + right.val == k) {
                return true;
            }
            if (left.val + right.val < k) {
                left = getLeft(leftStack);
            } else {
                right = getRight(rightStack);
            }
        }
        return false;
    }

    public TreeNode getLeft(Deque<TreeNode> stack) {
        TreeNode root = stack.pop();
        TreeNode node = root.right;
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        return root;
    }

    public TreeNode getRight(Deque<TreeNode> stack) {
        TreeNode root = stack.pop();
        TreeNode node = root.left;
        while (node != null) {
            stack.push(node);
            node = node.right;
        }
        return root;
    }
}

另一棵树的子树

难死了

572. 另一棵树的子树

方法一：
深度优先搜索暴力匹配
做两次深度优先，对每个节点的子树做一次暴力匹配。

方法二：深度优先搜索序列上做串匹配

因为一棵子树上的点在 先、中、后序 遍历下是连续的，所以可以判断 串2 是否是 串1 的子串。
我想到这个了，但是，这只是一个必要条件，并不充分。
可以通过引入节点的两个空值 leftNull 和 rightNull 节点来进行标记，这样子串就能唯一匹配。

可以用 KMP 来进行匹配判断。（KMP不知可以用来对字符串进行匹配，也可以用来对数组匹配）

public boolean kmp() {
        int sLen = sOrder.size(), tLen = tOrder.size();
        int[] fail = new int[tOrder.size()];
        Arrays.fill(fail, -1);
        for (int i = 1, j = -1; i < tLen; ++i) {
            while (j != -1 && !(tOrder.get(i).equals(tOrder.get(j + 1)))) {
                j = fail[j];
            }
            if (tOrder.get(i).equals(tOrder.get(j + 1))) {
                ++j;
            }
            fail[i] = j;
        }
        for (int i = 0, j = -1; i < sLen; ++i) {
            while (j != -1 && !(sOrder.get(i).equals(tOrder.get(j + 1)))) {
                j = fail[j];
            }
            if (sOrder.get(i).equals(tOrder.get(j + 1))) {
                ++j;
            }
            if (j == tLen - 1) {
                return true;
            }
        }
        return false;
    }

方法三： 树哈希

很牛的方法，字节面过要求写出这个，估计是故意为难人的。

自定义哈希函数，把每个子树都映射成一个唯一的数。

本质就是每个子树的哈希值要考虑每个节点的值，子树哈希值，子树大小，以及左右子树拥有不同权值，这样出现冲突的几率比较小。如果还怕出现冲突，可以设计两个哈希函数，由这两个哈希函数生成第三个哈希函数，这就是双哈希。

这里求素数再用上之前学过的 埃氏筛法（此处为欧拉筛）。

回溯

讲道理，遇到回溯题，自己把递归树稍微画一下。

回溯本质就是暴力枚举，通过递归来实现。

尽量多用全局变量（就算集合也可以用全局），可以省内存，但要注意。
不管什么写法（用全局还是传下来的集合参数），添加结果的时候都一定要拷贝一份，不然结果会出错，因为 Java 是 pass by reference。如：ans.add(new ArrayList<>(temp));

// 回溯的第二种经典写法 即：不选走一次，选的话也走一次
/*
第一种经典写法是用 for 循环，也就是回溯里用for循环表示层内遍历，
而递归本身是纵向遍历。 这种写法能更好地理解回溯，
回溯相当于树的深度，而for循环本身是树的宽度， 我常用这种写法
*/
class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return ans;
    }

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }
}

二进制手表

401. 二进制手表

这是这题的回溯解法，其实就是罗列所有 1 的位数等于 turnedOn 的10位二进制数，进一步判断是否题意( 即 private String convert(int num)中所列的，当不满足时返回空串)，所以明确回溯的目标和难点就是罗列所有 1 的位数等于 turnedOn 的10位二进制数（这也是我不会的，毕竟第一次做回溯，后面肯定拿下）。

turnedOn( 1 的总位数 )肯定是关键，分散到十位二进制数的每一位看就是 这一位取0还是取1 的小问题，取了 0，剩余位数一定要满足一共有 turnedOn 个 1 ，取了 1 ，剩余位数一定要满足一共有 turnedOn-1 个 1 ，那很明显了，这就是递归，我们用num保存这个结果传递给两个子递归。剩余 1 的总位数一定要传递，还有个关键就是记录当前走到这个十位二进制数的哪一位了，也就是 参数 idx。

说到递归一定要想到 递归的底是什么，底当然是 turnedOn递减为0，这时候的 数(num) 才能符合第一个要求，这时候就交给private String convert(int num)函数了。

还要注意对回溯剪枝，毕竟回溯是暴力解法，适当的剪枝能提高程序性能，结合我们的
参数 idx 表示走到哪一位了，参数 turnedOn 表示剩余位数还需要取几个1，还有这一定是一个十位二进制数，剪枝呼之欲出：

if ( (turnedOn+idx)>10 ) {
    return;
}

    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        backtrace(0, 0, turnedOn, res);
        return res;
    }
    private void backtrace(int num, int idx, int turnedOn, List<String> res) {
    if (turnedOn == 0) {
        String r = convert(num);
        if (!"".equals(r)) {
            res.add(r);
        }
        return;
    }
    //剪枝  现在有的位数加上你还需要的1的数目超过了10位，那这个肯定不是你要的数了
    if ( (turnedOn+idx)>10 ) {
        return;
    }
    //选和不选
    backtrace(num, idx + 1, turnedOn, res);
    num |= (1 << idx);
    backtrace(num, idx + 1, turnedOn - 1, res);
}

private String convert(int num) {
    int hour = (num & 0b1111000000) >> 6;
    int minute = (num & 0b111111);
    if (hour >= 12) {
        return "";
    }
    if (minute > 59) {
        return "";
    }
    StringBuilder sb = new StringBuilder();
    sb.append(hour + ":");
    if (minute < 10) {
        sb.append("0");
    }
    sb.append(minute);
    return sb.toString();
}   

77. 组合

77. 组合

非递归（字典序法）实现组合型枚举 看不懂，好难

40. 组合总和 II

前提：去重一定要排序。

40. 组合总和 II
第一次做要去重的题，我真的麻了，仅仅是因为不确定局部变量在递归时候的变化（实际上递归时是会进行压栈保存环境的，当你递归出来的时候数据是完全不会变的，看了这么多理论竟然不会用，我真的服了你了），仅仅把preval定成全局的，没有去思考定成局部的数据并付诸行动导致失败，各种尝试都做不出来，离成功就差一点。真的服了你了。

看看人家的：
去重就是，dfs的同一层第二次遍历到一个数，那么就是重复的，保证每一层一种数只会遍历到一次，又因为进入dfs前数组经过了排序（相同数一定相邻），所以去重只需要在每一层遍历一个数时，判断上一个数是否和当前数相同，相同的话就是重复了，就不需要再对这个数进行递归。

class Solution {
public:
	void backtracking(vector<vector<int>>& res, vector<int>& temp, vector<int>& candidates, int target, int index, int& sum) {
		// 判断temp加上当前index的值是否是
		if (sum == target) {
			res.push_back(temp);
			return;
		}
		if (sum > target) return;
		// preVal是解决会出现重复结果问题
		int preVal = -1;
		// 如果sum小于target
		for (int i = index; i < candidates.size(); i++) {
			if (candidates[i] != preVal && (sum + candidates[i]) <= target) {
				preVal = candidates[i];
				temp.push_back(candidates[i]);
				sum += candidates[i];
				backtracking(res, temp, candidates, target, i + 1, sum);
				sum -= candidates[i];
				temp.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		vector<vector<int>> res;
		if (candidates.size() == 0) return res;
		// 从小到大排序
		sort(candidates.begin(), candidates.end());
		vector<int> temp = {};
		int sum = 0;
		backtracking(res, temp, candidates, target, 0, sum);
		return res;
	}
};

看看我的：

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTrace(candidates, target, 0, 0);
        return ans;
    }
    private void backTrace(int[] candidates, int target, int sum, int startIdx) {
        if(sum==target){
            ans.add(new ArrayList<>(tmp));
            return;
        }
        int preVal = -1;
        for(int i = startIdx; i<candidates.length && (sum + candidates[i]) <= target ; i++) {
            if(candidates[i]!=preVal){
                tmp.add(candidates[i]);
                preVal = candidates[i];
                backTrace(candidates, target, sum + candidates[i], i + 1);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}

这题的去重原理可以看 代码随想录

这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单！

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过（同一子树, 一个子树就是一个集合），一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。其实就是，重复出现的元素，第一次出现的是最好用的，它会把所有有用的集合都包括起来，而后面出现的只会造成重复！

强调一下，树层去重的话，需要对数组排序！

讲道理，遇到回溯题，自己把递归树稍微画一下。

重点在于区分 “树层去重”和“树枝去重”。

妈的还有更狠的：直接用startIndex来去重

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            // 要对同一树层使用过的元素进行跳过
            if (i > startIndex && candidates[i] == candidates[i - 1]) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i + 1); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
            sum -= candidates[i];
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        path.clear();
        result.clear();
        // 首先把给candidates排序，让其相同的元素都挨在一起。
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

子集 II

子集 II

注意子集(子序列)和之前的区别，之前是不选没关系，直接往下走就可以，等走到底添加结果，相当于只要叶子节点，而子集在你选或者不选的情况下都需要直接添加进结果，也就是所有节点都是我们想要的结果。

class Solution {
          List<List<Integer>> ans = new ArrayList<>();
          List<Integer> tmp = new ArrayList<>();
          public List<List<Integer>> subsetsWithDup(int[] nums) {
              Arrays.sort(nums);
              ans.add(new ArrayList<>(tmp));
              backTrace(nums, 0);
              return ans;
          }
          private void backTrace(int[] nums, int startIdx) {
              if(startIdx==nums.length) {
                  return ;
              }
              for(int i = startIdx; i<nums.length; i++) {
                  if(i>startIdx && nums[i]==nums[i-1])
                      continue;
                  tmp.add(nums[i]);
                  ans.add(new ArrayList<>(tmp)); // 就是这里
                  backTrace(nums, i+1);
                  tmp.remove(tmp.size()-1);
              }
          }
}

491.递增子序列

491.递增子序列
真尼玛难啊

这里不能排序了，所以用 hashset uset 表示这层用过的符合要求的数，这里的符合要求指的是非递减。
这种hashset用法也可以用于前面的 子集Ⅱ 题，但是依然需要排序。
比如 4 4 1 4 4 4 不排序的话会有 4 1 和 1 4，那为什么这题不需要排序呢。
因为这题要求非严格递增，不会有 4 1 ，只会有 1 4。

去重题看 代码随想录 讲的确实清楚。
关键还是 树层 不能重复。

唉真是无语了，心累。

46. 全排列

46. 全排列

我写了标记数组 ，没想到还有这么秀的解法。
要好好理解递归的变量保存，回溯的撤销操作。
这两点很重要。
撤销撤销撤销

class Solution {
          List<List<Integer>> ans = new ArrayList<>();
          List<Integer> tmp = new ArrayList<>();
          public List<List<Integer>> permute(int[] nums) {
              List<Integer> output = new ArrayList<Integer>();
              for (int num : nums) {
                  output.add(num);
              }
              backTrack(output, 0);
              return ans;
          }
          private void backTrack(List<Integer>  nums, int startIdx) {
              if(startIdx==nums.size()) {
                  ans.add(new ArrayList<>(nums));
                  return ;
              }
              for(int i = startIdx; i<nums.size(); i++) {
//                  tmp.add(nums.get(i));
                  Collections.swap(nums, startIdx, i);
                  backTrack(nums, startIdx+1);
//                  tmp.remove(tmp.size()-1);
                  Collections.swap(nums, startIdx, i);
              }
          }
      }

全排列 II

47.全排列 II

目前为止已经遇到了 组合、子集、排列的去重。

允许排序的题都可以先排序再去重，当然对这题而言也可以不排序的去重也就是用 uset 记录当前树层使用过的数字，但是之前的组合用 uset 的话也得去重，之前讲过了，这题的话因为是全排列所以可以。

排序去重的话效率肯定更高，这里的话得用标记数组了，不能用之前全排列的优化方法，因为那个方法会改变数字的顺序，排序数组也变乱序数组了。

排序去重最为关键的代码为：

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

如果改成 used[i - 1] == true， 也是正确的!，去重代码如下：

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
    continue;
}

如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。
具体可以看 47.全排列 II中的图。

51. N 皇后

51. N 皇后

经典回溯，没写出来

37. 解数独

37. 解数独

做出来了。

有迭代优化，不断循环固定那些只能放一个数字的位置，之后再去回溯。

494. 目标和

494. 目标和

这题最好的做法是转化为0-1背包问题进行求解。

这里说一个回溯的注意事项，困扰了很久。

首先此背包问题可以转化为一个组合问题，关键在于递归的返回时间。

如果用的是 for 循环的写法，不能加上判断索引是否走到数组末尾这个条件，表面上没有影响，实际上是有的，会影响那么几个值，调试一下就知道了，因为如果最后一个数不取也就是不拿(startIndex-1)能达到target，不取之后并没有继续调用递归函数，因为for循环到底了，所以不取最后一个数的结果是没有计入ans的（因为此时startIndex != candidates.length），所以判断不拿是否应该计入ans得在for循环之前判断，而此时startIndex != candidates.length，也就是加入判断索引是否走到数组末尾这个条件确实是会影响的，之前的写法都没有写这个条件所以能通过，之前没注意到这个，没想到今天被暴击了。

并且注意到，反正是组合，达到条件之后自然可以记录下来。

调试果然还是好用的。

    class Solution {
        int cnt = 0;
        public int findTargetSumWays(int[] nums, int target) {
            int sum = Arrays.stream(nums).sum() + target;
            if(sum<0 || sum%2!=0) return 0;
            int bagSize = sum/2;
            backtracking(nums, bagSize, 0, 0);
            return cnt;
        }
        void backtracking(int[] candidates, int target, int sum, int startIndex) {
            // 这是错误的，不能多加这个判断
//              if(startIndex == candidates.length) {
//                  if (sum == target) {
//                      cnt++;
//                  }
//              }

            // 这是正确的
            if (sum == target) {
                cnt++;
            }
            for (int i = startIndex; i<candidates.length; i++) {
                sum += candidates[i];
                backtracking(candidates, target, sum, i + 1);
                sum -= candidates[i];
            }
        }
//    public int findTargetSumWays(int[] nums, int target) {
//        int sum = Arrays.stream(nums).sum() + target;
//        if(sum<0 || sum%2!=0) return 0;
//        sum /= 2;
//        int [] dp = new int[sum+1]; // 表示凑到总和为 j 有几种方案
//        dp[0] = 1;
//        for(int i = 0; i<nums.length; i++) {
//            for(int j = sum; j>=nums[i]; j--) {
//                dp[j] += dp[j-nums[i]];
//            }
//        }
//        return dp[sum];
//    }
    }

贪心

贪心基本都是 O(n) O(1)

跳跃游戏 II

跳跃游戏 II
有点难，但是能做，迭代有点难看懂。

关键在于：每次选能跳最远的那个位置去跳，别理解成每次跳最远的位置。比如当前位置我能跳到两三个位置，我看从这两三个位置起跳哪个能跳的更远，那这个位置就是局部最优的，当前我就选择跳这个位置。
也就是需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

每次以最大覆盖范围为一次跳跃次数。

406. 根据身高重建队列

406. 根据身高重建队列

烂题，烂的要死。

没做出来

435. 无重叠区间

没做出来 想死

435. 无重叠区间

妈的两题都倒在排序上，没有一点思路，怎么回事啊

我一直想的是移除，实际上反着来才好做，怎样符合题意地去放最多的区间。

我一直找最早下课的，这样我一天才可能上最多的课。

763. 划分字母区间

763. 划分字母区间

没用贪心做就是没做出来 ， 废物

只要记录最远出现的位置，说实话贪心代码都不太好实现。

int left = 0;
       int right = 0;
       for (int i = 0; i < S.size(); i++) {
           right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
           if (i == right) {
               result.push_back(right - left + 1);
               left = i + 1;
           }
       }

968. 监控二叉树

968. 监控二叉树

这个确实做不来，树dp也看不懂。

这题的后序遍历可以由底至上我知道，输在定义状态，随想录定义了三个状态在进行状态转移真的舒服很多。

定义状态真的很重要啊，像之前的线段树，还有很多动规题，定义出好的状态基本就成功了。

动态规划

动态规划思想

状态设计很重要，有时候状态设计是很难看出来的，没有定义状态也就没办法进行状态转移了。

第 300 题：「最长上升子序列」 待做

最后再谈谈状态转移的「无后效性」(当前状态与之后状态无关)

为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」。
我的解释：

「有向无环图」「拓扑序」表示了每一个子问题只求解一次，以后求解问题的过程不会修改以前求解的子问题的结果；
换句话说：如果之前的阶段求解的子问题的结果包含了一些不确定的信息，导致了后面的阶段求解的子问题无法得到，或者很难得到，这叫「有后效性」，我们在当前这个问题第 1 次拆分的子问题就是「有后效性」的（大家可以再翻到上面再看看）；
解决「有后效性」的办法是固定住需要分类讨论的地方，记录下更多的结果。在代码层面上表现为：
状态数组增加维度，例如：「力扣」的股票系列问题；
把状态定义得更细致、准确，例如：前天推送的第 124 题：状态定义只解决路径来自左右子树的其中一个子树。

可以看看这篇讲股票系列问题的动规题解股票问题系列通解（转载翻译）

动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。

判断子序列

392. 判断子序列
判断 s 是否是 t 的子序列。

本质就是对 s 中每一个字符，在 t 中寻找下一个匹配字符，这也是时间复杂度的主要来源，当要匹配的子串 s 很多的时候，重复工作很多，所以可以尝试用动态规划的思想对母串 t 做预处理。

我们可以预处理出对于 t 的每一个位置(0~t.length-1)，从该位置开始往后每一个字符(a,b,c,…,z)第一次出现的位置(只需要记录第一次出现的位置即可，不需要更新也不能更新)，所以预处理数组dp[t.length][26]是一个二维数组。

令 dp[idx][c] 表示从 idx 位置开始字符 c (也就是当前匹配到的s中的字符)第一次出现的索引，状态转移是：
如果 dp[idx] 处的字符就是 c ，则 dp[idx][c] = idx ，否则 dp[idx][c] = dp[idx+1][c]，因为 c 没在 idx 位置，那么 c 一定在 (idx+1) 位置或之后的位置，也就是 dp[idx+1][c]。

状态转移表示 前面的状态要由后面的状态而来，所以动态规划应该倒过来，由底至上。
底部就是 dp[t.length-1][c]，如果在 t.length-1 位置出现了字符 c ，则dp[t.length-1][c] = t.length-1，其余的 25个字符不会再出现，dp值会等于 dp[t.length][c]，所以我们建的二维数组应该是 (t.length+1)*26 的，让边界也能进行状态转移，并且 dp[t.length][…] 应该初始化为让我们能够判断这个字符不存在的索引，比如就是t.length。
在遍历 s 中字符的时候，如果发现这个字符在 t 中的索引是 t.length ，则说明 s 并不是 t 的子序列，能够遍历完成则成功。

匹配过程就是直接dp[idx][s.charAt(j)]跳到这个字符所在的索引。

预处理的时间是固定的，并且之后匹配每一个 s 的时间复杂度都是 O(s.length)，所以当s数目很多的时候也可以完成匹配。

注意先判断这个字符所在的索引是不是t.length，不是的话索引更新为idx = dp[idx][c]+1用来匹配下一个字符(因为dp[idx][c]已经和这一个字符匹配了)，如果没有这个+1一定错。

比特位计数

338. 比特位计数

三种动规都很好理解。

53. 最大子数组和

53. 最大子数组和

前缀和解法

要边维护最小前缀和一边求答案，不能求出最大、最小前缀和再算差值，因为最小前缀和可能会出现在最大前缀和后面，我就是犯了这个错误一直写不出来。
并且前缀和要初始化为0，并且 curSum 加上当前值之后才能与 minPreSum 相减，因为子数组至少要有一个数。

int ans = Integer.MIN_VALUE;
int curSum = 0;
int minPreSum = 0;
for(int n : nums) {
    curSum += n;
    ans = Math.max(ans, curSum-minPreSum);
    minPreSum = Math.min(minPreSum, curSum);
}
return ans;

第一次接触到 线段树
这个线段树很有意思 ，维护四个变量，合并过程也很有趣

线段树区间合并法解决多次询问的「区间最长连续上升序列问题」和「区间最大子段和问题」

376. 摆动序列

376. 摆动序列

这个动规解释的很好

定义双状态，两个状态之间进行转移，不同于以前见到的只有一个状态。
上升摆动序列
下降摆动序列

var wiggleMaxLength_2 = function (nums) {
	const n = nums.length;
	if (n < 2) return n;
	//! up[i] 记录以i截止的上升摆动的最大长度
	const up = new Array(n).fill(0);
	//! down[i] 记录以i截止的下降摆动的最大长度
	const down = new Array(n).fill(0);
	up[0] = down[0] = 1;
	for (let i = 1; i < n; i++) {
		if (nums[i] > nums[i - 1]) {
			//! 上升摆动：
			//情况1：连续的上升，不用当前元素，沿用之前的上升摆动长度值
			//情况2：下降过程，从上一个下降摆动过来 + 当前元素 成为上升摆动
			up[i] = Math.max(up[i - 1], down[i - 1] + 1);

			//! 此过程是上升摆动，所以下降摆动未变化，所以沿用之前的值
			down[i] = down[i - 1];
		} else if (nums[i] < nums[i - 1]) {
			//! 下降摆动：
			//情况1：连续的下降，不用当前元素，沿用之前的下降摆动长度
			//情况2: 下降过程，由上一个上升摆动过来 + 当前元素 成为下降摆动
			down[i] = Math.max(down[i - 1], up[i - 1] + 1);
			//! 此过程是下降摆动，所以上升摆动未变化，所以沿用之前的值
			up[i] = up[i - 1];
		} else {
			//!既不是上升也不是下降，直接沿用直接的值 
			up[i] = up[i - 1];
			down[i] = down[i - 1];
		}
	}
	return Math.max(up[n - 1], down[n - 1]);
};

背包问题

0-1背包问题讲解见 代码随想录

在一维dp中很重要的一点就是遍历的顺序，首先，最外层应该是待放物品，这是最基本的保证物品只取一次的要求，其二，内层循环应该倒序，因为：在dp数组更新的时候是用上一层的左边索引处的值来更新当前层当前索引处的值，如果正序的话，那每个左边索引值都给你改成新值，还是错的，当前索引值有可能是对的么？

上面两个坑我都踩过了，卡哥还是牛。

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

完全背包问题讲解
01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

01背包中二维dp数组的两个for遍历的先后循序是可以颠倒的，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！

因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的新值就可以了。

对于纯完全背包问题，其for循环的先后循环是可以颠倒的！

但如果题目稍稍有点变化，就会体现在遍历顺序上。

如果问装满背包有几种方式的话？ 那么两个for循环的先后顺序就有很大区别了。

416. 分割等和子集

416. 分割等和子集

至于上面说到的 “在dp数组更新的时候是用上一层的左边索引处的值来更新当前层当前索引处的值” ，到底什么时候用左边更新当前，什么时候用右边更新当前呢？
还得看题意。

以本题为例：如果设dp[0] = true，慢慢更新到dp[sum]判断是否等于 true ，翻译过来就是用数组里的数能不能叠加到 sum，那很明显从索引0->sum自然就是以左更新右。
此时要用dp左边更新dp右边，所以肯定是先改右边的数再去改左边的数，即逆序。

我也可以这么看：设dp[sum] = true，慢慢更新到dp[0]判断是否等于 true ，翻译过来就是我能不能用 sum 去减数组的数，最终减到0，从索引sum->0自然就是以右更新左。
此时要用dp右边更新dp左边，所以肯定是先改左边的数再去改右边的数，即正序。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if(sum%2!=0) return false;
        sum /= 2;
        boolean [] dp = new boolean[sum+1];
        // 以左更新右
//        dp[0] = true;
//        for(int i = 0; i<nums.length; i++) {
//            for(int j = sum; j>=nums[i]; j--) {
//                dp[j] |= dp[j-nums[i]];
//            }
//        }

        // 以右更新左
        dp[sum] = true;
        for(int i = 0; i<nums.length; i++) {
            for(int j = 0; j<=sum-nums[i]; j++) {
                dp[j] |= dp[j+nums[i]];
            }
        }
        return dp[0];
    }
}

1049. 最后一块石头的重量 II

1049. 最后一块石头的重量 II

这个讲的也不错

// 思路：
// 动态规划：01背包

// 0.分析：
// 我们由题目可以知道经过n次粉碎后，最终最多只会剩下1个石头，并且我们需要让最后一块石头的质量最小
// 我们继续分析可以发现（关键）：我们可以将这一堆石头分成两堆（heap1和heap2）
// 我们不妨设 heap1总质量 >= heap2总质量，而最后的结果就是heap1 - heap2，我们只需要保证heap1 - heap2最小即可

// 0.1 如何计算：
// 我们可以先求出这一堆石头的总质量sum，
// 而sum = heap1 + heap2    （heap1 > heap2）
// heap1 - heap2 = sum - 2 * heap2
// 要求heap1 - heap2 的最小值，就可以转化成求sum - 2 * heap2 的最小值，
// 也就转化成了求 2 * heap2 的最大值，也就是求heap2的最大值（前提：sum - 2 * heap2 >= 0 等价于 heap2 <= sum / 2）
// 那么就转化成了01背包问题：背包的最大容量为 sum / 2


// 1.状态表示：f[i][j]
// 1.1 集合划分：i表示前i个石头，j表示背包最大容量；f[i][j]就表示前i个数，容量为j的背包能装下的石头最大质量
// （注意：此题的石头体积与石头质量都是stones[i]）
// 1.2 属性（一般为最大值、最小值、数量）：最大值


// 2.状态计算：
// 2.1 f[i][j]可以表示成f[i - 1][j]，表示不加上当前第i块石头的背包最大质量
// 2.2 f[i][j]还可以表示成f[i - 1][j - stones[i]] + stones[i]，表示加上第i块石头后背包最大质量
// 2.3 所以最后总和为j的所有方案为：f[i][j] = max(f[i - 1][j] + f[i - 1][j - stones[i]] + stones[i])


// 3.优化：
// 通过滚动数组可以将二维数组优化成一维数组：f[i][j] --> f[j] 



class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();
        int sum = 0;

        for (auto s : stones) sum += s;

        vector<int> f(sum / 2 + 1);

        for (int i = 0 ; i < n; ++i)
        {
            for (int j = sum / 2; j >= stones[i]; --j)
            {
                f[j] = max(f[j], f[j - stones[i]] + stones[i]);
            }
        }

        return sum - 2 * f[sum / 2];
    }
};

518. 零钱兑换 II

518. 零钱兑换 II

纯完全背包问题由于并不限制数组只取一次，所以内外循环没有额外要求，但某些情况除外！因为纯完全背包问题求的是最大价值，多余的排列并不影响这个值，但是影响计数！

不限制数目，所以是一个完全背包问题，但要注意的本题求的是组合数。
做法就是固定硬币的顺序，让外层循环遍历数组 coins 的值，内层循环遍历背包的大小，这样在求出 dp[i]的时候，该金额对应的硬币面额的顺序就固定了，因此不会计算重复的排列。
如 coins = [1,2]，对于 dp[3] 的计算，因为先遍历面额 1 再遍历面额 2，所以不会出现2+1的组合，只有1+1+1 和 1+2的组合。

反之，如果两个循环遍历颠倒，外层循环遍历背包的大小，内层循环遍历数组 coins 的值，则因为每个dp[i]都去尝试各个硬币值，一定会出现重复的排列，如coins = [2，3，5]，对于 dp[5] = 2+3 和 3+2，这就是区别。

377. 组合总和 Ⅳ

377. 组合总和 Ⅳ

刚好，上一题是组合，这一题考的是排列，很明显，只要更换内外层循环的顺序即可。

外层循环遍历从 1 到 target 的每个值，内层循环遍历数组 nums 的值，外层的每个值作为一个总和计算 dp[i] 时要考虑以 nums 的每一个小于等于 i 的数作为排列的最后一个元素的情况，将这些情况加起来作为当前的排列数。
如：以 nums={2,3,5} 为例，计算 dp[5]时会以 2 为结尾，以 3 为结尾，所以dp[5] = dp[3]+dp[2]。动手模拟下也能发现。

背包总结

背包的递推公式比较容易，难在遍历顺序上，把遍历顺序摸透，才算是真正理解背包。

一维 dp 数组 01背包 只能先遍历物品再遍历背包容量（因为每个物品只有一个），且第二层for循环是从大到小遍历（因为要用dp数组左边的旧值更新当前的值，所以只能从右往左更新）。

一维 dp 数组 纯完全背包先遍历物品还是先遍历背包都是可以的（因为纯完全背包求得是最大价值，求排列还是组合并不影响），且第二层for循环是从小到大遍历（因为每个物品可以取无限次）。

完全背包如果求组合数就是外层for循环遍历物品，内层for遍历背包（固定物品的顺序）。

完全背包如果求排列数就是外层for遍历背包，内层for循环遍历物品（不固定物品顺序）。

打家劫舍

198.打家劫舍

动态规划经典题，有扩展。

关键就在于 考虑这个关键字。

如果偷当前 i 这个房间，则 i-1不能考虑，注意，考虑不代表一定偷，偷不偷由遍历过程中的max来决定，保证取最大值。

也就是 dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

树 dp

目前做到的树 dp 都是用数组作为容器储存状态，就像之前提过的，问题复杂时可以用更多的状态来实现动态规划。

968. 监控二叉树

968. 监控二叉树

337. 打家劫舍 III

337. 打家劫舍 III

class Solution {
    public int rob(TreeNode root) {
        return traversal(root)[1];
    }
    private int[] traversal(TreeNode root) {
        if(root==null) return new int[]{0,0};
        int[] status = new int [2]; // 不考虑自身时能获得的最大值，考虑自身时能获得的最大值
        int[] left = traversal(root.left);
        int[] right = traversal(root.right);
        status[0] = left[1]+right[1];
        status[1] = Math.max( left[1]+right[1], root.val+left[0]+right[0]);
        return status;
    }
}

股票问题

股票问题常常增加状态的维度

123. 买卖股票的最佳时机 III
这题比较难，很关键的一点就在于一定要定义清楚状态，不能把第一次交易和第二次交易混在一起，第二次交易一定是在第一次交易结束的时候进行的。

300. 最长递增子序列

这题的贪心解法很有意思，也很难想。

最长递增子序列

贪在让子序列最后一个元素最小，让 minTail[i] 为所有长度为 i 的子序列中最小的尾元素。

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 贪心
        // minTail
        int n = nums.length;
        int[] minTail = new int[n];
        int len = 1;
        minTail[0] = nums[0];
        for(int i = 1; i<n; i++) {
            if(nums[i]>minTail[len-1]) {
                minTail[len++] = nums[i];
            }
            else {
                int idx = find(minTail,0,len-1,nums[i]);
                minTail[idx+1] = nums[i];
            }
        }
        return len;
    }
    public int find(int[] array, int start, int end, int num) {
        while(start<end) {
            int mid = (end-start+1)/2+start;
            if(array[mid]<num) {
                start = mid;
            }
            else {
                end = mid-1;
            }
        }
        if(array[start]>=num) return -1;
        return start;
    }
}

字符串二维 dp

1143. 最长公共子序列

拼多多一面原题

1143. 最长公共子序列

他妈我是真服了你个废物，明明718. 最长重复子数组一下就写出来了，这题基本一样写老半天。

他妈是真服了，这种题就得动态规划做，整那种花里胡哨的就等死吧。

和以前做的题很不一样的是这种匹配问题关键就是这种都是 二维dp。

状态转移的关键不再是判断一维状态是否相等了，而是二维各自的元素是否相等了，一共两种状态。

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n1 = s1.length();
        int n2 = s2.length();
        int [][] dp = new int[n1+1][n2+1];
        int ans = 0;
        for(int i = 0; i<n1; i++) {
            for(int j = 0; j<n2; j++) {
                if(s1.charAt(i)==s2.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                }
                else {
                    dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
                }
                ans = Math.max(ans, dp[i+1][j+1]);
            }
        }
        return ans;
    }
}

72. 编辑距离

72. 编辑距离
编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。

编辑距离是一系列经典题目，很多二维dp题都由编辑距离改编而来，重中之重。

这题的关键在于 虽然说是让 word1 向 word2 靠齐，也就是字面意义的 word2 不能改，但在逻辑上是可以改的，word1 插入一个最合适的数等效于 word2 删除一个数，毕竟在 dp 过程中是肯定不能在word1 显式插入一个数字的。

妈的就倒在这了，只考虑word1删除和替换元素，甚至考虑到如果 word1 比 word2 短就反过来执行程序。

唉，so close。

关键：对两个单词计算编辑距离，插入与删除等价！

这样一来，本质不同的操作实际上只有三种：
在单词 A 中删除一个字符；
在单词 B 中删除一个字符；
修改单词 A/B 的一个字符。

回文 dp

5. 最长回文子串 许多回文题基本都很相似，可以用 dp 做， 也可以用 中心扩展法（双指针法）做，还有 Manacher 算法。

中心扩展法 空间性能比 DP 更好，关键就是 首先回文串要么是偶数长度要么是奇数长度，而区分不同回文串的要点除了回文串的内容，还有就是回文串的中心（这个中心更具体地是指中心在原字符串中所处的位置），因为当回文中心不一样时也算不同的回文子串，计算 回文子串数目 或者 回文子串长度 都是不影响的。

那接下要做的就是遍历所有的回文中心，获得这个中心能向外扩展得到的偶数长奇数长回文子串，故谓中心扩展。当然这里的回文中心是广义的，因为偶数长回文子串肯定是由起始长度为2的回文中心向外扩展而来的。

写法是：

for(int i = 0; i<n; i++) {
    for(int j = 0; j<=1; j++) {  // j 为0， 奇数长； j 为1， 偶数长
        int l = i;
        int r = i+j;
        while(l>=0 && r<n && ch[l]==ch[r]) {
            if(r-l+1>maxLen) {
                left = l;
                right = r;
                maxLen = r-l+1;
            }
            l--;
            r++;
        }
    }
}

单调栈

什么时候用单调栈呢？

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

654. 最大二叉树

图解讲的很清楚

这题用单调栈
边遍历数组边构造树只遍历一次，真的太精妙了。
感觉关键就在于：
1、有大小的比较
2、入栈元素可能是我的右节点，也可能我(栈顶)或者我下面的一些都属于它的左子树。一切都是根据大小的比较。
最难的就是想到边形成单调栈边构造，我一直以为单调栈是生成完了才用，和单调队列一样。

下一个更大元素 I

496. 下一个更大元素 I

自己写出单调栈了哈哈

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> hmap = new HashMap<>();
        Stack<Integer> stk = new Stack<>();
        int tmp;
        int [] ans = new int[nums1.length];
        for(int i = 0; i< nums2.length; i++) {
            while(!stk.empty() && stk.peek()<nums2[i]) {
                tmp = stk.pop();
                hmap.put(tmp, nums2[i]);
            }
            stk.push(nums2[i]);
        }
        for(int i = 0; i< nums1.length; i++) {
            ans[i] = hmap.containsKey(nums1[i])? hmap.get(nums1[i]) : -1;
        }
        return ans;
    }
}

739. 每日温度

739. 每日温度

第一次做到存储下标的，之前都是直接存储数，还是看需求的，必须这题的需求就是两个数索引的差。

42. 接雨水

42. 接雨水 一开始我是用类dp法写的，比较简单。

这题的单调栈法很不错，有种一层层往上加的感觉，原理就是栈里保存比栈顶大的，然后遍历过程中遇到比当前栈顶大的，那么对这个栈顶来说就已经是一个坑了，可以装水。

双指针法有点难，关键是只需要知道左右两边比自己高的两个柱子中比较低的一个，所以当左边/右边出现了一个比现在明确的真正意义上的右边/左边最大高度柱子时，当前位置能接的水量也就知道了。

int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);
    // 对 left 来说，leftMax 是明确的真正意义上的左边最大高度
    if (leftMax < rightMax) {
        ans += leftMax - height[left];
        ++left;
    // 对 right 来说，rightMax 是明确的真正意义上的左边最大高度
    } else {
        ans += rightMax - height[right];
        --right;
    }
}
return ans;

84. 柱状图中最大的矩形

84. 柱状图中最大的矩形

看看我的题解

图

图的遍历 讲的不错。

// N叉树
public void dfsTree(Tree root) {
    if (root == null)
        return;
    // 访问当前节点，不一定放在这，也可以放到其他地方
    System.out.println(root.val);
    for (int i = 0; i < root.子节点个数; i++) {
        dfsTree(root.第i个子节点);
        // 如果需要回溯，这里要撤销选择
    }
}

// 对于矩阵的访问我们可以把它看做是一棵 4 叉树的前序遍历
// 如果是矩阵，需要访问和他挨着的上下左右4个方向，(x,y)是当前位置的坐标。
public void dfsMatrix(int[][] matrix, boolean[][] visited, int x, int y) {
    // 首先不能越界。
    if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length)
        return;
    // 如果当前位置被访问过，就不要在重复访问，直接跳过。
    if (visited[x][y])
        return;
    visited[x][y] = true;// 先标记，表示当前位置被访问过。
    // 访问当前位置的上下左右4个方向，也可以像BFS中使用for循环来访问他的4个方向。
    dfsMatrix(matrix, visited, x - 1, y);//上
    dfsMatrix(matrix, visited, x + 1, y);//下
    dfsMatrix(matrix, visited, x, y - 1);//左
    dfsMatrix(matrix, visited, x, y + 1);//右
    // 递归之后还要往回走，如果需要回溯这个位置要还原，
    // 如果不需要回溯，下面这行代码就不要写。
    visited[x][y] = false;
}

广搜： 广搜的搜索方式就适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。

当然，也有一些问题是广搜 和 深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。

只要BFS只要搜到终点(搜到的一瞬间)一定是一条最短路径，不管有没有障碍。DFS 应该是需要遍历完所有的路径并维护最短路径。

一圈一圈的搜索过程是怎么做到的，是放在什么容器里，才能这样去遍历？

很多网上的资料都是直接说用队列来实现。

其实，我们仅仅需要一个容器，能保存我们要遍历过的元素就可以，那么用队列，还是用栈，甚至用数组，都是可以的。

用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。

因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。

如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。

因为栈是先进后出，加入元素和弹出元素的顺序改变了。

那么广搜需要注意转圈搜索的顺序吗？ 不需要！

所以用队列，还是用栈都是可以的，但大家都习惯用队列了，所以下面的讲解用我也用队列来讲，只不过要给大家说清楚，并不是非要用队列，用栈也可以。

200. 岛屿数量

flood fill 算法，水漫算法，相当于用每种颜色填充每一个连通块。

200. 岛屿数量 好难

难在想到每次处理一个岛屿，只处理所有连成一片的 1 。

广搜难在需要注意到：是加入队列时进行标记访问过这个点，而不是出队的时候进行标记。
这取决于我们对 代码中队列的定义，队列中的节点就表示已经走过的节点。 所以只要加入队列，立即标记该节点走过。

并查集解法

已经完全解析了，看注释吧。

class UnionFind {
    int count;
    int[] parent;

    public UnionFind(char[][] grid) {
        count = 0;
        int m = grid.length;
        int n = grid[0].length;
        parent = new int[m * n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    parent[i * n + j] = i * n + j;
                    ++count;
                }
            }
        }
    }

    public int find(int i) {
        // 路径压缩
        if (parent[i] != i) parent[i] = find(parent[i]);
        return parent[i];
    }

    public void union(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {  // 不在一个集合，如果已经在一个集合的话不会再次操作，也就不会再次减 count
            parent[rootx] = rooty;
            --count;
        }
    }

    public int getCount() {
        return count;  // 比如总共五个 1 ，会拉四个集合，每拉一个 union count 自减一次，所以能得到岛屿数
    }
}

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }

    int nr = grid.length;
    int nc = grid[0].length;
    int num_islands = 0;
    UnionFind uf = new UnionFind(grid);
    for (int r = 0; r < nr; ++r) {
        for (int c = 0; c < nc; ++c) {
            if (grid[r][c] == '1') {
                grid[r][c] = '0';  // 减少一点 union 操作次数，对结果不影响 
                // 换句话说是表示这个 1 已经完成了它的使命，把所有与它相连的 1 都拉到集合里面了，这些 1 后面没必要再访问它
                // 当然，由于集合的性质，不改为0，后面访问了也没关系，count不会再减了
                if (r - 1 >= 0 && grid[r-1][c] == '1') {
                    uf.union(r * nc + c, (r-1) * nc + c);
                }
                if (r + 1 < nr && grid[r+1][c] == '1') {
                    uf.union(r * nc + c, (r+1) * nc + c);
                }
                if (c - 1 >= 0 && grid[r][c-1] == '1') {
                    uf.union(r * nc + c, r * nc + c - 1);
                }
                if (c + 1 < nc && grid[r][c+1] == '1') {
                    uf.union(r * nc + c, r * nc + c + 1);
                }
            }
        }
    }
    return uf.getCount();
}

并查集

并查集常用来解决连通性问题。

大白话就是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。

并查集主要有两个功能：

将两个元素添加到一个集合中。
判断两个元素在不在同一个集合

并查集理论基础 讲的不错

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程  Java 写法
int find(int u) {
    if (parent[i] != i) parent[i] = find(parent[i]);
        return parent[i];
}


// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

注意，join 函数中前三行和 isSame 函数是重复的，但这三行绝对不能用通过调用 isSame 函数来替换，因为下一行的 father[v] = u 表示的意思是让 v 的 根 指向 u的 根，这样才能通过单向的连接就能表示两个元素的相连。否则单单 father[v] = u 的意思就是让 v 指向 u ，比如：

join(1, 2);
join(3, 2);

这是用 isSame 替换，此时无法表示 1 与 3 在一个集合里。

这是不用 isSame 替换，此时可以表示 1 与 3 在一个集合里。

join(u, v) 的含义就是 v 的根（或者叫头）指向 u 的根（或者叫头）。这点和上面的那个易错点是很关连的。

还有：路径压缩 // 验证过了
路径压缩会在寻根的漫长过程中，把这条路径上的所有非根节点的父节点全都设为最前端的根节点，只要这条路径跑一次，基本都会重设父节点，这些子节点都会直接挂载到根节点下面。

注意看：无论使用并查集模板里哪一个函数（除了init函数），都会有路径压缩的过程（因为里面都调用了 find 函数），第二次访问相同节点的时候，这个节点就是直连根节点的，即 第一次访问的时候它的路径就被压缩了。

路径压缩后的并查集时间复杂度在O(logn)与O(1)之间，且随着查询或者合并操作的增加，时间复杂度会越来越趋于O(1)。
在第一次查询（find）的时候，相当于是n叉树上从叶子节点到根节点的查询过程，时间复杂度是logn，但路径压缩后，后面的查询操作都是O(1)，而 join 函数 和 isSame 函数里涉及的查询操作也是一样的过程。

拓展

在「路径压缩」讲解中，我们知道如何靠压缩路径来缩短查询根节点的时间。

其实还有另一种方法：按秩（rank）合并。

rank表示树的高度，即树中结点层次的最大值。

为防止两颗树合并后整棵树的高度变的更高，一定是 rank 小的树合入 到 rank大 的树（比较矮的树合入比较高的树），这样可以保证最后合成的树rank 最小，降低在树上查询的路径长度。

按秩（rank）合并不需要路径压缩，因为一旦做路径压缩，rank记录的高度就不准了，根据rank来判断如何合并就没有意义。

其实我们在优化并查集查询效率的时候，只用路径压缩的思路就够了，不仅代码实现精简，而且效率足够高。
按秩合并的思路并没有将树形结构尽可能的扁平化，所以在整理效率上是没有路径压缩高的。

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector father = vector (n, 0); // C++里的一种数组结构
vector rank = vector (n, 1); // 初始每棵树的高度都为1

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
        rank[i] = 1; // 也可以不写
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : find(father[u]);// 注意这里不做路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根

    if (rank[u] <= rank[v]) father[u] = v; // rank小的树合入到rank大的树
    else father[v] = u;

    if (rank[u] == rank[v] && u != v) rank[v]++; 
    // 如果两棵树高度相同，则v的高度+1，因为上面 if (rank[u] <= rank[v]) father[u] = v; 注意是 <=
}

疑难

300 动态规划、二分查找解法

105 106从前序与中序遍历序列构造二叉树 迭代法很恶心

812. 最大三角形面积 凸包问题

77. 组合 字典序法解决组合枚举

491. 非递减子序列 回溯去重
这个回溯去重真看不懂

332. 重新安排行程 Hierholzer 算法

ACM模式

import java.util.Scanner;
class climbStairs{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int m, n;
        while (sc.hasNextInt()) {
            // 从键盘输入参数，中间用空格隔开
            n = sc.nextInt();
            m = sc.nextInt();

            // 求排列问题，先遍历背包再遍历物品
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int j = 1; j <= n; j++) {
                for (int i = 1; i <= m; i++) {
                    if (j - i >= 0) dp[j] += dp[j - i];
                }
            }
            System.out.println(dp[n]);
        }
    }
}

参考资料

CS-Notes

代码随想录

算法通关手册（LeetCode）

深入理解递归