【算法】算法思想合集

数组分块

1. 将数组分成具有某些特征的段
2. 使用双指针算法（如果是数组，使用下标充当指针）
3. 存在信息丢失的问题，可以考虑从后向前进行
4. 利用单调性进行定性分析（盛最多的水）
   滑动窗口
5. 同向移动的双指针
6. 出窗口一般是while
7. 必须具备单调性

二分查找

1. 如果left=mid，那么mid就应该是右边的
2. 如果right=mid，那么mid就应该是左边的
   这两点是为了防止取中的时候，left或right会在原地不动，造成死循环
3. 只要有二段性，就是根据各段的性质，对于mid位置进行判断，看其符合哪段的性质
4. 找二段性是非常重要的一环

前缀和

1. 和可被k整除的子数组：
   a. 同余定理：(a-b)%p = k —> a%k = b%k
   b. 负数 % 正数 修正为正数： ((a % p) +p ) % p
2. 前缀和需要考虑的特殊情况：
   a. 从后往前倒着来
   b. 可以不使用前缀和数组，而是使用hash表进行记录

位运算

1. 提取最低位1（low bit）
   a. n & (-n)
2. 干掉最低位1
   a. n & (n-1)
   本质就是低位的0减不动1，只能一直向前直到最低位的1才能开始减
3. 异或
   a. 三个数异或 就相当于给这三个数做无进位相加，就相当于给这三个数的1进行抵消，并且不考虑顺序问题

动态规划

1. 状态表示
   经验 + 题目要求：以 i 位置为结尾 / 开头，xxx
   明确 dp 的每个位置的含义。
2. 结尾：这个位置的状态不需要使用到后面的信息
   这种方式也可以使用 贪心
3. 开头：需要用到后面的信息
4. 状态转移方程
   以 i 位置最近的状态进行分析 i 位置的状态应该怎么来。
   就是 i-1，i-2 等位置的状态怎么能到 i。
5. 初始化
   dp 表需要明确最开始的几个状态，有了这几个状态，后续的才能开展。
6. 填表顺序
   状态的填充应该是从哪里到哪里。
7. 返回值
   题目中需要的是不是最后一个状态。

原文地址：https://blog.csdn.net/leadera_/article/details/142381632

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！