算法基础思维——附带题单

双指针、滑动窗口、二分、位运算、前缀和（下划线内是例题的链接
）

双指针

注意处理边界情况

1. 解决数组中复写数字 复写0

   • 先考虑异地操作。
   • 然后尝试原地操作来进行优化。

2. 简单的数组区间维护 移动0

   • 两个指针分别指向区间的开始和末尾 。

3. 判断是否有循环的问题 环状链表Ⅱ

   • 快慢指针，如果有循环，由于两个指针有速度差异，那么两个指针迟早会相遇

4. 利用双指针移动的变化规律处理区间极值问题 盛最多水的容器

5. 三个数之间的判断 四数之和

   • 一般都是先排序，然后利用单调性来解决。

滑动窗口 —— 同向双指针

求解的过程就是更新窗口的过程

1. 连续子数组的值问题。 无重复的最长子串

2. 最大连续 1 的个数III

3. 找到字符串中所有字母异位词

4. 最小覆盖子串

二分

查找区间首未问题

口诀：

1. 谁的区间内可能存在正确答案，谁的更新策略就带等号。
2. 左端左中点，右端右中点
3. 左加右减

求中点

• left + (right -left)/ 2 最后剩余偶数（两个）元素的时候，取左边的那一个元素。
• left + (right - left +1)/2 最后剩余偶数（两个）的时候，取右边的那一个元素。

求区间左端点

• 使用条件：left < right
• 计算公式：mid = left + (right - left) / 2
• 更新策略：
  • 如果mid < tar，则left = mid + 1
  • 如果mid >= tar，则right = mid

求区间右端点

• 使用条件：left < right
• 计算公式：mid = left + (right - left + 1) / 2
• 更新策略：
  • 如果mid <= tar，则left = mid
  • 如果mid > tar，则right = mid - 1

例题

1. 消失的两个数字,结合下标和二分

反证

1. 将x减小到0的最小操作数

位运算

^ 异或运算符(无进位相加)。
~ 取反运算符

常见情况

1. 确定某一位(n)是0还是1
   • (num>>n)&1
2. 将一个数的第n位的二进制修改为1
   • num|（1<<n）
3. 将一个数的第n位的二进制修改为0
   • num&(~(1<<n))
4. 提取一个数,二进制表示中最右侧的1
   • num&(-num)
   • (-num)的操作，会将最右侧的1的左边区域全部变为相反数。
5. 将一个数,二进制表示中最右侧的1变为0
   • num & (num-1)

位图思想

利用一个数的二进制位来记录信息

异或运算规律

1. num^0 = num
2. num^num = 0（偶数消消乐）
3. a^b^c = a^(c^b)

前缀和（常常需要多添加一行一列来解决边界问题）

一维前缀和：dp[i] = dp [i-1] + nums

矩阵前缀和：画图计算即可（下图中ret为右下角矩阵的大小），其中坐标的计算为了防止越界，可以采用例如

1. 解决连续的子数组的值的问题。 和为 k 的子数组

2. 连续数组

3. 矩阵区域和