首页 > 其他分享 >leetcode刷题-归纳总结

leetcode刷题-归纳总结

时间：2024-06-11 18:56:21浏览次数：10  
标签：遍历 归纳 路径 DFS leetcode BFS 算法 节点 刷题

框架思维

124.求⼆叉树中最⼤路径和
后序遍历最大路径转换为为求单边最大路径
105.根据前序和中序遍历构造二叉树
前序遍历，找到根节点构建root，得到左右子树区间，左右子树递归构建
注意：1.终止条件 2.构建unordered_map
230.寻找⼆叉搜索树中的第 k ⼩的元素
⼆叉搜索树即左支树所有比根节点小，右支树比根节点大
中序遍历 就是从小到大排序

计算机算法本质就是穷举

1.⽆遗漏地穷举所有可能解
2.避免所有冗余的计算

数组

前缀和

1.前缀和主要适⽤的场景是原始数组不会被修，改的情况下，频繁查询某个区间的累加和。
2.为了方便处理边界首位添加0
303.区域和检索 - 数组不可变
前缀和，为了方便处理边界首位添加0
304.⼆维区域和检索 - 矩阵不可变
递归计算二维前缀和
为了处理边界，补0行，0列

差分数组

主要适⽤场景是频繁对原始数组的某个区间的元素进⾏增减
1109.航班预订统计
左边界 +value 右边界+1 - value ，注意右边界是否越界
1094.拼⻋

链表

双指针

21.合并两个有序链表
技巧是虚拟头结点dummy节点
86.分隔链表
关键要把大链表最后节点next置nullptr，避免出现环
23.合并K个升序链表
效率比较差，逐个合并2个链表；
效率比较高，优先队列；
19. 删除链表的倒数第 N 个结点
注意坑点，只有一个节点，删除完变空
增加dummy节点
876.链表的中间结点

快慢指针

142.环形链表 II
160.相交链表
26. 删除有序数组中的重复项
83.删除排序链表中的重复元素
27.移除元素
283.移动零

167.两数之和 II
有序数组 快速查找可以用二分法
二分查找模板

int binarySearch(int[] nums, int target) {
// ⼀左⼀右两个指针相向⽽⾏
int left = 0, right = nums.length - 1;
while(left <= right) {
  int mid = (right + left) / 2;
    if(nums[mid] == target)
      return mid;
    else if (nums[mid] < target)
      left = mid + 1;
    else if (nums[mid] > target)
      right = mid - 1;
}
return -1;
}

回文串

判断回文串用双指针
5.最⻓回⽂⼦串

滑动窗口

模板

nt left = 0, right = 0;
while (left < right && right < s.size()) {
// 增⼤窗⼝
window.add(s[right]);
right++;
while (window needs shrink) {
// 缩⼩窗⼝
window.remove(s[left]);
left++;
}
}

6.最⼩覆盖⼦串(hard)
567.字符串的排列
438.找到字符串中所有字⺟异位词

反转链表

206.反转链表
3个指针pre cur next
92.反转链表 II 反转区间链表
注意2个node left前对prenode和rightnode

队列/栈

20.有效的括号
注意最后stack为空才是true
921.使括号有效的最少添加
注意 stack不为空 需要加上这部分数目
1541.平衡括号字符串的最少插⼊次数
496.下⼀个更⼤元素
由于要保存比自己大的元素，逆着存入单调栈
739.每⽇温度
同下⼀个更⼤元素，只不过存下标
503.下⼀个更⼤元素II
239.滑动窗⼝最⼤值
优先队列priority_queue好理解 单调队列deque不好理解
316. 去除重复字⺟ （难以理解）

LRU（Least Recently Used）

146.LRU缓存机制」（难记）
380.常数时间插⼊、删除和获取随机元素
295. 数据流的中位数

二叉树

⼆叉树题⽬的递归解法可以分两类思路，第⼀类是遍历⼀遍⼆叉树得出答案，第⼆类是通过分解问题计算出答案，
这两类思路分别对应着 回溯算法核⼼框架 和 动态规划核⼼框架
遍历traverse 回溯backtrack 动态规划dp（dynamic programming)
动归/DFS/回溯算法都可以看做⼆叉树问题的扩展，只是它们的关注点不同：
动态规划算法属于分解问题的思路，它的关注点在整棵「⼦树」。
回溯算法属于遍历的思路，它的关注点在节点间的「树枝」。
DFS 算法属于遍历的思路，它的关注点在单个「节点」。
104.⼆叉树的最⼤深度
543.⼆叉树的直径(左右子树深度相加=改节点路径)
226.翻转⼆叉树
116.填充每个⼆叉树节点的右侧指针

层序遍历框架

层序遍历
queue<int> q;
Q.front() push() pop() empty() size()
// 初始化队列同时将第一层节点加入队列中，即根节点
        queue<Node*> Q;
        Q.push(root);
        
        // 外层的 while 循环迭代的是层数
        while (!Q.empty()) {
            
            // 记录当前队列大小，这块容易踩坑
            int size = Q.size(); 
            
            // 遍历这一层的所有节点
            for(int i = 0; i < size; i++) {
                
                // 从队首取出元素
                Node* node = Q.front();
                Q.pop();
                
                // 连接
                if (i < size - 1) {
                    node->next = Q.front();
                }
                
                // 拓展下一层节点
                if (node->left != nullptr) {
                    Q.push(node->left);
                }
                if (node->right != nullptr) {
                    Q.push(node->right);
                }
            }
        }

114.将⼆叉树展开为链表
105.从前序与中序遍历序列构造⼆叉树
106.从中序与后序遍历序列构造⼆叉树
652.寻找重复的⼦树

BST⼆叉搜索树（Binary Search Tree)

1对于 BST 的每⼀个节点 node，左⼦树节点的值都⽐ node 的值要⼩，右⼦树节点的值都⽐ node 的值⼤。
2对于 BST 的每⼀个节点 node，它的左侧⼦树和右侧⼦树都是 BST。
3BST 的中序遍历结果是有序的（升序）。
logN 级别的增删查改。

230.⼆叉搜索树中第 K ⼩的元素
538.把⼆叉搜索树转换为累加树
98.验证⼆叉搜索树
INT_MAX INT_MIN
更大范围的是 LONG_MIN LONG_MAX
96.不同的⼆叉搜索树
1373.⼆叉搜索⼦树的最⼤键值和
struct SubTree {
bool isBST;
int minValue;
int maxValue;
int sumValue;
SubTree(bool isBST, int minValue, int maxValue, int sumValue) : isBST(isBST), minValue(minValue), maxValue(maxValue), sumValue(sumValue) {}
};

DFS和BFS

深度优先搜索（Depth-First Search, DFS）和广度优先搜索（Breadth-First Search, BFS）是两种用于遍历或搜索树或图的算法。它们的主要区别在于遍历或搜索的顺序。

DFS

深度优先搜索优先深入到图的分支之中，直到当前分支终结或符合搜索条件为止，然后回溯，并探索下一条路径。DFS 通常使用递归实现，或者使用栈来进行迭代实现。
DFS 算法大体步骤如下：

  1. 从根节点（或任意指定的起始节点）开始。
  2. 访问节点，将其标记为已访问。
  3. 递归地对该节点的每一个未访问的相邻节点进行 DFS。
  4. 当图中所有从当前节点出发可达的节点都被访问过后，回溯到上一个节点。

BFS

广度优先搜索是按层序遍历图的节点，先访问离起始节点近的节点，再访问离起始节点远的节点。BFS 通常使用队列来实现。
BFS 算法大体步骤如下：

  1. 从根节点（或任意指定的起始节点）开始，并将其标记为已访问。
  2. 访问当前节点的所有未访问的相邻节点，将它们添加到队列中，并标记为已访问。
  3. 从队列中移除一个节点，并对其进行访问。
  4. 重复步骤 2 和步骤 3，直到队列为空。

区别总结

遍历方式：DFS 类似于树的先序遍历，一条路走到黑（深入）后再回溯；而 BFS 类似于树的层序遍历，逐层搜索。
数据结构：DFS 使用栈（或隐式的递归栈）来记录访问路径；BFS 使用队列来记录待访问的节点。
路径搜索：DFS 更适合目标节点深度较深的情况，且在找到解后会终止搜索；BFS 可以找到从起点到终点的最短路径。
空间复杂度：DFS 的空间复杂度可以较小（如果深度有限），因为它在任何时刻只需记录一条路径；而 BFS 可能需要更多的空间来存储所有扩展出的节点。
应用场景：DFS 更常用于决策树的搜索，如走迷宫、括号生成、解数独等；BFS 则适用于找到最短路径或层级遍历。
根据不同的问题和场景，你可以选择用 DFS 或 BFS 来达成目标效果。在无权图中找最短路径时使用 BFS，而在有需要进行深入搜索的问题时使用 DFS。

图

797.所有可能路径
207.课程表 (环检测)
注意，点的三种状体：未遍历 遍历中 遍历完成
210. 课程表 II（在207基础上改变）

二分图（暂时过）

Union-Find并查集

323.⽆向图中连通分量的数⽬（过滤）
130.被围绕的区域
990.等式⽅程的可满⾜性（过）

Kruskal算法

Kruskal算法是一种用于在加权图中寻找最小生成树的算法。最小生成树是一种特殊的树，它连接了图中的所有顶点，并且权重之和尽可能小。这种树在网络设计、电路设计、运输网络规划等领域有着广泛的应用。
Kruskal算法的工作原理是选择图中边的权重最小的边，同时确保选择的边不会形成环路。如果新选的边没有与现有生成树形成环，则将其加入到最小生成树中。
以下是Kruskal算法的基本步骤：

  1. 将图的所有边从小到大排序：依据边的权重将它们排序。
  2. 初始化最小生成树(MST)为空：开始时，最小生成树没有任何边。
  3. 选择最小权重的边：从按权重排列的边的列表中选取最小的边。
  4. 检查是否形成环路：确定选择的这条边加入MST后是否会形成一个环。为了检查这一点，可以使用并查集数据结构（Union-Find）。
  5. 如果不形成环，则将其加入MST：如果加入这条边不会导致环路的产生，就将其添加到MST中。
  6. 重复步骤3、4和5：继续选择下一条最小的边，重复上述过程，直至MST中含有n-1条边，这里n是图中顶点的数量。
  7. 完成最小生成树的构建：当最小生成树中包含所有顶点（或者正确地说是顶点数减1的边数）时，算法结束。
    Kruskal算法的时间复杂度主要取决于边的排序操作，使用效率高的排序算法可以达到O(E log E)的时间复杂度，其中E是边的数量。
    Kruskal算法非常适合用于稠密图，即边的数量接近于顶点数量平方的图。对于稀疏图来说，Prim算法可能是更好的选择，不过Kruskal算法具有实现简单、容易理解的优点。

Dijkstra 算法

Dijkstra 算法是由荷兰计算机科学家 Edsger W. Dijkstra 提出的，它用于解决加权图中的单源最短路径问题。这种算法可以找出图中一个节点到其他所有节点的最短路径。它适用于有向图和无向图，但不能处理带有负权重边的图。
Dijkstra 算法的基本思想是贪婪法 —— 每次寻找最小的未被处理的节点并进行松弛操作。
以下是 Dijkstra 算法的步骤：

  1. 初始化：将所有节点的最短距离估计值设置为无穷大，只将起始节点的最短距离设置为 0。
  2. 创建一个集合，用于跟踪已经访问过的节点：这个集合最初为空。
  3. 遍历所有节点：
    1. 从未访问的节点集合中选择距离起点距离最短的节点 u。
    2. 将节点 u 标记为已访问，并放入步骤2创建的集合。
    3. 对于通过节点 u 可以到达的每一个相邻节点 v，计算通过 u 从起始点到 v 的总距离。如果这个距离比当前已知的最短路径还短，就更新 v 的最短路径估计值。
  4. 重复上述步骤，直到所有的节点都被访问。
  5. 输出结果：在算法完成后，每个节点存储的最短路径估计值就是从起点到该节点的最短路径长度。
    为了加快寻找未访问节点中最短距离节点的过程，可以使用优先队列（如最小堆）来实现。使用优先队列的 Dijkstra 算法拥有更优的时间复杂度 O((V+E)logV)，其中 V 表示节点数，E 表示边数。
    Dijkstra 算法在网络路由、地图软件、社交网络分析等许多领域都有着广泛的应用。需要注意的是，如果图包含负权重边，Dijkstra 算法可能不会得到正确的结果，而此时应该使用比如贝尔曼-福特算法（Bellman-Ford algorithm）这样的算法来解决单源最短路径问题。
    让你算从节点 k 出发到其他所有节点的最短路径，就是标准的 Dijkstra 算法。
    在⽤ Dijkstra 之前，别忘了要满⾜⼀些条件，加权有向图，没有负权重边。
    743.⽹络延迟时间
    1631.最⼩体⼒消耗路径
    1514.概率最⼤的路径

backtrack回溯算法

46.全排列
Vector 清除最后一个元素
if (!vec.empty()) {
vec.pop_back(); // 删除最后一个元素
}
51.N 皇后

排列、组合、⼦集问题

⽆论形式怎么变化，其本质就是穷举所有解，⽽这些解呈现树形结构，所以合理使⽤回溯算法框架，稍改代码框架即可把这些问题⼀⽹打尽。

子集（元素⽆重不可复选）

78.⼦集

组合

组合和⼦集是⼀样的：⼤⼩为 k 的组合就是⼤⼩为 k 的⼦集
90.⼦集 II
元素可重先进⾏排序，让相同的元素靠在⼀起，如果发现 nums[i] == nums[i-1]，则跳过不可复选
添加了排序和剪枝的逻辑。
47.全排列 II
39.组合总和 （元素⽆重可复选）
想让每个元素被重复使⽤，只要把 i + 1 改成 i 即可

集合划分问题

回溯算法就是穷举⼀棵决策树的过程，只要在递归之前「做选择」，在递归之后「撤销选择」就⾏了。
698.划分为k个相等的⼦集.略过

DFS

200.岛屿数量
技巧：淹没已遍历的岛屿，可以不用visited 加快效率
1254.统计封闭岛屿的数⽬
注意靠边的岛屿不是封闭岛，其他都是
695.岛屿的最⼤⾯积
1905.统计⼦岛屿
技巧,grid2中1对应grid1中0 肯定就不是子岛屿
694.不同的岛屿数量
记录遍历的方向（包含进和出，1和-1） 转化为字符串进行哈希

BFS

算法解题套路框架
BFS 算法都是⽤「队列」这种数据结构，每次将⼀个节点周围的所有节点加⼊队列。BFS 找到的路径⼀定是最短的，但代价就是空间复杂度可能⽐ DFS ⼤很
多。BFS 出现的常⻅场景问题的本质就是让你在⼀幅「图」中找到从起点start 到终点 target 的最近距
DFS 不能找最短路径吗？其实也是可以的，但是时间复杂度相对⾼很多,DFS 是线，BFS 是⾯
BFS 可以找到最短距离，但是空间复杂度⾼，⽽ DFS 的空间复杂度较低。
111.⼆叉树的最⼩深度
注意无叶子节点情况
752.打开转盘锁
注意 每次动锁 下个状态有8个
注意bfs时候 while（for（size 不能取qsize））
773.滑动谜题.
Bfs，关键是统计每次前后状态，转化为字符串

动态规划

动态规划的核⼼思想就是穷举求最值
以上提到的重叠⼦问题、最优⼦结构、状态转移⽅程就是动态规划三要素

509.斐波那契数
322.零钱兑换
注意：多个分支 结果如何合并， 有效分支取最值，分支全无效才整个无效

931.下降路径最⼩和
300.最⻓递增⼦序列」 最⻓递增⼦序列
dp[i] 以nums[i]结尾的序列
If nums[j] < nums[I]
dp[i] = max(dp[i],dp[j]+1)
354. 俄罗斯套娃信封问题
Sort

53.最⼤⼦序和 最⼤⼦数组和问题
dp[i] 有两种「选择」，要么与前⾯的相邻⼦数组连接，形成⼀个和更⼤的⼦数组；要么不与前
⾯的⼦数组连接，⾃成⼀派，⾃⼰作为⼀个⼦数组。

72.编辑距离
重点是状态转移方程
我们用 D[i][j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离。
操作归为3种：
在单词 A 中插入一个字符
在单词 B 中插入一个字符
修改单词 A 的一个字符
获得 D[i][j-1]，D[i-1][j] 和 D[i-1][j-1] 的值之后就可以计算出 D[i][j]
技巧：队首添加空字符

0-1 背包问题

第⼀步要明确两点，「状态」和「选择」。
dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最⼤价值是 dp[i][w]。
如果你没有把这第 i 个物品装⼊背包，那么很显然，最⼤价值 dp[i][w] 应该等于 dp[i-1][w]，继承之前的结果。
如果你把这第 i 个物品装⼊了背包，那么 dp[i][w] 应该等于 val[i-1] + dp[i-1][w - wt[i-1]]。

518.零钱兑换 II
416.分割等和⼦集

  1. 买卖股票的最佳时机 IV
    121.买卖股票的最佳时机」
    122.买卖股票的最佳时机 II
    309.最佳买卖股票时机含冷冻期」
  2. 买卖股票的最佳时机含⼿续费 Leetcode
  3. 买卖股票的最佳时机 III
  4. 买卖股票的最佳时机 IV

198.打家劫舍
877.⽯头游戏(没意思)
486. 预测赢家 Leetcode 没做对
State:dp[i][j] 表示当数组剩下的部分为下标 iii 到下标 jjj 时，即在下标范围 [i,j][i, j][i,j] 中，当前玩家与另一个玩家的分数之差的最大值，注意当前玩家不一定是先手。
转移：1.i>j 0 2;:I=j num[I] 3.i<j dp[i][j] = max(num[i] - dp[i+1][j], num[j] - dp[i][j-1])

64.最⼩路径和
887.鸡蛋掉落」\

55.跳跃游戏
Dfs 只要有一条true则true 怎么实现？

标签：遍历,归纳,路径,DFS,leetcode,BFS,算法,节点,刷题
From： https://www.cnblogs.com/dingz/p/18242530

相关文章

  • LeetCode 419. 甲板上的战舰（深度优先搜索dfs、数组）
    419.甲板上的战舰思路：方法一，深度优先搜索dfs，遇到‘X’，就dfs一次，并在board中将其变为‘.’。classSolution{public:voiddfs(intx,inty,vector<vector<char>>&board){if(board[x][y]!='X')return;board[x][y]='.';if(x+1......
  • Leetcode419 甲板上的战舰
    最近以来，我在力扣上坚持完成每天一题，今天系统推的题目为《甲板上的战舰》，在此记录一下。题目描述如下:给你一个大小为mxn的矩阵board表示甲板，其中，每个单元格可以是一艘战舰'X'或者是一个空位'.'，返回在甲板board上放置的战舰的数量。战舰只能水平或者垂直放置在......
  • 华为OD刷题C卷 - 每日刷题 22（计算面积、绘图机器，信道分配）
    1、（计算面积、绘图机器）：这段代码是解决“计算面积、绘图机器”的问题。它提供了一个Java类Main，其中包含main方法，用于计算绘图机器按照给定指令绘制直线所形成的图形面积。main方法首先读取指令数量n和横坐标终点值end_X。然后，初始化面积和area为0，以及上一个点的坐标last_X......
  • 华为OD刷题C卷 - 每日刷题 23（提取字符串中的最长表达式，模拟目录管理功能 - 完整实现）
    1、提取字符串中的最长表达式目标是从一个给定的字符串中提取出最长的合法简单数学表达式，并计算该表达式的值。如果存在多个同样长度的合法表达式，则选择第一个出现的表达式进行计算。简单数学表达式的规则：只包含0-9的数字和+、-、*三种运算符。所有数字的计算结果不超过......
  • LeetCode 409 Longest Palindrome All In One
    LeetCode409LongestPalindromeAllInOneLeetCode409最长回文算法题解Solutions//MapfunctionlongestPalindrome(s:string):number{constmap=newMap();letlen=0;for(leti=0;i<s.length;i++){if(map.has(s[i])){//配对，消元......
  • LeetCode 算法：缺失的第一个正数c++
    原题链接......
  • Q25 LeetCode49 字母异位词分组
    难好好看看  1classSolution{2publicList<List<String>>groupAnagrams(String[]strs){3if(strs==null||strs.length==0)4returnnewArrayList<>();5//map中key存储的是字符串中字母排序后新的字符串6Map<Stri......
  • 第一篇 LeetCode(42)接雨水
    LeetCode(42)接雨水力扣官网题目描述：给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。输入：height=[0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组[0,1,0,2,1,0,1,3,2,1,2,1]表示的高度图，在这种情况下，可以接6个单位的雨水......
  • LeetCode 974 Subarray Sums Divisible by K All In One
    LeetCode974SubarraySumsDivisiblebyKAllInOneLeetCode974能被K整除的子数组之和errosfunctionsubarraysDivByK(nums:number[],k:number):number{//-5/0/5letcount:number=0;//单个元素for(leti=0;i<nums.length;i++){......
  • Q24 LeetCode383 赎金信
    同Q23只需要先将随机字符串挨个存入hashmap中，然后循环遍历给定字符串，只要最后hashmap中size为0，即可返回true 1classSolution{2publicbooleancanConstruct(StringransomNote,Stringmagazine){34HashMap<Character,Integer>smap=newH......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99