死磕算法
2024-05-09 16:16:44 0 举报AI智能生成
登录查看完整内容
作为前端开发者，你是否在寻找提升编程技能的途径？我们的模板汇集了LeetCode上的常见算法题目，从简单到中级难度，为你的前端技术栈增添算法智慧。
作者其他创作
大纲/内容
困难
子元素区间右侧排序
相交会出现end相交
外框
435. 无重叠区间
概要
同上一题
452. 用最少数量的箭引爆气球
找出对应gas[i] - cost[i]结余
上述条件，小于0，point = i+ 1
134. 加油站
中等
简单
贪心算法
回溯算法
const reg = /[a-zA-Z]+|[0-9]+|\\[|\\]/g;
const last = () => stack[stack.length - 1];
用到了正则的lastIndex，因为exec和test执行以下，每执行一次，lastIndex就会往后+1
string.repeat(num)
394. 字符串解码
字符串
算法
128. 最长连续序列
代码
525. 连续数组
523. 连续的子数组和
150. 逆波兰表达式求值
剑指 Offer II 036. 后缀表达式
数组
200. 岛屿数量
剑指 Offer II 105. 岛屿的最大面积
递归
239. 滑动窗口最大值
剑指 Offer 59 - II. 队列的最大值
155. 最小栈
滑动窗口
62. 不同路径
63.不同路径II
不同路径
343. 整数拆分
树中有相同的
96.不同的二叉搜索树
整数拆分
416. 分割等和子集
698.划分为k个相等的子集
473.火柴拼正方形
类似于416题，return sum - dp[target] - dp[target]
1049. 最后一块石头的重量 II
474.一和零
01背包问题
518. 零钱兑换 II
322. 零钱兑换
377. 组合总和 Ⅳ
279.完全平⽅数
139. 单词拆分
left组合 - right组合 = target，left + right等于sum，left = (target + sum) /2
dp[j] += dp[j - nums[i]]
494.目标和
完全背包
多重背包
分组背包
198. 打家劫舍
213.打家劫舍II
337. 打家劫舍 III
打家劫舍
122. 买卖股票的最佳时机 II
买卖股票
300.最⻓递增⼦序列
674. 最⻓连续递增序列
718. 最长重复子数组
1143. 最长公共子序列
与1143一致
1035.不相交的线
动态规划
53. 最大子数组和
392. 判断子序列
115.不同的⼦序列
583. 两个字符串的删除操作
72. 编辑距离
子序列问题
509.斐波那契数
一次m个台阶
70.爬楼梯
第一步不需要花费体力，最后一步不需要花费体力
746.使用最小花费爬楼梯
爬楼梯
121. 买卖股票的最佳时机
123. 买卖股票的最佳时机 III
188.买卖股票的最佳时机IV
309.最佳买卖股票时机含冷冻期
714. 买卖股票的最佳时机含手续费
采用分治法，两个两个merge
23. 合并K个升序链表
先实现reverse(head)反转
a.next = 对应的K反转结果
25. K 个一组翻转链表
1.head递归往下遍历，知道head === null，即遍历完毕
2.新pre = ListNode(-1)指针
3.p指向pre的临时指针
4.q指向head的临时指针，在执行head = head.next之前调用
while循环，判断新的head值在pre链表里插入位置
147.对链表进行插入排序
快慢指针
先判断是环
上一步结束，fast是否为链表最后节点
重置slow指针为head，在递归slow !== fast(此时fast = fast.next)
142.环形链表 II
快慢指针+链表新增个头部节点(涉及到删除操作，需要知道slow的前一个，和下一个)
先遍历到第k个节点，不处理slow指针
继续遍历，此时处理slow指针
当fast结束时，slow即为被删除的节点
19.删除链表的倒数第N个节点
92. 反转链表 II
725. 分隔链表
first、cur、last指针
分别代表正数第k个，遍历条件，及倒数第k个
cur.next !== null，遍历结束，获得first、last指针
只需要交换节点值
交换节点
1721. 交换链表中的节点
445.两数相加II
链表1遍历结束，遍历链表2
循环条件p1 !== p2，如果相同肯定相交
160. 相交链表
循环条件fast !== null && fast.next !== null
循环结束，输出slow
876.链表中间结点
slow === fast，就退出循环
141. 环形链表
先遍历到第k个节点，不处理slow
继续遍历处理slow指针
剑指 Offer 22. 链表中倒数第k个节点
空链表，临时指针(指向空链表)
两个指针，依次循环，一次加入到空链表
循环结束后，判断两个链表是否都遍历完
21. 合并两个有序链表
if(head === null || head.next === null)const last = reverse(head.next)head.next.next = head;head.next = null;
递归法
交换顺序var tmp = cur.next;cur.next = pre;pre = cur;cur = tmp;
非递归法
剑指 Offer II 024. 反转链表
双指针找到中间位置
if (fast !== null) slow = slow.next;校验是双数还是单数位置
while(cur !== null) { const tmp = cur.next; cur.next = pre; pre = cur; cur = cur.next;}
右侧链表做一次reverse
递归判断对应位置是否一致即可
剑指 Offer II 027. 回文链表
链表
1373.二叉搜索子树的最大键值和
维护一个队列[root]
while(queue.length)
cur = queue.shift()
res.push(null)
判断cur是否为null
不为空，把cur.left，cur.right分别入队
序列化
维护一个队列[root]及序列化结果arr
left === null;parent.left = null
left !== nullparent.left = new TreeNode(left)queue.push(parent.left)
parent = queue.shift(); left = arr.shift()
right === null;parent.right = null
left !== nullparent.right = new TreeNode(right)queue.push(parent.right)
right = arr.shift()
反序列化
程序遍历
297.二叉树的序列化与反序列化
1483. 树节点的第 K 个祖先
去掉叶子0的节点
后序遍历
判断为空的条件：root.left === null && root.right === null && root.val === 0 => return null
814. 二叉树剪枝
栈stack = [root]
while(stack.length)
层数概念，就是当前stack的length
parent = stack.shift
parent.left => stack.push(parent.left)
parent.right => stack.push(parent.right)
102. 二叉树的层序遍历
结果做一下倒序处理
107.⼆叉树的层次遍历 II
114. 将二叉树展开为链表
i === 0 => point = parent
point.next = parent;point = point.next;
需要有一个point指向该层的第一个TreeNode
116. 填充二叉树节点的右侧指针
117.填充每个节点的下⼀个右侧节点指针II
i===len - 1 => res.push(parent.val)只添加层的最后一个元素值
199.⼆叉树的右视图
654.最大二叉树
parent.children.length => stack.push(parent.children[j])
429.N叉树的层序遍历
515. 在每个树行中找最大值
105.从前序与中序遍历序列构造二叉树
106.从中序与后序遍历序列构造二叉树
652. 寻找重复的子树
230.二叉搜索树中第K小的元素
538. 二叉搜索树转化累加树
同538
1038. BST 转累加树
root.left === null && root.right === null => null
root.left !== null && root.right === null => root.left
root.right !== null && root.left === null => root.right
while(cur.left) => cur = cur.left
把root.left移动到root.right的左叶子节点
把root = root.right
root.right !== null && root.right !== null
root.val === key
450. 删除二叉搜索树中的节点
669. 修剪二叉搜索树
701.二叉搜索树中的插入操作
98.验证二叉搜索树
穷举
95.不同的二叉搜索树II
341. 扁平化嵌套列表迭代器
261. 以图判树
root=== null，return
判断叶子节点，root.left === null && root.right === null
上述条件成立，res+=XX
递归左子树，递归右子树
回溯法
剑指 Offer II 049. 从根节点到叶节点的路径数字之和
遍历pLeft.left左孩子，获取深度deepLeft
遍历pRight.right右孩子，获取深度deepRight
如果深度相同，是满二叉树
否则是完全二叉树，return 1 + fn(root.left) + fn(root.right)
迭代法
222. 完全二叉树的节点个数
if (root === p || root === q || root === null) return root;
if(p !== null && q !== null) return root
左子树和右子树都不为null，return root
return left === null ? right : left
有一方为空
236. 二叉树的最近公共祖先
找出dp含义
res += left * right
思路
记录栈stack=[root]
while循环for(let i= 0; i < len;i++) { if (i === 0) res = parent.val 入栈parent.left 入栈parent.right}
513.找树左下角的值
同513题
剑指 Offer II 045. 二叉树最底层最左边的值
类似于112题
113. 路径总和II
先交换左右子树
递归对应左子树
递归对应右子树
226. 翻转二叉树
root === null => null
root.val === val => root
递归返回条件
700.二叉搜索树中的搜索
872. 叶子相似的树
sum += parent.val
for循环
res.push(sum / len)
637.⼆叉树的层平均值
left = null && right != null => false
left != null && right == null => false
left.val != right.val => false
left === null && right === null => true
left === null && right === null => continue;
left === null || right === null || left.val !== right.val => false
stack.push(left.left); stack.push(right.right)
stack.push(left.right); stack.push(right.left)
迭代
101. 对称⼆叉树
root === null return 0;
leftDep = getDepth(root.left)
rightDep = getDepth(root.right)
root == nul => return 0;
stack = [root]
depth++
for() => stack.shift();
接上，parent.left => stack.push()parent.right => stack.push()
迭代---层序遍历
104.⼆叉树的最⼤深度
stack =[root]
while循环->depth++;for(var i = 0; i < length;) { parent = stack.shift(); for(var j of parent.children) parend.children[j] && stack.push(parent.children[j])}
迭代---程序遍历
559. N 叉树的最大深度
root.left === null && root.right !== null => 1 + right
root.right === null && root.left !== null => 1 + left
for() => {stack.shift();parent.left=> stack.push(parent.left);parent.right => stack.push(parent.right)if (parent.left === null && parent.right === null) { return dep}}
111.⼆叉树的最⼩深度
110. 平衡二叉树
257. 二叉树的所有路径
404. 左叶子之和
112.路径总和
530.⼆叉搜索树的最⼩绝对差
501. 二叉搜索树中的众数
235.二叉搜索树的最近公共祖先
108. 将有序数组转换为二叉搜索树
树
死磕算法
0 条评论
回复 删除
下一页
