算法
2024-05-24 21:13:12 2 举报AI智能生成
刷题思路
作者其他创作
大纲/内容
二分法
1. 问题拆解，找到问题之间的具体联系
状态是什么
状态转移方程
状态初始值
问题最后的答案是什么
2. 状态定义
3. 递推公式，状态转移方程
4. 实现
要点
爬楼梯-LeetCode70
递推
三角形-LeetCode120
矩阵型
序列型
双序列型
划分型
石子问题
最大括号匹配数
最长回文串-leetcode32
区间型
背包型
状态压缩型
树型
类型
最大最小值
方案总数
可行不可行
问题特点
优化
动态规划
递归
贪心算法
分治
回溯
排序
搜索
哈希算法
字符串匹配
划分为k个相等的子集-LeetCode698
参考
深度优先搜索DFS
算法
排序+双指针
数组
LeetCode876
快慢双指针
链表
队列
栈
哈希表
二叉树
AVL树
红黑树
平衡二叉树
B树
Trie树
树
堆
图
数据结构
难度从低到高
tag分类刷
定期复习之前的题，总结思路
时间充沛
leetCode热门题
精选题面试题
时间紧迫
题目选择
回溯法
分治思想
算法思想
算法分类
要解决什么问题
会用到什么数据结构和算法
5分钟内看懂
看懂题目
思考，参考答案，总结思考方式和最优解，分析题目类型用到的算法和数据结构
第一遍
先思考，最优解，与之前自己的解法对比，总结差异点和方法
第二遍
提升刷题速度，拿出一个题就知道考察的算法与数据结构、解题方法，短时间内解答
第三遍
做题步骤
自己的第一遍解法
网上好的解法
思维上的差异，卡住的地方
改进点
对题目的思路、算法、数据结构进行归类总结
总结
刷题技巧
滑动窗口，双指针
set判断重复
要点思路
无重复字符串最大长度-3
先循环找到要反转的链表
反转链表的同时记录前后节点，反转后连接上，进行下一轮反转
思路
封装反转函数，反转时要把尾节点设置为null
K 个一组翻转链表-25
双指针
反转链表-206
利用快排logn
数组中第K个大的数-215
排序，双指针
当前节点+左指针+右指针==0则放入并跳过相同数据，<0则左指针向右遍历，>0则右指针往左遍历
三数之和-15
广度优先遍历，双队列，一个负责遍历，一个负责写入数据，写入数据考虑方向
二叉树的锯齿形层次-103
暴力解
前面遍历存最小值，用后面正在遍历的数据减最小值求差
买卖股票的最佳时机-121
找到非旋转那一段，判断是否在这里面，在就二分这一段，不在就二分另一段
搜索旋转排序数组-33
递归DFS数组深度优先遍历
下标越界、已遍历直接返回
二维数组遍历每个节点，每个节点dfs
岛屿数量-200
如果相交，双指针便利两条链表，遍历的路径是一样长，最终会相遇，不相交则最终都是null
相交链表-160
算出有多少行（数组最大值），求每一行雨水数量
遍历每一行，每行都遍历一下数组，数组值<当前行数的，temp++，>当前行数，累加到最终值，temp=0
解法1（求每行）
遍历每一列，计算左边最大值，计算右边最大值，当前列低于两边，累加（左右较小值-当前值）
解法2（求每列）
还是解法2的思路
用动态规划的方式分别提前计算出左右两边的最大值
解法3（解法2的优化版）
解法2的思路，双指针，左右交替接水
左边比右边小那就左边遍历接水，左边比右边大那就右边开始接水
解法4（解法2优化版双指针）
接雨水-42
上下左右边界4指针，依次右下左上循环遍历到边界，遍历完后增加或减小下标值，比如第一次向右遍历完，那么上边界++，向下遍历完，右边界--依次类推
外层死循环，内层4个上下左右循环，超出边界直接退出死循环
螺旋矩阵-54
二叉树最近公共祖先节点-236
暴力遍历
hash表
两数之和-1
动态规划，非标准
前面累计和+当前节点和当前节点对比，取最大值做为累积和，用另外一个值来存储全局最大值
最大子数组和-53
动态规划，转移方程：dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]
出始赋值
最长回文字符串-5
回溯算法
全排列-46
从后往前找到第一个比左边的数大的节点，在从右往左找到最小的比当前节点左边大的数
交换位置然后将右边的数组反转，右边已经是有序的了
下一个排列-31
1. 遍历当前头节点找到最小的那个插入结果链表，时间复杂度n*m
思路1
两两归并
递归，二分法归并结果，对结果再归并
思路2
合并K个升序链表-23
dp[i]是必须要包含当前节点的
遍历到i时，再往前遍历所有之前的节点，把自己作为最后一个节点
最长递增子序列-300
层序遍历，取每一层最右边的节点
队列存每一层的数据，每次遍历的时候用下标标记本次遍历的结束位置
二叉树右视图-199
使用栈，如果是左括号压栈，右括号出栈，栈空了说明为false，出栈和当前节点不匹配也为false
有效括号-20
使用队列记录节点
while循环队列直到不为空
每层用for循环遍历
二叉树层序遍历-102
快慢指针找到中间节点
中间节点往后反转
双链表合并
重排链表-143
创建头节点
大的节点塞入返回节点后面
最后把剩余的节点拼到结果节点后面
合并两个有序链表-21
开辟新的数组，两个数组合并到新数组里面，最后再复制回原数组
逆向合并，原数组后面是空的，找到大的数往后面放
合并两个有序数组-88
hash表，将当前数组作为hash表
遍历当前节点当下标不符合的即为缺失的正数
缺失的第一个正数-41
快慢指针，快指针=慢指针时就有环
环形链表-141
全局保存最大值
深度遍历二叉树，左右节点+自身和最大值比较，如果大的话就替换最大值
递归返回自身节点最大值，三种情况，父节点、父左子、父右子
二叉树中的最大路径和-124
结尾记得单独加上进一位
字符串相加-415
找到left节点，记录前节点pre，开始反转，到right节点为止，pre指向反转后的第一个节点，开始反转的节点指向right.next
反转链表2-92
递归dfs，根节点往下遍历，往下一层就将之前的数*10+当前节点数
叶子节点累加总数
求根到叶子节点数字之和-129
排序，前后节点判断，没交集就新增一行新数据，有交集就将右节点更新为当前行的右节点
合并区间-56
计算要转long，不然超出int最大值
x的平方根-69
递归，分治，归并
排序链表-148归并排序
最大正方形-221
层序遍历，对比两边节点是否对称
递归，同时递归左右子节点，不同就返回false，相同就继续递归左节点的左子节点和右节点的右子节点&&左节点右子节点和右节点左子节点
对称二叉树-101
双指针前后对比找到中间的节点，二分
快排-912
方程
编辑距离-72
切割“.”号，注意带转译符号
比较版本号-165
每次遍历可以加在左括号，也可以加在右括号
左右括号数相等，递归左右两边可使用的括号数==0就返回
括号生成-20
前序表明顺序，中序表明左右节点
递归构建当前节点，利用中序知道左右节点个数，就知道先序要遍历的个数
前序和中序遍历构架二叉树
栈记录每个左括号的下标
遍历为右括号的时候出栈，并将下标值对应的数据改为完成
遍历完成的数组，找到最长完成的数据
最长有效括号-32
快慢指针
寻找第一次遇到的节点，没遇到说明不是环
第一次遇到后，快指针变为慢指针，从头开始遍历，相遇节点即为入环节点
环形链表-142
算出当前节点总和，叶子节点判断是否等于目标值
路径总和-112
两个栈，一个输入，一个输出
输入栈只管输入，输出栈输出时判断当前是否为空，空了就讲输入栈的数据放到输出栈来
用栈实现队列-232
滑动窗口
维护一个map，key是字符串字符，value是需要的个数
开始时往右扩大窗口，字符需要的个数为0从左边收缩窗口
最小覆盖子串-76
双指针累加
两数相加-2
nums[-1]=nums[n]=-无穷
二分往大方向找一定能找到峰值
寻找峰值-162
递归，用栈或队列保存走过的路
递归完当前节点直接出栈或者移除队列
路径总和2-113
零钱兑换-322
临时头节点
找到重复元素后开启新循环找到第一个不重复的元素
改变指针
删除链表中重复元素82-思路
中序遍历，前一个值一定比后一个值小
验证搜索二叉树-98
先将自己添加到path中，下标增加，递归下一次
递归完了将自己移除，下标增加，继续递归
子集-78
右指针先走n步，左指针才开始走
右指针下一个节点==null就表示左指针的下一个节点就是倒数第n个节点，替换
删除链表的倒数第 N 个结点-19
递归dfs
剩余目标值除当前下标数，往path里面添加，如果刚好等于目标数就新增结果，不等就下标+1，递归下去
不匹配将当前放进去的数据移除再次递归
组合总和-39
字节
真题
算法&数据结构
0 条评论
回复 删除
下一页
