数据结构刷题总结
起始时间：2021.4.25
1.链表
链表类问题注意事项：
· 一般问题中如果头结点可能会发生变化的题目，需要定义虚拟头结点，来保证对头结点的操作不会影响整个链表；
AcWing 33.链表中倒数第k个节点
LeetCode 剑指 Offer 18. 删除链表的节点 （只删一个点，需要跳出循环）
LeetCode 203. 移除链表元素 (删多个点，跳过结点后不用跳出循环)
LeetCode 83.删除排序链表中的重复元素-简单(删除多余，保留一个)
LeetCode 61.旋转链表 （尽量简化求解过程，减少开销）
这题因为可以保留一个，不会完全删掉某类结点，所以不用虚拟头结点
4.LeetCode 82.删除排序链表中的重复元素-中等 II (重复元素全删)
这题会完全删除某类结点，所以需要虚拟头结点
2.数组
2.1 一维数组
1.LeetCode 137.只出现一次的数字 II（第一次只写了sort的方法时间复杂度nlogn）
2.LeetCode 26.删除有序数组中的重复项 (快慢指针，用慢指针表示删除后的数组)
3.LeetCode 80.删除有序数组中的重复项 II （同时要注意数组判空）
2.2 二维数组
1.LeetCode 73. 矩阵置零 （优化空间）
2.3174. 旋转 (顺时针旋转90°)
3.3212. 图像旋转（逆时针90°）
2.3 字符串/数组以及转换
1.LeetCode 179.最大数 （贪心，改写sort排序规则）
2.剑指 Offer 45.把数组排成最小的数 （把1的规则倒过来）
3.AcWing 1453.移掉K位数字 （贪心，每步最优解基于前一步最优解，dp是综合全部的局部最优解）
4.AcWing 445.数字反转 (两种解法：字符串/整数)
5.LeetCode 7.整数反转(用4中的整数解法)
6.AcWing 78.左旋转字符串 (字符串操作，主要使用pop_push(),或者用3次reverse)
7.AcWing 77.翻转单词顺序 （两次reverse）
3.栈
1.LeetCode 150. 逆波兰表达式求值 （后缀表达式求值）
2.3302. 表达式求值 (中缀表达式求值–模板题)
推演计算过程
3.LeetCode 1006.笨阶乘 （解法1使用双栈）
4.队列
5.树
LeetCode 226.翻转二叉树 (递归思想，类似前序遍历模板)
LeetCode 116.填充每个节点的下一个右侧节点指针 （递归思想）
LeetCode 100.相同的树 （递归思想）
剑指Offer 55-II.平衡二叉树 （递归）
LeetCode114.二叉树展开为链表 （迭代/递归）
LeetCode 94.二叉树的中序遍历(递归与非递归写法)
LeetCode 98.验证二叉搜索树
LeetCode 700.二叉搜索树中的搜索
LeetCode 701.二叉搜索树中的插入操作 （迭代与递归写法）
LeetCode 450.删除二叉搜索树中的节点 （相对复杂）
LeetCode 230.二叉搜索树中第K小的元素 (中序遍历-递归)
LeetCode 897.递增顺序搜索树
LeetCode 538.把二叉搜索树转换为累加树（从右子树开始的中序遍历）
AcWing 47.二叉树中和为某一值的路径 （二叉树深度优先遍历）
LeetCode 938.二叉搜索树的范围和 (深搜/广搜)
6.二进制/位运算
1.一些二进制位运算的变换操作
2.LeetCode 190.颠倒二进制位
3.LeetCode 191.位1的个数 (题解扩展)
4.LeetCode 461.汉明距离
5.LeetCode 338.比特位计数（题解）
6.AcWing 85. 不用加减乘除做加法 (参考的思想)
7.LeetCode 136.只出现一次的数字 (异或运算)
8.AcWing 73.数组中只出现一次的两个数字 (异或+位移运算)
9.LeetCode 137.只出现一次的数字 II （状态机分析 公式分析）
7.哈希表
1.AcWing 3192.出现次数最多的数 （简单题）
2.LeetCode 781. 森林中的兔子 (向上取整转向下取整证明过程 图解) （用来理解计算过程）
8.贪心
1.剑指 Offer 45.把数组排成最小的数
2.AcWing 1453.移掉K位数字 （贪心，每步最优解基于前一步最优解，dp是综合全部的局部最优解）
9.动态规划dp
LeetCode 279.完全平方数
AcWing 426.开心的金明
LeetCode 96.不同的二叉搜索树
10.结构体操作
11.逻辑题（脑筋急转弯）
LeetCode1736.替换隐藏数字得到的最晚时间（简单的if-else逻辑判断）
LeetCode 263.丑数
AcWing 62.丑数
LeetCode 781. 森林中的兔子
12.双指针
12.1 快慢指针
LeetCode 141.环形链表
LeetCode 142.环形链表 II
LeetCode 876.链表的中间结点
LeetCode 19.删除链表的倒数第N个结点
12.2 左右指针
LeetCode 633.平方数之和（左右指针）
LeetCode 167.两数之和 II-输入有序数组
LeetCode 344.反转字符串
13.二分
一般写二分的思考顺序是这样的：首先通过题目背景和check(mid)函数的逻辑，判断答案落在左半区间还是右半区间。
左右半区间的划分方式一共有两种：
1.中点mid属于左半区间，则左半区间是[l, mid]，右半区间是[mid+1, r]，更新方式是r = mid;或者 l = mid + 1;，此时用第一个模板；
2.中点mid属于右半区间，则左半区间是[l, mid-1]，右半区间是[mid, r]，更新方式是r = mid - 1;或者 l = mid;，此时用第二个模板；
模板1就是在满足chek()的区间内找到左边界，模板2在满足check()的区间内找到右边界。然后无论是左边界还是右边界，都应该是整个区间中某一段满足某性质（如单调不降）与另一段不满足该性质的分界点
应用版本一：LeetCode 275.H-Index II
应用版本二：LeetCode 69.Sqrt(x) ;
1.二分法的边界判断
2.LeetCode 153.寻找旋转排序数组中的最小值 末尾元素旋转到起始（类似右移）
3.LeetCode 154.寻找旋转排序数组中的最小值II (相比上题多了去除最右边重复元素)
3.AcWing 22.旋转数组的最小数字 起始元素旋转到末尾（类似左移）
4.LeetCode 33.搜索旋转排序数组 (所有元素互不相同，找出是否含有target，二次二分)
5.LeetCode81.搜索旋转排序数组II （存在相同元素，找出是否含有target，二次二分）相比于上题，多了一步去除最右边重复数操作，以及return的不同
6.AcWing 68.0到n-1中缺失的数字
7.LeetCode 278.第一个错误的版本
8.AcWing 680.剪绳子
9.LeetCode 1011.在D天内送达包裹的能力
10.LeetCode 5786.可移除字符的最大数目
二分法相关题目
14.处理较大数据
处理的数据可能很大时，一般在处理过程中的小步骤里就应该设法将其尽量减小，如1中对于大数的阶乘处理，
就可在计算阶乘的每一步中按题意尽可能减小化简，并保证不对结果产生影响。
