🔥hot100-P2
树🌲
35.二叉树的中序遍历:递归/非递归
前序:根左右 中序:左根右 后序:左右根
36.二叉树的最大深度:递归
37.翻转二叉树:递归 交换
38.对称二叉树:递归 判断左右子树是否互为镜像
39.二叉树直径:链:node子树中叶子节点到node路径,拼node左右两条链长最大值为直径。DP
40.二叉树的层序遍历:Queue BFS
41.有序数组转换为二叉搜索树:二分得到两个小数组 递归
42.验证二叉搜索树:前序/中序遍历
43.二叉搜索树中第k小的元素:中序遍历找第k个节点
44.二叉树的右视图:先递归右子树,再递归左子树
45.二叉树转为链表:头插法 按右子树-左子树-根顺序DFS树
46.前序 中序 数组构造二叉树:前序:根左右 中序:左根右 分左右子树递归
47.路径总和III:哈希表统计根节点开始的路径和的出现次数,计算起点的次数
48.二叉树最近的公共次数:当前节点 null p q / 左右子树是否为空
49.二叉树中的最大路径和:DP 链 直径
图
50.岛屿数量:递归遍历上下左右并标记
51.腐烂的橘子:多源BFS Queue 四方向遍历
52.课程表:(有向图是否有环)建图 三色标记法
53.实现Trie(前缀树):构造26叉树(包含长26的子节点,和布尔值end/flag 标识变量判断是否为终止节点)。
回溯
选与不选:子序列排列型回溯:枚举选哪个
54.全排列:boolean []onPath标记选过没 再枚举path[i]填哪个的数
55.子集:选与不选
56.电话号码的字母组合:DFS + 枚举回溯
先写数字对应电话键盘字母常量数组 获取当前数字对应的字母串 当前数字对应的字母串
57.组合总数:选与不选 dfs中target == 0 说明找到了一个合法组合 加入path
58.括号生成:')' 数量==n 填完 '(' < n 填 '('')' < '(' 填')'
59.单词搜索:DFS + 回溯 上下左右 优化:可行性剪枝+顺序剪枝
60.分割回文串:DFS + 回溯
枚举字符串中所有可能的分割点(选 / 不选 i 和 i+1 之间的逗号),只保留 所有分割出的子串都是回文
61.N皇后:DFS + 回溯 逐行放置皇后
正斜线diag1[2 * n - 1] r + c反斜线diag2[2 * n - 1] r - c + n - 1
queens[r] = c 表示第 r 行的皇后放在第 c 列
col[c] = true 表示第 c 列已被皇后占用
二分
62.搜索插入位置:二分
63.搜索二维矩阵:从第一行最后一列排除法
64.在排序数组中查找元素的第一个和最后一个位置:
二分找第一个位置再找元素值+1的第一个位置下标再 -1 要判断能否找到
65.搜索旋转排序数组:
先找到旋转数组的最小值下标(旋转点),将数组拆分为两个升序的子数组
判断 target 属于哪个升序子数组,在该子数组中用二分查找找目标值。
66.寻找旋转排序数组中的最小值:二分中点值与最后一位值(nums[n-1])比较
67.寻找两个正序数组中位数:
将两个数组整体划分为左右两部分,左部分的所有数 ≤ 右部分的所有数;
a/b 对 nums1/nums2 的 “哨兵扩展数组”:头部加(-∞)、尾部加 (+∞),避免处理数组边界越界。
a[i] ≤ b[j+1] && b[j] ≤ a[i+1]
左部分的元素个数 = (m+n+1)/2(保证奇数长度时左部分多一个,直接取左部分最大值为中位数);
枚举 nums1 的分割点,推导 nums2 的分割点,找到满足 “左≤右” 的分割点后,计算中位数。
#算法#
35.二叉树的中序遍历:递归/非递归
前序:根左右 中序:左根右 后序:左右根
36.二叉树的最大深度:递归
37.翻转二叉树:递归 交换
38.对称二叉树:递归 判断左右子树是否互为镜像
39.二叉树直径:链:node子树中叶子节点到node路径,拼node左右两条链长最大值为直径。DP
40.二叉树的层序遍历:Queue BFS
41.有序数组转换为二叉搜索树:二分得到两个小数组 递归
42.验证二叉搜索树:前序/中序遍历
43.二叉搜索树中第k小的元素:中序遍历找第k个节点
44.二叉树的右视图:先递归右子树,再递归左子树
45.二叉树转为链表:头插法 按右子树-左子树-根顺序DFS树
46.前序 中序 数组构造二叉树:前序:根左右 中序:左根右 分左右子树递归
47.路径总和III:哈希表统计根节点开始的路径和的出现次数,计算起点的次数
48.二叉树最近的公共次数:当前节点 null p q / 左右子树是否为空
49.二叉树中的最大路径和:DP 链 直径
图
50.岛屿数量:递归遍历上下左右并标记
51.腐烂的橘子:多源BFS Queue 四方向遍历
52.课程表:(有向图是否有环)建图 三色标记法
53.实现Trie(前缀树):构造26叉树(包含长26的子节点,和布尔值end/flag 标识变量判断是否为终止节点)。
回溯
选与不选:子序列排列型回溯:枚举选哪个
54.全排列:boolean []onPath标记选过没 再枚举path[i]填哪个的数
55.子集:选与不选
56.电话号码的字母组合:DFS + 枚举回溯
先写数字对应电话键盘字母常量数组 获取当前数字对应的字母串 当前数字对应的字母串
57.组合总数:选与不选 dfs中target == 0 说明找到了一个合法组合 加入path
58.括号生成:')' 数量==n 填完 '(' < n 填 '('')' < '(' 填')'
59.单词搜索:DFS + 回溯 上下左右 优化:可行性剪枝+顺序剪枝
60.分割回文串:DFS + 回溯
枚举字符串中所有可能的分割点(选 / 不选 i 和 i+1 之间的逗号),只保留 所有分割出的子串都是回文
61.N皇后:DFS + 回溯 逐行放置皇后
正斜线diag1[2 * n - 1] r + c反斜线diag2[2 * n - 1] r - c + n - 1
queens[r] = c 表示第 r 行的皇后放在第 c 列
col[c] = true 表示第 c 列已被皇后占用
二分
62.搜索插入位置:二分
63.搜索二维矩阵:从第一行最后一列排除法
64.在排序数组中查找元素的第一个和最后一个位置:
二分找第一个位置再找元素值+1的第一个位置下标再 -1 要判断能否找到
65.搜索旋转排序数组:
先找到旋转数组的最小值下标(旋转点),将数组拆分为两个升序的子数组
判断 target 属于哪个升序子数组,在该子数组中用二分查找找目标值。
66.寻找旋转排序数组中的最小值:二分中点值与最后一位值(nums[n-1])比较
67.寻找两个正序数组中位数:
将两个数组整体划分为左右两部分,左部分的所有数 ≤ 右部分的所有数;
a/b 对 nums1/nums2 的 “哨兵扩展数组”:头部加(-∞)、尾部加 (+∞),避免处理数组边界越界。
a[i] ≤ b[j+1] && b[j] ≤ a[i+1]
左部分的元素个数 = (m+n+1)/2(保证奇数长度时左部分多一个,直接取左部分最大值为中位数);
枚举 nums1 的分割点,推导 nums2 的分割点,找到满足 “左≤右” 的分割点后,计算中位数。
#算法#
全部评论
相关推荐