Xuanyi Fu Blog

• 指针使用前，一定要检查指针是否是nullptr。
• 善用dummyNode
• 链表操作三板斧：slice, transform, splice 裁剪，变换，拼接
• 裁剪下来的节点，一定要设置next为nullptr。

链表逆序：
LC206 Reverse Linked List
⚠️LC92 Reverse Linked List II[用dummyHead更容易处理m == 0的情况]
链表删除：
LC237 Delete Node in a Linked List[靠拷贝后一个节点的val来做删除]
LC19 Remove Nth Node From End of List[无论如何也要遍历，裁拼]
LC203 Remove Linked List Elements[删除给定值的节点，裁拼]
LC83 删除排序链表中的重复元素[裁变拼]
⚠️LC82 删除排序链表中的重复元素II[要求将重复元素全部清除，需要维护两个指针]
链表求环：
LC141 Linked List Cycle
LC142 Linked List Cycle II[环长为相遇时慢指针移动的步数]
LC287 Find the Duplicate Number[相等的是first/slow，返回的也是first/slow]
链表归并/排序：
LC21 Merge Two Sorted Lists
LC23 Merge k Sorted Lists
LC147 对链表进行插入排序
⚠️⚠️LC148 排序链表
其他：
❌LC24 两两交换链表中的节点
❌LC143 重排链表
LC138 复杂链表复制
LC725 分隔链表
LC160 两个链表的公共节点
❌LC24 K个一组翻转链表
LC1171 从链表中删去总和为零的连续节点
LC430 扁平化多级双向链表

• begin到first的区间[begin, first)是否对于一个特性是单调的？last到end的区间[last,end)是否针对一个特性是单调的？
• 是否已知区间的范围？如果不知道，是否可以用单边二分查找来先确定范围？

二分查找三基础：
LC35 Search Insert Position
LC704 Binary Seach
LC34 Find First and Last Position of Element in Sorted Array
[equal_range —> 将 lower_bound中的!(*mid < target)分解为 小于：target < *mid 和 等价：!(*mid < target) && !(*mid > target)，将等价的区间分为[first, mid)和[mid, last)，再在前面做lower_bound后面做upper_bound。
简单二分查找：
LC278 第一个错误的版本 单边二分。注意下标溢出。记录上一次badVersion的位置，缩小二分区间。
剑指53 - II 0到n-1中缺失的数字
⚠️LC1060 有序数组上缺失的数字 [设计一个函数计算到目前为止缺失的元素个数，记得要找lower_bound前一个元素（最后一个不大于）]
剑指53 - III 数组中数值和下标相等的元素[小心size_t和int的大小比较]

峰值数组：
LC1095 山脉数组中查找目标值
LC162 寻找峰值

旋转数组：
LC153 Find Minimum in Rotated Sorted Array
LC154 Find Minimum in Rotated Sorted Array II [有重复数字，遇到重复直接线性查找]
LC33 Search in Rotated Sorted Array [想要在旋转数组上找某个数字]
矩阵查询：
LC74 Search a 2D Matrix [展开为一维/两次二分/线性]
LC240 Search a 2D Matrix II [线性/对角线二分]
困难二分查找：
⚠️LC4 排序数组的中位数
⚠️LC410 分割数组的最大值
⚠️LC162 寻找峰值
LC222 完全二叉树的节点个数
数学二分：
LC96 Sqrt(x)
LC878 第N个神奇数字

popcount类问题：
LC191 Number of 1 bits (Hamming Weight)
LC338 Counting bits
LC231 2的整数次幂 除了0和负数，(n & (n - 1)== 0)的是2的整数次幂。
⚠️LC477 汉明距离总和 统计每一位0或1的个数为t，总共有n个数，则该位贡献的汉明距离为t * (n - t)

异或：
LC421 数组中两个数的最大异或值
LC1310 子数组异或查询
LC1442 形成两个异或相等数组的三元组数目

异或找数：
LC136 Single Number全部与一下即可
LC137 Single Number II全部与，找一位是1的做partition，再分别与
LC260 Single Number III 统计每一位，mod3，再恢复
LC268 缺失的数字 原序列和[1…n]序列做位与

其他：
LC371 两整数之和
LC50 快速幂位与左移是进位，异或是不带进位的加法
LC190 Reverse Bits[32位都要与到]
⚠️LC201 数字范围按位与 右移到相等，再左移回来。
IP到CIDR