算法总结
2023-06-06 15:19:39 6 举报AI智能生成
数据结构与算法，leetcode刷题笔记
作者其他创作
大纲/内容
基础数据结构
1. 双指针
1. 快慢指针
1.1 链表问题
141.环形链表
142.环形链表2
160.相交链表
19.删除链表的倒数第n个节点
21.合并两个有序链表
23.合并k个有序链表
876.链表的中间节点
1.2 数组
26.原地删除数组中的重复项
2. 左右指针
1. 二分查找
167.两数之和
344.反转数组
5.最长回文子串： 从中心 --> 两端
66.剑指offer-52.两个链表的第一个公共节点
3. 滑动窗口
5.最长回文子串
76.最小覆盖子串
567.字符串的排列
438.找到字符串中所有字母异位词（排列）
3.无重复字符的最长子串
1477.找到和为目标值且不重叠的子数组
771.字符串中最长的连续出现的字符
799.最长连续不重复子序列
800.数组元素的目标和
4. 二分搜索
4.1 寻找一个数
4.2 寻找左右边界
2. 前缀和 && 差分数组
2.1 前缀和 preSum [n + 1]
原理
preSum[i] = num[i - 1] + preSum[i - 1]
2.1.1 一维数组
2.1.2 二维数组
2.2 差分 diff[ n ]
原理
多次、区间内的、加减操作（比如航班预定、公交车等问题）
[l, r]：diff[l] += k， diff[r + 1] -= k
计算原数组的某个值：a[i] = diff[i] + a[i-1]
计算原数组：对diff数组求前缀和
应用
1094.拼车
1109.航班预定系统
5. 单调栈
6. 单调队列
二叉树
1. 通用思路
分析题目，选择算法
1. 是否可以通过遍历一遍得到答案？—— 外部变量 + void dfs()
2. 是否可以定义一个dfs，设计返回值，通过子问题推导出答案？int dfs()
ps：如何设计？：单独一个二叉树节点，它需要做什么事情？需要在什么时候做？（前/中/后序位置）
ps：注意baseCase！
算法1：遍历思维
297.序列化与反序列化二叉树
算法2： 分解子问题思维
1. 最值问题（利用后序位置）
104. 最大深度、543直径
124. 最大路径和
687. 最大同值路径
652. 寻找重复的子树
2. 构造新的二叉树
654. 最大二叉树
105. 前中序序列构造二叉树
106. 后中序序列构造二叉树
889. 前后序序列构造二叉树
2. BST二叉搜索树
原理
左节点 < 根 < 右节点
中序遍历序列：升序
复杂度：logN
应用
1038.从BST到更大和树
230.从BST中第K小的元素
538.把BST转换为累加树
450.删除BST树中的节点
700.BST中的搜索
701.BST中的插入操作
98.验证BST树
3. 归并排序
原理
二分 + 二叉树后序遍历 + merge合并（双指针）
应用
912.排序数组
315。计算右侧小于当前元素的个数
493.翻转对
327.区间和的个数
回溯与BFS
回溯
原理
1. 维护【选择列表】（可以通过boolean数组记录状态）
2. 前序位置：做选择
3. 后序位置：撤销选择
4. 结束条件：添加结果、可以提前返回、累加次数等
应用
46.全排列
51.N皇后
52.N皇后2
数学形式
1. 组合问题（子集）
标准框架
场景
无重复元素：backtrack（nums, i+1）
有重复元素：要排序，再剪枝
1. 先对nums排序
2. 剪枝：如果发现 nums[i] == nums[i-1] ，则跳过
无重可复选
backtrack（nums, i）
base case：trackSum > target, return（因为重复选，不添加base case会无限循环）
应用
216.组合总和3
39.组合总和
40.组合总和2
77.组合
78.子集
90.子集2
2. 排列问题
场景
无重复元素
全排列：base case：track.size() == nums.length
k个元素全排：base case：track.size() == k
有重复元素
固定相同元素在排列中的相对位置，不同的排列即变成一种排列
if (i > 0 && nums[i] == nums[i-1] && !used[i-1])
无重可复选
去除boolean[] uesd 控制即可
应用
46.全排列
47.全排列2
BFS
动态规划
贪心
0 条评论
下一页
