死磕算法思维导图模板_ProcessOn思维导图、流程图

贪心算法

困难

中等

435. 无重叠区间

子元素区间右侧排序

相交会出现end相交

452. 用最少数量的箭引爆气球

同上一题

134. 加油站

找出对应gas[i] - cost[i]结余

上述条件，小于0，point = i+ 1

简单

回溯算法

字符串

困难

中等

394. 字符串解码

const reg = /[a-zA-Z]+|[0-9]+|\[|\]/g;

const last = () => stack[stack.length - 1];

用到了正则的lastIndex，因为exec和test执行以下，
每执行一次，lastIndex就会往后+1

string.repeat(num)

简单

数组

困难

中等

128. 最长连续序列

算法

525. 连续数组

代码

523. 连续的子数组和

代码

150. 逆波兰表达式求值

代码

剑指 Offer II 036. 后缀表达式

代码

简单

递归

困难

中等

50. Pow(x, n)

代码

200. 岛屿数量

代码

剑指 Offer II 105. 岛屿的最大面积

简单

滑动窗口

困难

239. 滑动窗口最大值

代码

中等

剑指 Offer 59 - II. 队列的最大值

代码

简单

155. 最小栈

代码

动态规划

困难

中等

不同路径

62. 不同路径

代码

63.不同路径II

代码

整数拆分

343. 整数拆分

代码

96.不同的二叉搜索树

树中有相同的

01背包问题

416. 分割等和子集

代码

dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])

698.划分为k个相等的子集

473.火柴拼正方形

1049. 最后一块石头的重量 II

类似于416题，
return sum - dp[target] - dp[target]

代码

474.一和零

代码

完全背包

518. 零钱兑换 II

代码

322. 零钱兑换

代码

377. 组合总和 Ⅳ

代码

279.完全平⽅数

代码

139. 单词拆分

代码

494.目标和

left组合 - right组合 = target，
left + right等于sum，
left = (target + sum) /2

代码

dp[j] += dp[j - nums[i]]

多重背包

分组背包

打家劫舍

198. 打家劫舍

代码

213.打家劫舍II

代码

337. 打家劫舍 III

代码

买卖股票

122. 买卖股票的最佳时机 II

代码

子序列问题

300.最⻓递增⼦序列

代码

674. 最⻓连续递增序列

代码

718. 最长重复子数组

代码

1143. 最长公共子序列

代码

1035.不相交的线

与1143一致

代码

53. 最大子数组和

代码

动态规划

392. 判断子序列

代码

115.不同的⼦序列

583. 两个字符串的删除操作

代码

72. 编辑距离

简单

爬楼梯

509.斐波那契数

代码

70.爬楼梯

代码

一次m个台阶

746.使用最小花费爬楼梯

代码

第一步不需要花费体力，最后一步不需要花费体力

买卖股票

121. 买卖股票的最佳时机

代码

123. 买卖股票的最佳时机 III

代码

188.买卖股票的最佳时机IV

代码

309.最佳买卖股票时机含冷冻期

代码

714. 买卖股票的最佳时机含手续费

代码

链表

困难

23. 合并K个升序链表

采用分治法，两个两个merge

merge(sort(start, mid), sort(mid + 1, end))

25. K 个一组翻转链表

先实现reverse(head)反转

同理解决reverse(a, b)，即节点a -> b之间的链表反转

a.next = 对应的K反转结果

中等

147.对链表进行插入排序

1.head递归往下遍历，知道head === null，
即遍历完毕

2.新pre = ListNode(-1)指针

3.p指向pre的临时指针

4.q指向head的临时指针，在执行head = head.next之前调用

while循环，判断新的head值在pre链表里插入位置

142.环形链表 II

快慢指针

先判断是环

上一步结束，fast是否为链表最后节点

重置slow指针为head，在递归slow !== fast(此时fast = fast.next)

19.删除链表的倒数第N个节点

快慢指针+链表新增个头部节点(涉及到删除操作，需要知道slow的前一个，和下一个)

先遍历到第k个节点，不处理slow指针

继续遍历，此时处理slow指针

当fast结束时，slow即为被删除的节点

92. 反转链表 II

通用公式，reverse(head, n)

if (n === 1) {
// 全局变量暂存
tmp = head.next;
return head;
}
last = reverse(head.next, n - 1)
head.next.next = head;
head.next = tmp;
return head

if (left === 1) {
return reverseN(head, right)
}
head.next = reverseBetween(head.next, left - 1, right - 1);
return head;

725. 分隔链表

代码

1721. 交换链表中的节点

只需要交换节点值

first、cur、last指针

分别代表正数第k个，遍历条件，及倒数第k个

k > 1, first = first.next

k <= 1, last = last.next

cur.next !== null，遍历结束，获得first、last指针

交换节点

445.两数相加II

代码

简单

160. 相交链表

链表1遍历结束，遍历链表2

循环条件p1 !== p2，如果相同肯定相交

876.链表中间结点

快慢指针

循环条件fast !== null && fast.next !== null

循环结束，输出slow

141. 环形链表

快慢指针

slow === fast，就退出循环

剑指 Offer 22. 链表中倒数第k个节点

快慢指针

先遍历到第k个节点，不处理slow

继续遍历处理slow指针

21. 合并两个有序链表

空链表，临时指针(指向空链表)

两个指针，依次循环，一次加入到空链表

循环结束后，判断两个链表是否都遍历完

剑指 Offer II 024. 反转链表

递归法

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 027. 回文链表

双指针找到中间位置

if (fast !== null) slow = slow.next;校验是双数还是单数位置

右侧链表做一次reverse

while(cur !== null) {
const tmp = cur.next;
cur.next = pre;
pre = cur;
cur = cur.next;
}

递归判断对应位置是否一致即可

树

困难

1373.二叉搜索子树的最大键值和

代码

算法

297.二叉树的序列化与反序列化

程序遍历

序列化

维护一个队列[root]

while(queue.length)

cur = queue.shift()

判断cur是否为null

res.push(null)

不为空，把cur.left，cur.right分别入队

反序列化

维护一个队列[root]及序列化结果arr

parent = queue.shift(); left = arr.shift()

left === null;
parent.left = null

left !== null
parent.left = new TreeNode(left)
queue.push(parent.left)

right = arr.shift()

right === null;
parent.right = null

left !== null
parent.right = new TreeNode(right)
queue.push(parent.right)

1483. 树节点的第 K 个祖先

中等

814. 二叉树剪枝

去掉叶子0的节点

后序遍历

判断为空的条件：
root.left === null && root.right === null && root.val === 0
=> return null

102. 二叉树的层序遍历

栈stack = [root]

while(stack.length)

层数概念，就是当前stack的length

parent = stack.shift

parent.left => stack.push(parent.left)

parent.right => stack.push(parent.right)

107.⼆叉树的层次遍历 II

栈stack = [root]

while(stack.length)

层数概念，就是当前stack的length

parent = stack.shift

parent.left => stack.push(parent.left)

parent.right => stack.push(parent.right)

结果做一下倒序处理

114. 将二叉树展开为链表

116. 填充二叉树节点的右侧指针

栈stack = [root]

while(stack.length)

层数概念，就是当前stack的length

parent = stack.shift

需要有一个point指向该层的第一个TreeNode

i === 0 => point = parent

point.next = parent;
point = point.next;

parent.left => stack.push(parent.left)

parent.right => stack.push(parent.right)

117.填充每个节点的下⼀个右侧节点指针II

栈stack = [root]

while(stack.length)

层数概念，就是当前stack的length

parent = stack.shift

需要有一个point指向该层的第一个TreeNode

i === 0 => point = parent

point.next = parent;
point = point.next;

parent.left => stack.push(parent.left)

parent.right => stack.push(parent.right)

199.⼆叉树的右视图

栈stack = [root]

while(stack.length)

层数概念，就是当前stack的length

parent = stack.shift

i===len - 1 => res.push(parent.val)
只添加层的最后一个元素值

parent.left => stack.push(parent.left)

parent.right => stack.push(parent.right)

654.最大二叉树

代码

算法

429.N叉树的层序遍历

栈stack = [root]

while(stack.length)

层数概念，就是当前stack的length

parent = stack.shift

parent.children.length => stack.push(parent.children[j])

515. 在每个树行中找最大值

栈stack = [root]

while(stack.length)

层数概念，就是当前stack的length

parent = stack.shift

max = Math.max(max, parent.val)

105.从前序与中序遍历序列构造二叉树

代码

算法

106.从中序与后序遍历序列构造二叉树

代码

算法

652. 寻找重复的子树

代码

算法

230.二叉搜索树中第K小的元素

代码

538. 二叉搜索树转化累加树

代码

1038. BST 转累加树

同538

450. 删除二叉搜索树中的节点

root.val === key

root.left === null && root.right === null => null

root.left !== null && root.right === null => root.left

root.right !== null && root.left === null => root.right

root.right !== null && root.right !== null

while(cur.left) => cur = cur.left

把root.left移动到root.right的左叶子节点

把root = root.right

if (root.val > key) root.left = deleteNode(root.left, key);

if (root.val < key) root.right = deleteNode(root.right, key)
return root;

669. 修剪二叉搜索树

代码

701.二叉搜索树中的插入操作

代码

算法

98.验证二叉搜索树

代码

算法

95.不同的二叉搜索树II

递归

穷举

341. 扁平化嵌套列表迭代器

代码

算法

261. 以图判树

剑指 Offer II 049. 从根节点到叶节点的路径数字之和

回溯法

root=== null，return

判断叶子节点，root.left === null && root.right === null

上述条件成立，res+=XX

递归左子树，递归右子树

222. 完全二叉树的节点个数

遍历pLeft.left左孩子，获取深度deepLeft

遍历pRight.right右孩子，获取深度deepRight

如果深度相同，是满二叉树

否则是完全二叉树，return 1 + fn(root.left) + fn(root.right)

迭代法

算法

236. 二叉树的最近公共祖先

if (root === p || root === q || root === null) return root;

let left = lowestCommonAncestor(root.left, p, q)

let right = lowestCommonAncestor(root.right, p, q)

左子树和右子树都不为null，return root

if(p !== null && q !== null) return root

有一方为空

return left === null ? right : left

96.不同的二叉搜索树

递归

穷举

动态规划

找出dp含义

找出递推公式, dp[i] += dp[j - 1] * dp[i - j]

513.找树左下角的值

记录栈stack=[root]

while循环
for(let i= 0; i < len;i++) {
if (i === 0) res = parent.val
入栈parent.left
入栈parent.right
}

剑指 Offer II 045. 二叉树最底层最左边的值

同513题

113. 路径总和II

类似于112题

算法

简单

226. 翻转二叉树

先交换左右子树

递归对应左子树

递归对应右子树

700.二叉搜索树中的搜索

递归返回条件

root === null => null

root.val === val => root

searchTree(root.right || root.left, val)

872. 叶子相似的树

637.⼆叉树的层平均值

栈stack = [root]

while(stack.length)

层数概念，就是当前stack的length

for循环

parent = stack.shift

sum += parent.val

parent.left => stack.push(parent.left)

parent.right => stack.push(parent.right)

res.push(sum / len)

101. 对称⼆叉树

递归

left = null && right != null => false

left != null && right == null => false

left.val != right.val => false

left === null && right === null => true

外侧比对，compare(left.left, right.right)

内侧比对，compare(left.right, right.left)

迭代

stack = [root.left, root.right]

while(stack.length)

left = stack.shift(), right = stack.shift()

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)

104.⼆叉树的最⼤深度

递归

root === null return 0;

leftDep = getDepth(root.left)

rightDep = getDepth(root.right)

1 + Math.max(leftDepth, rightDepth)

迭代---层序遍历

root == nul => return 0;

stack = [root]

while(stack.length)

depth++

for() => stack.shift();

接上，parent.left => stack.push()
parent.right => stack.push()

559. N 叉树的最大深度

递归

root === null return 0;

depth = Math.max(leftDepth, maxDep(root.children[i]))

迭代---程序遍历

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])
}

111.⼆叉树的最⼩深度

递归

root.left === null && root.right !== null => 1 + right

root.right === null && root.left !== null => 1 + left

dep = 1 + Math.min(left, right)

迭代

root == nul => return 0;

stack = [root]

while(stack.length)

depth++

for() => {
stack.shift();
parent.left=> stack.push(parent.left);
parent.right => stack.push(parent.right)
if (parent.left === null && parent.right === null) {
return dep
}
}

110. 平衡二叉树

算法

257. 二叉树的所有路径

算法

404. 左叶子之和

算法

112.路径总和

算法

530.⼆叉搜索树的最⼩绝对差

算法

501. 二叉搜索树中的众数

算法

235.二叉搜索树的最近公共祖先

算法

108. 将有序数组转换为二叉搜索树

代码