【算法】算法思想合集
数组分块
- 将数组分成具有某些特征的段
- 使用双指针算法（如果是数组，使用下标充当指针）
- 存在信息丢失的问题，可以考虑从后向前进行
- 利用单调性进行定性分析（盛最多的水）
滑动窗口 - 同向移动的双指针
- 出窗口一般是while
- 必须具备单调性
二分查找
- 如果left=mid，那么mid就应该是右边的
- 如果right=mid，那么mid就应该是左边的
这两点是为了防止取中的时候，left或right会在原地不动，造成死循环 - 只要有二段性，就是根据各段的性质，对于mid位置进行判断，看其符合哪段的性质
- 找二段性是非常重要的一环
前缀和
- 和可被k整除的子数组：
a. 同余定理：(a-b)%p = k —> a%k = b%k
b. 负数 % 正数 修正为正数： ((a % p) +p ) % p - 前缀和需要考虑的特殊情况：
a. 从后往前倒着来
b. 可以不使用前缀和数组，而是使用hash表进行记录
位运算
- 提取最低位1（low bit）
a. n & (-n) - 干掉最低位1
a. n & (n-1)
本质就是低位的0减不动1，只能一直向前直到最低位的1才能开始减 - 异或
a. 三个数异或 就相当于给这三个数做无进位相加，就相当于给这三个数的1进行抵消，并且不考虑顺序问题
动态规划
- 状态表示
经验 + 题目要求：以 i 位置为结尾 / 开头，xxx
明确 dp 的每个位置的含义。 - 结尾：这个位置的状态不需要使用到后面的信息
这种方式也可以使用 贪心 - 开头：需要用到后面的信息
- 状态转移方程
以 i 位置最近的状态进行分析 i 位置的状态应该怎么来。
就是 i-1，i-2 等位置的状态怎么能到 i。 - 初始化
dp 表需要明确最开始的几个状态，有了这几个状态，后续的才能开展。 - 填表顺序
状态的填充应该是从哪里到哪里。 - 返回值
题目中需要的是不是最后一个状态。
原文地址：https://blog.csdn.net/leadera_/article/details/142381632
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！