Leetcode 算法解题思路总结

简介: Leetcode 算法解题思路总结

注:拿到题目后先通过审题,判断是哪一类题,可以套用什么模板,明确这一块非常重要没有之一,明确了之后,很可能出现自己都不知道是为什么,但题已经迎刃而解了!!!


一、二叉树问题


注:二叉树的遍历方式主要有广度遍历(BFS)和深度遍历(DFS),深度遍历又主要包含:先序遍历、中序遍历和后序遍历;


拿到题目

1)判断是搜索还是遍历;

2)如果是搜索,使用递归;

       明确当前节点要做的事;

       其他交给递归,如果当前节点会影响整个二叉树,借助辅助函数;

3)如果是遍历,使用对应框架;


二者区别及适用范围:

(1)BFS、DFS 最坏时间复杂度相同,但是相比之下 BFS 更高效;

(2)DFS 的空间复杂度优于 BFS,且 DFS 使用递归,代码比较好些;

(3)一般在寻找最短路径时使用BFS,其他时候使用DFS;

(4)DFS 是线,BFS 是面;相当于 DFS 是单打独斗,BFS 是集体行动;


1、BFS(广度优先搜索)


   BFS 主要解决最短路径问题,BFS 又分为传统 BFS 和双向 BFS;传统 BFS 是从起点开始扩散,遇到终点时停止;双向 BFS是从起点和终点同时开始扩散,且当两边有交集时停止;虽然二者的最坏时间复杂度相同,但是实际上双向 BFS会较快一些;二者空间复杂度相同;


       只要涉及暴力穷举的问题,BFS 都可以使用,而且可以更快地找到答案;在使用 BFS 框架时,如果遇到二维数组问题,一般都会转化为一维数组处理,因为二维数组套用 BFS 框架比较麻烦且效率低;如滑动拼图问题, labuladong 的算法小抄 P311 ;


注:使用双向 BFS 的前提是必须知道终点在哪里;


下面举例说明;

(1)BFS 求二叉树的最小高度

(2)BFS 求解开密码锁的最少次数

       002 BFS 实现解开密码锁的最少次数

       003 双向 BFS 实现解开密码锁的最少次数


注:在双向 BFS 中,如果每次选择较小的集合进行扩散,占用的空间增长速度就会慢一些,且效率会高一些;即在 while 循环开始时做一个交换,找出较小的集合;


补充:BFS 的使用有两种情况


情况一:在 while(!q.empty()){} 循环中使用 for 循环,for 循环结束即对应着,当前层遍历结束,应用的场合如:求树的深度;


情况二:在 while(!q.empty()){} 循环中不使用 for 循环,直接把当前节点的子节点加入到 q 队列中;


2、DFS(深度优先搜索)


       DFS 主要解决最短路径以外的搜索问题(例如涉及排序的相关问题);深度优先搜索主要包括:先序遍历、中序遍历和后续遍历;


(1)先序遍历

 004 DFS 先序遍历实现全排列问题


3、BST(二叉搜索树)


       二叉搜索树是一种非常常用的二叉树,特点:任意节点的值要大于等于左子树所有节点的值,且要小于等于右子树的所有节点的值;基本框架见:labuladong 的算法小抄 P238 ;


 BFS 技巧:

(1)二叉树算法设计总路线:把当前节点要做的事做好,其他的扔给递归,无需当前节点操心;

(2)如果当前节点会对下面的子节点有整体影响,可以通过辅助函数增长参数列表,借助参数传递信息;

       006 验证二叉搜索树[C++]

       007 二叉搜索树的插入操作[C++]


二、查找问题


1、已知数组—无序状态


优先考虑:unordered_set、unordered_map 容器


原因1:两者的实现都是基于哈希表,其在插入和查找问题上时间复杂度很低,且高效,代价是消耗较多的内存;


原因2:两者都有 find() 内置函数,查找起来比较方便;


2、已知数组—有序状态


优先考虑二分查找,套用模板;

注:在实现二分查找的过程中也可以考虑使用 unordered_set、unordered_map 容器;

二分查找模板如下:

注:模板参考 labuladong 的算法小抄 P83


三、回溯算法


       解决回溯问题,实际上就是一个决策树的遍历问题,所以解决回溯问题使用的方法是二叉树的先序遍历,只不过二叉树变成了多叉树;且回溯算法就是纯暴力穷举,复杂度一般都很高;


    下面使用 Leetcode 例题说明;        

       004 DFS 先序遍历实现全排列问题

       005 回溯算法实现 N 皇后问题


回溯方法的框架见: labuladong 的算法小抄 P43

注:总结仅仅是为了自己在刷题后期复习起来比较方便,持续更新中;

目录
打赏
0
0
0
0
1
分享
相关文章
|
3月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
53 0
通义灵码:融合创新玩法与探索,重塑LeetCode解题策略
欢迎来到工程师令狐小哥的频道。本文介绍如何利用AI工具高效刷LeetCode,通过通义灵码插件在IntelliJ IDEA中实现代码生成、优化、单元测试等功能,提升编程学习效率。
105 1
通义灵码:融合创新玩法与探索,重塑LeetCode解题策略
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
【算法每日一练及解题思路】有n级台阶,一次只能上1级或2级,共有多少种走法?
本文深入解析了“爬楼梯问题”,探讨了递归与迭代两种解法,并提供了Java代码实现。通过分析问题本质,帮助读者理解动态规划技巧,提高解决实际编程问题的能力。关键词:Java, 算法, 动态规划, 爬楼梯问题, 递归, 迭代。
141 0
|
5月前
|
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
92 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
【算法解题思想】动态规划+深度优先搜索(C/C++)
【算法解题思想】动态规划+深度优先搜索(C/C++)
|
5月前
|
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
63 6
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
85 2
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
58 1
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
78 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等