算法心得
2023-07-06 11:38:38 0 举报AI智能生成
11111
作者其他创作
大纲/内容
解题逻辑
先暴力，后优化
优化瓶颈处
🌰
lc 1 先两层循环
lc 11 先两层循环
先简化，后复杂
🌰
lc 20 先简化一种括号
理解视角
具体
带入具体数字
抽象
跳出具体数字，看代码框架和整体逻辑
数据结构
数组
static array
使用场景
当数量比较少的时候，可以用数组计数
dynamic array
使用场景
数据流
实现方式
List<Integer> list = new ArrayList<>();
链表
注意
null也是一步
什么时候从0开始遍历，什么时候从1开始遍历
哈希
HashMap
使用场景
键值对：需要记录两个数据
快速查找某个东西
统计次数/词频
347
HashSet
使用场景
去重
此时，可以与boolean[]互换
等值查找
不需要key
记录是否访问过
Deque
使用场景
FIFO
queue
FILO
stack
stack
monotonic stack
使用场景
第一个大于/小于的元素
一个普通栈
使用场景
括号
heap/pq
使用场景
快速得到最大最小值
Kth
最大值
使用小顶堆，因为小顶堆里储存的反而是最大值
最小值
使用大顶堆，因为大顶堆里储存的反而是最小值
tree
解题思路
树：遍历
dfs
recursion
写法
整体框架完全一样
换了换res.add的位置
symmetrical recursion
定义
dfs(root.left)
dfs(root.right)
使用场景
不需要辅助方法
利用树的左右子树就可以做出来
辅助方法（需要超过一个变量）
树的左右子树特性
另外一个变量
iteration
本质上
用外显栈模拟递归的隐性系统栈
写法
前（序）后（序）相反
先stack.push(root) 再while
中（序）不同
先while (!stack.isEmpty() || curr != null)，再stack.push(root)
bfs
iteration
本质上
用队列实现
BST：中序遍历
preorder
特点
top-down
只能从函数参数中获得父亲节点传递来的数据
preorder（root, 1）
使用场景
inorder
特点
对于BST，结果是一个升序数组
postorder
特点
bottom-up
能从函数参数中获得父亲节点传递来的数据
traverse（root, 1）
获得子树通过函数返回值(return)传递回来的数据
使用场景
只有后序位置能返回子树信息
543. diameter of binary tree
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 后序位置，顺便计算最大直径
int myDiameter = leftMax + rightMax;
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 后序位置，顺便计算最大直径
int myDiameter = leftMax + rightMax;
unionfind
使用场景
检测无向图中是否有环
TreeMap
使用场景
key是排序排列的hashmap
需要hashmap的key有序时
算法
查找算法
线性查找
实现方式
循环遍历
二分查找
使用场景
有序
完全有序
部分有序
无序且不需要返回index
实现方式
不断在循环体内查找目标元素
在循环体中排除一定不存在目标元素的区间
二叉树查找
哈希查找
常用数据结构
HashSet
HashMap
当数量比较少的时候，可以用数组计数
leetcode 169
two pointer
快慢指针
使用场景
linked list
find a cycle
对撞指针
使用场景
回文串
有序数组的求和
two sum II
排序
奇偶性
905
922
衍生情况
three pointers
滑动窗口
使用场景
满足条件的最长窗口
满足条件的最短窗口
满足指定长度的数据
通常基于数组，因为数组有索引
实现方式
two pointers
排序算法
quick sort
基本快排
本质
把与pivot相等的放在任意一栏
two-way
本质
把与pivot相等的平均分在大于或小于的部分
context
移动0
three-way
本质
把与pivot相等的单独列出一部分
对比
merge sort
counting sort
Dijkstra算法
使用场景
无向有权图
sweep line
使用场景
调度类
会议室
divide and conquer
本质
先解决子问题
再将子问题合并得出答案
实现方式
递归
递归终止条件 base case
每个问题可以划分为两个子问题
子问题的解决方案和大问题一样
🌰
merge sort
回溯算法
本质
暴力穷举，尝试各种可能
DFS + 剪枝
使用场景
组合/子集
本质
组合：元素大小为k的子集
实现方式
通过startIdx+1来避免重复的子集
排列
实现方式
nums[i]可以出现左边的元素，所以不能startIdx + 1
切割
棋盘
实现方式
遍历每一层
for循环
逐层深入
递归
dfs前做了什么，dfs后就取消什么
path.add()
path.remove()
贪心算法
使用场景
每一步都有最优解
每一步不会影响后面的操作
无后效性
动态规划
3个特征
重复子问题
状态数组
无后效性
最优子结构
子问题间相互独立
使用场景
1.求最优解，且最优解能通过暴力穷举得到
2.在暴力穷举的过程中，存在重复计算
与回溯区别
回溯求最优解具体是什么
硬币：5 5 1
动态规划是求最优解的值
硬币：需要3枚
BFS
使用场景
最短路径
🌲的最小深度，就是最少的层数
层序遍历
最左边/最右边的节点
最短时间
拓扑排序
使用场景
检测有向无环图中是否有环
要排序的元素间有依赖关系
本质
BFS和greed在有向无环图中的应用
逻辑
BFS加上区分每一层，变成了层序遍历
层序遍历加上了层数（表时间或路径），变成了最短路径问题
DFS
使用场景
最远距离
子主题
实现方式
递归
迭代
栈（显性）
104
常用函数
string<->char
实现方式
第一种
s.charAt(i)
第二种
先转化成char[]
char[] ch = s.toCharArray()
再转化成char
char c = ch[i]
使用场景
string char 转化
进一步表示先后顺序
order[s.charAt(i) - 'a'] = i
Arrays.sort()
使用场景
数据预处理
需要比较最大最小差
二分法
Math.max/min
使用场景
数轴场景下，可用于跳跃
相当于遍历
list.toArray()
57题
convert to String
String.valueOf()
使用场景
任何数据类型转化成string
Arrays.toString()
Integer.toString()
Stack.toString()
Array-based to Collection-based
Arrays.asList()
收藏
职业：暂无
0 条评论
下一页
