算法
2024-05-24 21:13:12 2 举报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，递归下去
不匹配将当前放进去的数据移除再次递归
0 条评论
下一页
