首页  思维导图  详情



 



算法

2024-05-24 21:13:12   3  举报





AI智能生成

刷题思路

技能提升

模板推荐

作者其他创作

大纲/内容

算法

二分法

动态规划

要点

1. 问题拆解，找到问题之间的具体联系

2. 状态定义

状态是什么

状态转移方程

状态初始值

问题最后的答案是什么

3. 递推公式，状态转移方程

4. 实现

类型

递推

爬楼梯-LeetCode70

矩阵型

三角形-LeetCode120

序列型

双序列型

划分型

区间型

石子问题

最大括号匹配数

最长回文串-leetcode32

背包型

状态压缩型

树型

问题特点

最大最小值

方案总数

可行不可行

优化

递归

贪心算法

分治

回溯

排序

搜索

哈希算法

字符串匹配

深度优先搜索DFS

划分为k个相等的子集-LeetCode698

数据结构

数组

排序+双指针

链表

快慢双指针

LeetCode876

队列

栈

哈希表

树

二叉树

平衡二叉树

AVL树

红黑树

B树

Trie树

堆

图

刷题技巧

题目选择

时间充沛

难度从低到高

tag分类刷

定期复习之前的题，总结思路

时间紧迫

leetCode热门题

精选题面试题

算法分类

数据结构

数组

链表

树

堆

图

栈

队列

哈希表

算法思想

二分法

递归

动态规划

回溯法

分治思想

贪心算法

做题步骤

看懂题目

要解决什么问题

会用到什么数据结构和算法

5分钟内看懂

第一遍

思考，参考答案，总结思考方式和最优解，分析题目类型用到的算法和数据结构

第二遍

先思考，最优解，与之前自己的解法对比，总结差异点和方法

第三遍

提升刷题速度，拿出一个题就知道考察的算法与数据结构、解题方法，短时间内解答

总结

自己的第一遍解法

网上好的解法

思维上的差异，卡住的地方

改进点

对题目的思路、算法、数据结构进行归类总结

真题

字节

无重复字符串最大长度-3

要点思路

滑动窗口，双指针

set判断重复

K 个一组翻转链表-25

思路

先循环找到要反转的链表

反转链表的同时记录前后节点，反转后连接上，进行下一轮反转

封装反转函数，反转时要把尾节点设置为null

反转链表-206

思路

双指针

递归

数组中第K个大的数-215

思路

利用快排logn

计算每次找到的下标，>k,往左遍历，<k往右遍历

三数之和-15

思路

排序，双指针

当前节点+左指针+右指针==0则放入并跳过相同数据，<0则左指针向右遍历，>0则右指针往左遍历

二叉树的锯齿形层次-103

思路

广度优先遍历，双队列，一个负责遍历，一个负责写入数据，写入数据考虑方向

买卖股票的最佳时机-121

思路

暴力解

前面遍历存最小值，用后面正在遍历的数据减最小值求差

搜索旋转排序数组-33

思路

二分法

找到非旋转那一段，判断是否在这里面，在就二分这一段，不在就二分另一段

岛屿数量-200

思路

递归DFS数组深度优先遍历

下标越界、已遍历直接返回

二维数组遍历每个节点，每个节点dfs

相交链表-160

思路

如果相交，双指针便利两条链表，遍历的路径是一样长，最终会相遇，不相交则最终都是null

接雨水-42

思路

解法1（求每行）

算出有多少行（数组最大值），求每一行雨水数量

遍历每一行，每行都遍历一下数组，数组值<当前行数的，temp++，>当前行数，累加到最终值，temp=0

解法2（求每列）

遍历每一列，计算左边最大值，计算右边最大值，当前列低于两边，累加（左右较小值-当前值）

解法3（解法2的优化版）

思路

还是解法2的思路

用动态规划的方式分别提前计算出左右两边的最大值

解法4（解法2优化版双指针）

思路

解法2的思路，双指针，左右交替接水

左边比右边小那就左边遍历接水，左边比右边大那就右边开始接水

螺旋矩阵-54

思路

上下左右边界4指针，依次右下左上循环遍历到边界，遍历完后增加或减小下标值，比如第一次向右遍历完，那么上边界++，向下遍历完，右边界--依次类推

外层死循环，内层4个上下左右循环，超出边界直接退出死循环

二叉树最近公共祖先节点-236

思路

递归, 当前节点为null或为目标节点直接返回

递归左右子节点，如果递归结果都为null返回null,left为null返回右节点，right为null返回左节点

两数之和-1

思路

暴力遍历

hash表

最大子数组和-53

思路

动态规划，非标准

前面累计和+当前节点和当前节点对比，取最大值做为累积和，用另外一个值来存储全局最大值

最长回文字符串-5

思路

动态规划，转移方程：dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]

出始赋值

全排列-46

思路

回溯算法

下一个排列-31

思路

从后往前找到第一个比左边的数大的节点，在从右往左找到最小的比当前节点左边大的数

交换位置然后将右边的数组反转，右边已经是有序的了

合并K个升序链表-23

思路1

1. 遍历当前头节点找到最小的那个插入结果链表，时间复杂度n*m

思路2

两两归并

递归，二分法归并结果，对结果再归并

最长递增子序列-300

思路

动态规划

方程：当nums[i]>nums[j]时，dp[i] = Math.max(dp[i],dp[j]+1)

dp[i]是必须要包含当前节点的

遍历到i时，再往前遍历所有之前的节点，把自己作为最后一个节点

二叉树右视图-199

思路

层序遍历，取每一层最右边的节点

队列存每一层的数据，每次遍历的时候用下标标记本次遍历的结束位置

有效括号-20

思路

使用栈，如果是左括号压栈，右括号出栈，栈空了说明为false，出栈和当前节点不匹配也为false

二叉树层序遍历-102

思路

使用队列记录节点

while循环队列直到不为空

每层用for循环遍历

重排链表-143

思路

快慢指针找到中间节点

中间节点往后反转

双链表合并

合并两个有序链表-21

思路

创建头节点

大的节点塞入返回节点后面

最后把剩余的节点拼到结果节点后面

合并两个有序数组-88

思路1

开辟新的数组，两个数组合并到新数组里面，最后再复制回原数组

思路2

逆向合并，原数组后面是空的，找到大的数往后面放

缺失的第一个正数-41

思路

缺失的数一定在数组长度n+1内，[1,n+1]

hash表，将当前数组作为hash表

遍历数组，让每个元素到它所在的下标，不在[1,n+1]的直接过滤

遍历当前节点当下标不符合的即为缺失的正数

环形链表-141

思路

快慢指针，快指针=慢指针时就有环

二叉树中的最大路径和-124

思路

全局保存最大值

深度遍历二叉树，左右节点+自身和最大值比较，如果大的话就替换最大值

递归返回自身节点最大值，三种情况，父节点、父左子、父右子

字符串相加-415

思路

双指针，模拟加法,当前chat数值=chat-'0'

结尾记得单独加上进一位

反转链表2-92

思路

找到left节点，记录前节点pre，开始反转，到right节点为止，pre指向反转后的第一个节点，开始反转的节点指向right.next

求根到叶子节点数字之和-129

思路

递归dfs，根节点往下遍历，往下一层就将之前的数*10+当前节点数

叶子节点累加总数

合并区间-56

思路

排序，前后节点判断，没交集就新增一行新数据，有交集就将右节点更新为当前行的右节点

x的平方根-69

思路

二分法

计算要转long，不然超出int最大值

排序链表-148归并排序

思路

递归，分治，归并

最大正方形-221

思路

动态规划，以[i,j]为右下角的最大正方形长度

方程,dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1

对称二叉树-101

思路1

层序遍历，对比两边节点是否对称

思路2

 递归，同时递归左右子节点，不同就返回false，相同就继续递归左节点的左子节点和右节点的右子节点&&左节点右子节点和右节点左子节点

快排-912

思路

双指针前后对比找到中间的节点，二分

编辑距离-72

思路

动态规划

方程

比较版本号-165

思路

切割“.”号，注意带转译符号

括号生成-20

思路

递归

每次遍历可以加在左括号，也可以加在右括号

左右括号数相等，递归左右两边可使用的括号数==0就返回

前序和中序遍历构架二叉树

思路

递归

前序表明顺序，中序表明左右节点

递归构建当前节点，利用中序知道左右节点个数，就知道先序要遍历的个数

最长有效括号-32

思路

栈记录每个左括号的下标

遍历为右括号的时候出栈，并将下标值对应的数据改为完成

遍历完成的数组，找到最长完成的数据

环形链表-142

思路

快慢指针

寻找第一次遇到的节点，没遇到说明不是环

第一次遇到后，快指针变为慢指针，从头开始遍历，相遇节点即为入环节点

路径总和-112

思路

递归

算出当前节点总和，叶子节点判断是否等于目标值

用栈实现队列-232

思路

两个栈，一个输入，一个输出

输入栈只管输入，输出栈输出时判断当前是否为空，空了就讲输入栈的数据放到输出栈来

最小覆盖子串-76

思路

滑动窗口

维护一个map，key是字符串字符，value是需要的个数

开始时往右扩大窗口，字符需要的个数为0从左边收缩窗口

两数相加-2

思路

双指针累加

寻找峰值-162

思路

nums[-1]=nums[n]=-无穷

二分往大方向找一定能找到峰值

路径总和2-113

思路

递归，用栈或队列保存走过的路

递归完当前节点直接出栈或者移除队列

零钱兑换-322

思路

动态规划

dp[n] = min(dp[n],dp[n-i]+1)

删除链表中重复元素82-思路

临时头节点

找到重复元素后开启新循环找到第一个不重复的元素

改变指针

验证搜索二叉树-98

思路

中序遍历，前一个值一定比后一个值小

子集-78

思路

递归

先将自己添加到path中，下标增加，递归下一次

递归完了将自己移除，下标增加，继续递归

删除链表的倒数第 N 个结点-19

思路

双指针

右指针先走n步，左指针才开始走

右指针下一个节点==null就表示左指针的下一个节点就是倒数第n个节点，替换

组合总和-39

思路

递归dfs

剩余目标值除当前下标数，往path里面添加，如果刚好等于目标数就新增结果，不等就下标+1，递归下去

不匹配将当前放进去的数据移除再次递归

 Collect

Get Started

WeChat基础算法

 Collect

Get Started

算法模型

 Collect

Get Started

循环算法

 Collect

Get Started

控制算法





0 条评论

下一页