常见的算法技巧
常见算法思路
1.滑动窗口
2.双指针
3.二分查找
4.优先级队列
5.单调栈
a. 说明
单调栈: 分为单调递增栈和单调递减栈. 单调递增栈即栈内元素保持单调递增的栈. 同理单调递减栈即栈内元素保持单调递减的栈
b. 模型:
单调递增栈: a.如果新的元素比栈顶元素大，就入栈. b.如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小 单调递减栈: a.如果新的元素比栈顶元素小，就入栈. b.如果新的元素较大，那就一直把栈内元素弹出来，直到栈顶比新元素大
c. 特性: 以递增栈举例
- 栈内的元素是递增的
- 当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素
- 当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素
d. 代码片段
// 定义一个单调递增栈
Stack<Integer> stack = new Stack<>();
// 遍历元素
for(int i = 0; i < nums.size(); i++)
{
// 如果新元素小于栈顶元素, 栈顶元素出栈, 直到合适为止
while(!st.empty() && st.top() > nums[i])
{
st.pop();
}
// 入栈
st.push(nums[i]);
}
e. 示例
// todo
f. 常见算法题
6.单调队列
7.数学公式
7.1 快速幂思想
7.2 牛顿方程
8. 回溯算法
9. 数组hash
10. 动态规划
a. 说明 b. 模型
- 原地hash
- 额外hash
c. 常见算法题
10. 位运算
常见数据结构
文档信息
- 本文作者：寒澈
- 本文链接：https://www.hancher.top/wiki/algorithm_skill/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）