三天学会算法
算法的设计真的很美,有时候会佩服设计的人真厉害
- https://www.iamshuaidi.com/ (opens new window)
- https://codetop.cc/#/home (opens new window)
- https://juejin.cn/book/6844733800300150797 (opens new window)
- https://leetcode-cn.com/leetbook/detail/top-interview-questions-easy/ (opens new window)
- http://febook.hzfe.org/awesome-interview/ (opens new window)
91 天学算法 Leetcode 图解题解集合 notion 笔记主要是 #Leetcode 经典题目的解析，包括思路，代码实现和复杂度分析，部分题解包含手绘图解。
# 两数之和
https://leetcode-cn.com/problems/two-sum/ (opens new window)
真题描述： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
function twoSum(nums, target) {
const diff = new Map();
const len = nums.length;
for (let i = 0; i < len; i++) {
const num = nums[i];
// target-当前值的差值是否存在
if (diff.get(target - num) !== undefined) {
return [diff.get(target - num), i];
}
// 不存在则记录当前值
diff.set(num, i);
}
}
# 三数之和
https://leetcode-cn.com/problems/3sum/ (opens new window)
真题描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
const threeSum = function (nums, target) {
// 用于存放数组结果
let res = [];
// 排序
nums = nums.sort((a, b) => a - b);
// 缓存length
const len = nums.length;
for (let i = 0; i < len; i++) {
// 左指针j
let j = i + 1;
// 右指针k
let k = len - 1;
// 如果遇到重复的数字，则跳过
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
while (j < k) {
// 三数之和小于0，左指针前进
if (nums[i] + nums[j] + nums[k] < 0) {
j++;
// 处理左指针元素重复的情况
while (nums[j] === nums[j - 1]) {
j++;
}
} else if (nums[i] + nums[j] + nums[k] > 0) {
// 三数之和大于0，右指针后退
k--;
while (nums[k] === nums[k + 1]) {
k--;
}
} else {
// 得到的目标组合，推入结果数组
res.push([nums[i], nums[j], nums[k]]);
// 左右指针一起前进
j++;
k--;
// 若左指针元素重复，跳过
while (nums[j] === nums[j - 1]) {
j++;
}
// 若有指针元素重复，跳过
while (nums[k] === nums[k + 1]) {
k--;
}
}
}
}
return res;
};
console.log(threeSum([-1, 0, 1, 2, -1, -4]));
# 回文字符串
https://leetcode-cn.com/problems/RQku0D/ (opens new window)
真题描述：给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串
const validPalindrome = function (s) {
// 缓存字符串长度
const len = s.length;
let i = 0;
let j = len - 1;
while (i < j && s[i] === s[j]) {
i++;
j--;
}
// 尝试判断跳过左指针元素后，字符串是否回文
if (isPalindrome(i + 1, j)) {
return true;
}
// 常识判断跳过右指针元素后，字符串是否回文
if (isPalindrome(i, j - 1)) {
return true;
}
// 工具方法，判断字符串是否回文
function isPalindrome(st, ed) {
while (st < ed) {
if (s[st] !== s[ed]) {
return false;
}
st++;
ed--;
}
return true;
}
return false;
};
console.log(validPalindrome("abca"));
# 链表的合并
https://leetcode-cn.com/problems/merge-two-sorted-lists/ (opens new window)
真题描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
const mergeTwoLists = function (l1, l2) {
// 定义头结点，确保链表可以访问
let head = new ListNode();
// cur 这里就是咱们的针
let cur = head;
// 针开始穿梭
while (l1 && l2) {
// 如果l1的节点值较小
if (l1.val <= l2.val) {
// 先串起l1的节点
cur.next = l1;
// l1往前一步
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
// 针在串起一个节点后，也会往前走一步
cur = cur.next;
}
cur.next = l1 !== null ? l1 : l2;
return head.next;
};
const l1 = {
val: 1,
next: {
val: 2,
next: {
val: 3,
next: null,
},
},
};
const l2 = {
val: 1,
next: {
val: 3,
next: {
val: 4,
next: null,
},
},
};
console.log(mergeTwoLists(l1, l2));
# 链表的删除
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/ (opens new window)
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/ (opens new window)
真题描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->2->3->3 输出: 1->2->3
function ListNode(val) {
this.val = val;
this.next = null;
}
const deleteDuplicates = function (head) {
let cur = head;
while (cur !== null && cur.next !== null) {
if (cur.val === cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
};
console.log(
deleteDuplicates({
val: 1,
next: {
val: 1,
next: {
val: 3,
next: null,
},
},
})
);
# 链表删除，dummy
真题描述：给定一个排序链表，删除所有含有重复数字的结点，只保留原始链表中 没有重复出现的数字。
输入: 1->2->3->3->4->4->5 输出: 1->2->5 示例 2: 输入: 1->1->1->2->3 输出: 2->3
function ListNode(val) {
this.val = val;
this.next = null;
}
const deleteDuplicates = function (head) {
if (!head || !head.next) {
return head;
}
let dummy = new ListNode();
dummy.next = head;
let cur = dummy;
while (cur.next && cur.next.next) {
if (cur.next.val === cur.next.next.val) {
let val = cur.next.val;
cur.next = cur.next.next.next;
while (cur.next && cur.next.val === val) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
};
console.log(
deleteDuplicates({
val: 1,
next: {
val: 1,
next: {
val: 1,
next: {
val: 2,
next: {
val: 3,
next: null,
},
},
},
},
})
);
# 总结
- head 是链表
- cur 是指针
- dummy 是链表的前一项的虚拟节点，当 head 有可能发生改变时使用
# 快慢指针
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/ (opens new window)
真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个结点后，链表变为 1->2->3->5.
function ListNode(val) {
this.val = val;
this.next = null;
}
const removeNthFromEnd = function (head, n) {
// 初始化 dummy 结点
const dummy = new ListNode();
// dummy 指向头结点
dummy.next = head;
// 初始化快慢指针，均指向 dummy
let fast = dummy;
let slow = dummy;
// 快指针闷头走 n 步
while (n !== 0) {
fast = fast.next;
n--;
}
// 快慢指针一起走
while (fast.next) {
fast = fast.next;
slow = slow.next;
}
// 慢指针删除自己的后继结点
slow.next = slow.next.next;
// 返回头结点
return dummy.next;
};
console.log(
removeNthFromEnd(
{
val: 1,
next: {
val: 2,
next: {
val: 3,
next: {
val: 4,
next: {
val: 5,
next: null,
},
},
},
},
},
2
)
);
# 链表的反转
https://leetcode-cn.com/problems/reverse-linked-list/ (opens new window)
function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
const reverseListNode = function (head) {
if (!head || head.next) {
return head;
}
let pre = null;
let cur = head;
while (cur !== null) {
let next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
};
console.log(
reverseListNode(
{
val: 1,
next: {
val: 2,
next: {
val: 3,
next: {
val: 4,
next: {
val: 5,
next: null,
},
},
},
},
},
2
)
);
# 局部反转一个链表
https://leetcode-cn.com/problems/reverse-linked-list-ii/ (opens new window)
真题描述：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转
输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
// 入参是头结点、m、n
const reverseBetween = function (head, m, n) {
// 定义pre、cur，用leftHead来承接整个区间的前驱结点
let pre, cur, leftHead;
// 别忘了用 dummy 嗷
const dummy = new ListNode();
// dummy后继结点是头结点
dummy.next = head;
// p是一个游标，用于遍历，最初指向 dummy
let p = dummy;
// p往前走 m-1 步，走到整个区间的前驱结点处
for (let i = 0; i < m - 1; i++) {
p = p.next;
}
// 缓存这个前驱结点到 leftHead 里
leftHead = p;
// start 是反转区间的第一个结点
let start = leftHead.next;
// pre 指向start
pre = start;
// cur 指向 start 的下一个结点
cur = pre.next;
// 开始重复反转动作
for (let i = m; i < n; i++) {
let next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// leftHead 的后继结点此时为反转后的区间的第一个结点
leftHead.next = pre;
// 将区间内反转后的最后一个结点 next 指向 cur
start.next = cur;
// dummy.next 永远指向链表头结点
return dummy.next;
};
# 环形链表
就是立 flag，等到下次发现 flag 说明就是个环
https://leetcode-cn.com/problems/linked-list-cycle/ (opens new window)
/**
* @param {ListNode} head
* @return {boolean}
*/
// 入参是头结点
const hasCycle = function (head) {
// 只要结点存在，那么就继续遍历
while (head) {
// 如果 flag 已经立过了，那么说明环存在
if (head.flag) {
return true;
} else {
// 如果 flag 没立过，就立一个 flag 再往
head.flag = true;
head = head.next;
}
}
return false;
};
# 判断换的起点
第一次发现 flag 的时候就是环的起点
/**
* @param {ListNode} head
* @return {boolean}
*/
// 入参是头结点
const hasCycle = function (head) {
// 只要结点存在，那么就继续遍历
while (head) {
// 如果 flag 已经立过了，那么说明环存在
if (head.flag) {
return head;
} else {
// 如果 flag 没立过，就立一个 flag 再往
head.flag = true;
head = head.next;
}
}
return false;
};
# 快慢指针思路找起点
定义慢指针 slow，快指针 fast。两者齐头并进， slow 一次走一步、fast 一次 走两步。这样如果它们是在一个有环的链表里移动，一定有相遇的时刻。这个原理证明起来也比较简单：我们假设移动的次数为 t，slow 移动的路程就是 t，fast 移动的路程为 2t，假如环的长度为 s，那么当下面这个条件：
2t - t = s
也就是：
t = s
满足时，slow 和 fast 就一定会相遇。反之，如果两者没有相遇，同时 fast 遍历到了链表的末尾，发现 next 指针指向 null，则链表中不存在环。
var detectCycle = function (head) {
// 快慢指针初始化指向 head
let slow = head;
let fast = head;
// 快指针走到末尾时停止
while (fast && fast.next) {
// 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
// 快慢指针相遇，说明含有环
if (slow == fast) {
// 任一一节点指向头节点
fast = head;
// 同步向前进
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
// 返回入口节点
return fast;
}
}
// 不包含环
return false;
};
# 有效括号
https://leetcode-cn.com/problems/valid-parentheses/ (opens new window)
题目描述：给定一个只包括 '('，')'，'{'，'}','[',']' 的字符串，判断字符串是否有效
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true
示例 2:
输入: "()[]{}" 输出: true
示例 3:
输入: "(]" 输出: false
示例 4:
输入: "([)]" 输出: false
示例 5:
输入: "{[]}" 输出: true
// 用一个 map 来维护左括号和右括号的对应关系
const leftToRight = {
"(": ")",
"[": "]",
"{": "}",
};
/**
* @param {string} s
* @return {boolean}
*/
const isValid = function (s) {
// 结合题意，空字符串无条件判断为 true
if (!s) {
return true;
}
const leftToRight = {
"(": ")",
"{": "}",
"[": "]",
};
const stack = [];
for (let i = 0; i < s.length; i++) {
if (["(", "{", "["].includes(s[i])) {
stack.push(leftToRight[s[i]]);
} else {
if (s[i] !== stack.pop()) {
return false;
}
}
}
return !stack.length;
};
# 每日温度问题
https://leetcode-cn.com/problems/daily-temperatures/ (opens new window)
题目描述: 根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
理解动图：https://www.bilibili.com/video/BV12t4y1274o/ (opens new window)
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function (temperatures) {
const stack = [];
const res = new Array(temperatures.length).fill(0);
for (let i = 0; i < temperatures.length; i++) {
while (
stack.length &&
temperatures[stack[stack.length - 1]] < temperatures[i]
) {
const top = stack.pop();
res[top] = i - top;
}
stack.push(i);
}
return res;
};
# 如何用栈实现队列
https://leetcode-cn.com/problems/implement-queue-using-stacks/ (opens new window)
/**
* 初始化构造函数
*/
const MyQueue = function () {
// 初始化两个栈
this.stack1 = [];
this.stack2 = [];
};
/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
// 直接调度数组的 push 方法
this.stack1.push(x);
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function () {
// 假如 stack2 为空，需要将 stack1 的元素转移进来
if (this.stack2.length <= 0) {
// 当 stack1 不为空时，出栈
while (this.stack1.length !== 0) {
// 将 stack1 出栈的元素推入 stack2
this.stack2.push(this.stack1.pop());
}
}
// 为了达到逆序的目的，我们只从 stack2 里出栈元素
return this.stack2.pop();
};
/**
* Get the front element.
* @return {number}
* 这个方法和 pop 唯一的区别就是没有将定位到的值出栈
*/
MyQueue.prototype.peek = function () {
if (this.stack2.length <= 0) {
// 当 stack1 不为空时，出栈
while (this.stack1.length != 0) {
// 将 stack1 出栈的元素推入 stack2
this.stack2.push(this.stack1.pop());
}
}
// 缓存 stack2 的长度
const stack2Len = this.stack2.length;
return stack2Len && this.stack2[stack2Len - 1];
};
/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
// 若 stack1 和 stack2 均为空，那么队列空
return !this.stack1.length && !this.stack2.length;
};
# 滑动窗口的最大值
https://leetcode-cn.com/problems/sliding-window-maximum/ (opens new window)
题目描述：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7]
解释: 滑动窗口的位置
[1 3 -1] -3 5 3 6 7
1 [3 -1 -3] 5 3 6 7
1 3 [-1 -3 5] 3 6 7
1 3 -1 [-3 5 3] 6 7
1 3 -1 -3 [5 3 6] 7
1 3 -1 -3 5 [3 6 7]
最大值分别对应：
3 3 5 5 6 7
提示：你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
# 双指针+遍历法
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function (nums, k) {
let left = 0;
let right = k - 1;
let res = [];
const calcMax = function (arr, left, right) {
let maxNum = arr[left];
for (let i = left; i <= right; i++) {
if (nums[i] > maxNum) {
maxNum = nums[i];
}
}
return maxNum;
};
while (right < nums.length) {
let max = calcMax(nums, left, right);
res.push(max);
left++;
right++;
}
return res;
};
# 双端队列
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function (nums, k) {
// 缓存数组的长度
const len = nums.length;
// 初始化结果数组
const res = [];
// 初始化双端队列
const deque = [];
// 开始遍历数组
for (let i = 0; i < len; i++) {
// 当队尾元素小于当前元素时
while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
// 将队尾元素（索引）不断出队，直至队尾元素大于等于当前元素
deque.pop();
}
// 入队当前元素索引（注意是索引）
deque.push(i);
// 当队头元素的索引已经被排除在滑动窗口之外时
while (deque.length && deque[0] <= i - k) {
// 将队头元素索引出队
deque.shift();
}
// 判断滑动窗口的状态，只有在被遍历的元素个数大于 k 的时候，才更新结果数组
if (i >= k - 1) {
res.push(nums[deque[0]]);
}
}
// 返回结果数组
return res;
};
# 深度优先搜索和广度优先搜索
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/ (opens new window)
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ (opens new window)
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如: 给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var levelOrder = function (root) {
const res = [];
if (!root) {
return res;
}
const queue = [];
queue.push(root);
while (queue.length !== 0) {
const top = queue.shift();
res.push(top.val);
if (top.left) {
queue.push(top.left);
}
if (top.right) {
queue.push(top.right);
}
}
return res;
};
# 全排列
https://leetcode-cn.com/problems/permutations/78 (opens new window).
/**
* @param {number[]} nums
* @return {number[][]}
*/
// 入参是一个数组
const permute = function (nums) {
// 缓存数组的长度
const len = nums.length;
// curr 变量用来记录当前的排列内容
const curr = [];
// res 用来记录所有的排列顺序
const res = [];
// visited 用来避免重复使用同一个数字
const visited = {};
// 定义 dfs 函数，入参是坑位的索引（从 0 计数）
function dfs(nth) {
// 若遍历到了不存在的坑位（第 len+1 个），则触碰递归边界返回
if (nth === len) {
// 此时前 len 个坑位已经填满，将对应的排列记录下来
res.push(curr.slice());
return;
}
// 检查手里剩下的数字有哪些
for (let i = 0; i < len; i++) {
// 若 nums[i] 之前没被其它坑位用过，则可以理解为“这个数字剩下了”
if (!visited[nums[i]]) {
// 给 nums[i] 打个“已用过”的标
visited[nums[i]] = 1;
// 将nums[i]推入当前排列
curr.push(nums[i]);
// 基于这个排列继续往下一个坑走去
dfs(nth + 1);
// nums[i]让出当前坑位
curr.pop();
// 下掉“已用过”标识
visited[nums[i]] = 0;
}
}
}
// 从索引为 0 的坑位（也就是第一个坑位）开始 dfs
dfs(0);
return res;
};
# 跳过没有看完的
https://juejin.cn/book/6844733800300150797/section/6844733800358871048 (opens new window)
# 迭代法先序遍历
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/ (opens new window)
使用迭代法，while，要注意后进先出，所以这里先判断 right，和递归法相反
/**
* @param {TreeNode} root
* @return {number[]}
*/
const preorderTraversal = function (root) {
// 定义结果数组
const res = [];
// 处理边界条件
if (!root) {
return res;
}
// 初始化栈结构
const stack = [];
// 首先将根结点入栈
stack.push(root);
// 若栈不为空，则重复出栈、入栈操作
while (stack.length) {
// 将栈顶结点记为当前结点
const cur = stack.pop();
// 当前结点就是当前子树的根结点，把这个结点放在结果数组的尾部
res.push(cur.val);
// 若当前子树根结点有右孩子，则将右孩子入栈
if (cur.right) {
stack.push(cur.right);
}
// 若当前子树根结点有左孩子，则将左孩子入栈
if (cur.left) {
stack.push(cur.left);
}
}
// 返回结果数组
return res;
};
# 迭代法后序遍历
/**
* @param {TreeNode} root
* @return {number[]}
*/
const preorderTraversal = function (root) {
// 定义结果数组
const res = [];
// 处理边界条件
if (!root) {
return res;
}
// 初始化栈结构
const stack = [];
// 首先将根结点入栈
stack.push(root);
// 若栈不为空，则重复出栈、入栈操作
while (stack.length) {
// 将栈顶结点记为当前结点
const cur = stack.pop();
// 当前结点就是当前子树的根结点，把这个结点放在结果数组的尾部
res.push(cur.val);
// 若当前子树根结点有右孩子，则将右孩子入栈
if (cur.right) {
stack.push(cur.right);
}
// 若当前子树根结点有左孩子，则将左孩子入栈
if (cur.left) {
stack.push(cur.left);
}
}
// 返回结果数组
return res;
};
# 迭代法中序遍历
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/ (opens new window)
刚开始 cur 当做向左的游标，left 到头的时候，又充当向右的游标
/**
* @param {TreeNode} root
* @return {number[]}
*/
const inorderTraversal = function (root) {
// 定义结果数组
const res = [];
// 初始化栈结构
const stack = [];
// 用一个 cur 结点充当游标
let cur = root;
// 当 cur 不为空、或者 stack 不为空时，重复以下逻辑
while (cur || stack.length) {
// 这个 while 的作用是把寻找最左叶子结点的过程中，途径的所有结点都记录下来
while (cur) {
// 将途径的结点入栈
stack.push(cur);
// 继续搜索当前结点的左孩子
cur = cur.left;
}
// 取出栈顶元素
cur = stack.pop();
// 将栈顶元素入栈
res.push(cur.val);
// 尝试读取 cur 结点的右孩子
cur = cur.right;
}
// 返回结果数组
return res;
};
# 层序遍历延伸
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ (opens new window)
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
/**
* @param {TreeNode} root
* @return {number[][]}
*/
const levelOrder = function (root) {
// 初始化结果数组
const res = [];
// 处理边界条件
if (!root) {
return res;
}
// 初始化队列
const queue = [];
// 队列第一个元素是根结点
queue.push(root);
// 当队列不为空时，反复执行以下逻辑
while (queue.length) {
// level 用来存储当前层的结点
const level = [];
// 缓存刚进入循环时的队列长度，这一步很关键，因为队列长度后面会发生改变
const len = queue.length;
// 循环遍历当前层级的结点
for (let i = 0; i < len; i++) {
// 取出队列的头部元素
const top = queue.shift();
// 将头部元素的值推入 level 数组
level.push(top.val);
// 如果当前结点有左孩子，则推入下一层级
if (top.left) {
queue.push(top.left);
}
// 如果当前结点有右孩子，则推入下一层级
if (top.right) {
queue.push(top.right);
}
}
// 将 level 推入结果数组
res.push(level);
}
// 返回结果数组
return res;
};
# 反转二叉树
https://leetcode-cn.com/problems/invert-binary-tree/ (opens new window)
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
const invertTree = function (root) {
// 定义递归边界
if (!root) {
return root;
}
// 递归交换右孩子的子结点
let right = invertTree(root.right);
// 递归交换左孩子的子结点
let left = invertTree(root.left);
// 交换当前遍历到的两个左右孩子结点
root.left = right;
root.right = left;
return root;
};
我自己是这样写的,也通过了
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function (root) {
if (!root) {
return root;
}
let right = root.right;
let left = root.left;
root.left = right;
root.right = left;
invertTree(root.right);
invertTree(root.left);
return root;
};
# 搜索二叉树，插入新节点
https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/submissions/ (opens new window)
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
var insertIntoBST = function (root, val) {
if (!root) {
root = new TreeNode(val);
return root;
}
if (root.val < val) {
root.right = insertIntoBST(root.right, val);
}
if (root.val > val) {
root.left = insertIntoBST(root.left, val);
}
return root;
};
# 删除二叉搜索树中的节点
https://leetcode-cn.com/problems/delete-node-in-a-bst/ (opens new window)
function deleteNode(root, n) {
// 如果没找到目标结点，则直接返回
if (!root) {
return root;
}
// 定位到目标结点，开始分情况处理删除动作
if (root.val === n) {
// 若是叶子结点，则不需要想太多，直接删除
if (!root.left && !root.right) {
root = null;
} else if (root.left) {
// 寻找左子树里值最大的结点
const maxLeft = findMax(root.left);
// 用这个 maxLeft 覆盖掉需要删除的当前结点
root.val = maxLeft.val;
// 覆盖动作会消耗掉原有的 maxLeft 结点
root.left = deleteNode(root.left, maxLeft.val);
} else {
// 寻找右子树里值最小的结点
const minRight = findMin(root.right);
// 用这个 minRight 覆盖掉需要删除的当前结点
root.val = minRight.val;
// 覆盖动作会消耗掉原有的 minRight 结点
root.right = deleteNode(root.right, minRight.val);
}
} else if (root.val > n) {
// 若当前结点的值比 n 大，则在左子树中继续寻找目标结点
root.left = deleteNode(root.left, n);
} else {
// 若当前结点的值比 n 小，则在右子树中继续寻找目标结点
root.right = deleteNode(root.right, n);
}
return root;
}
// 寻找左子树最大值
function findMax(root) {
while (root.right) {
root = root.right;
}
return root;
}
// 寻找右子树的最小值
function findMin(root) {
while (root.left) {
root = root.left;
}
return root;
}
# 二叉搜索树的验证
https://leetcode-cn.com/problems/validate-binary-search-tree/ (opens new window)
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function (root) {
// 定义递归函数
function dfs(root, minValue, maxValue) {
// 若是空树，则合法
if (!root) {
return true;
}
// 若右孩子不大于根结点值，或者左孩子不小于根结点值，则不合法
if (root.val <= minValue || root.val >= maxValue) return false;
// 左右子树必须都符合二叉搜索树的数据域大小关系
return (
dfs(root.left, minValue, root.val) && dfs(root.right, root.val, maxValue)
);
}
// 初始化最小值和最大值为极小或极大
return dfs(root, -Infinity, Infinity);
};
# 将排序数组转化为二叉搜索树
https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/ (opens new window)
/**
* @param {number[]} nums
* @return {TreeNode}
*/
const sortedArrayToBST = function (nums) {
// 处理边界条件
if (!nums.length) {
return null;
}
// root 结点是递归“提”起数组的结果
const root = buildBST(0, nums.length - 1);
// 定义二叉树构建函数，入参是子序列的索引范围
function buildBST(low, high) {
// 当 low > high 时，意味着当前范围的数字已经被递归处理完全了
if (low > high) {
return null;
}
// 二分一下，取出当前子序列的中间元素
const mid = Math.floor(low + (high - low) / 2);
// 将中间元素的值作为当前子树的根结点值
const cur = new TreeNode(nums[mid]);
// 递归构建左子树，范围二分为[low,mid)
cur.left = buildBST(low, mid - 1);
// 递归构建左子树，范围二分为为(mid,high]
cur.right = buildBST(mid + 1, high);
// 返回当前结点
return cur;
}
// 返回根结点
return root;
};
# 平衡二叉树跳过
https://juejin.cn/book/6844733800300150797/section/6844733800363065358 (opens new window)
# 冒泡排序
function betterBubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len; i++) {
// 区别在这里，我们加了一个标志位
let flag = false;
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
// 只要发生了一次交换，就修改标志位
flag = true;
}
}
// 若一次交换也没发生，则说明数组有序，直接放过
if (flag == false) return arr;
}
return arr;
}
# 选择排序
function selectSort(arr) {
// 缓存数组长度
const len = arr.length;
// 定义 minIndex，缓存当前区间最小值的索引，注意是索引
let minIndex;
// i 是当前排序区间的起点
for (let i = 0; i < len - 1; i++) {
// 初始化 minIndex 为当前区间第一个元素
minIndex = i;
// i、j分别定义当前区间的上下界，i是左边界，j是右边界
for (let j = i; j < len; j++) {
// 若 j 处的数据项比当前最小值还要小，则更新最小值索引为 j
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 如果 minIndex 对应元素不是目前的头部元素，则交换两者
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
# 插入排序
function insertSort(arr) {
// 缓存数组长度
const len = arr.length;
// temp 用来保存当前需要插入的元素
let temp;
// i用于标识每次被插入的元素的索引
for (let i = 1; i < len; i++) {
// j用于帮助 temp 寻找自己应该有的定位
let j = i;
temp = arr[i];
// 判断 j 前面一个元素是否比 temp 大
while (j > 0 && arr[j - 1] > temp) {
// 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
arr[j] = arr[j - 1];
j--;
}
// 循环让位，最后得到的 j 就是 temp 的正确索引
arr[j] = temp;
}
return arr;
}
# 归并排序
function mergeSort(arr) {
const len = arr.length;
if (len < 1) {
return arr;
}
const mid = Math.floor(len / 2);
const leftArr = mergeSort(arr.slice(0, mid));
const rightArr = mergeSort(arr.slice(mid, len));
arr = mergeArr(leftArr, rightArr);
return arr;
}
function mergeArr(arr1, arr2) {
let i = 0;
let j = 0;
const res = [];
const len1 = arr1.length;
const len2 = arr2.length;
while (i < len2 && j < len2) {
if (arr[i] < arr[j]) {
res.push(arr[i]);
i++;
} else {
res.push(arr[j]);
j++;
}
}
if (i < len1) {
return res.concat(arr1.slice(i));
} else {
return res.concat(arr2.slice(j));
}
}
# 快速排序
快速排序并不会把真的数组分割开来再合并到一个新数组中去，而是直接在原有的数组内部进行排序
// 快速排序入口
function quickSort(arr, left = 0, right = arr.length - 1) {
// 定义递归边界，若数组只有一个元素，则没有排序必要
if (arr.length > 1) {
// lineIndex表示下一次划分左右子数组的索引位
const lineIndex = partition(arr, left, right);
// 如果左边子数组的长度不小于1，则递归快排这个子数组
if (left < lineIndex - 1) {
// 左子数组以 lineIndex-1 为右边界
quickSort(arr, left, lineIndex - 1);
}
// 如果右边子数组的长度不小于1，则递归快排这个子数组
if (lineIndex < right) {
// 右子数组以 lineIndex 为左边界
quickSort(arr, lineIndex, right);
}
}
return arr;
}
// 以基准值为轴心，划分左右子数组的过程
function partition(arr, left, right) {
// 基准值默认取中间位置的元素
let pivotValue = arr[Math.floor(left + (right - left) / 2)];
// 初始化左右指针
let i = left;
let j = right;
// 当左右指针不越界时，循环执行以下逻辑
while (i <= j) {
// 左指针所指元素若小于基准值，则右移左指针
while (arr[i] < pivotValue) {
i++;
}
// 右指针所指元素大于基准值，则左移右指针
while (arr[j] > pivotValue) {
j--;
}
// 若i<=j，则意味着基准值左边存在较大元素或右边存在较小元素，交换两个元素确保左右两侧有序
if (i <= j) {
swap(arr, i, j);
i++;
j--;
}
}
// 返回左指针索引作为下一次划分左右子数组的依据
return i;
}
// 快速排序中使用 swap 的地方比较多，我们提取成一个独立的函数
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
# 动态规划
# 最少硬币数目
https://leetcode-cn.com/problems/gaM7Ch/ (opens new window)
const coinChange = function (coins, amount) {
// 用于保存每个目标总额对应的最小硬币个数
const f = [];
// 提前定义已知情况
f[0] = 0;
// 遍历 [1, amount] 这个区间的硬币总额
for (let i = 1; i <= amount; i++) {
// 求的是最小值，因此我们预设为无穷大，确保它一定会被更小的数更新
f[i] = Infinity;
// 循环遍历每个可用硬币的面额
for (let j = 0; j < coins.length; j++) {
// 若硬币面额小于目标总额，则问题成立
if (i - coins[j] >= 0) {
// 状态转移方程
f[i] = Math.min(f[i], f[i - coins[j]] + 1);
}
}
}
// 若目标总额对应的解为无穷大，则意味着没有一个符合条件的硬币总数来更新它，本题无解，返回-1
if (f[amount] === Infinity) {
return -1;
}
// 若有解，直接返回解的内容
return f[amount];
};
# 背包问题
有 n 件物品，物品体积用一个名为 w 的数组存起来，物品的价值用一个名为 value 的数组存起来；每件物品的体积用 w[i] 来表示，每件物品的价值用 value[i] 来表示。现在有一个容量为 c 的背包，问你如何选取物品放入背包，才能使得背包内的物品总价值最大？
注意：每种物品都只有 1 件
// 入参是物品的个数和背包的容量上限，以及物品的重量和价值数组
function knapsack(n, c, w, value) {
// dp是动态规划的状态保存数组
const dp = new Array(c + 1).fill(0);
// res 用来记录所有组合方案中的最大值
let res = -Infinity;
for (let i = 1; i <= n; i++) {
for (let v = c; v >= w[i]; v--) {
// 写出状态转移方程
dp[v] = Math.max(dp[v], dp[v - w[i]] + value[i]);
// 即时更新最大值
if (dp[v] > res) {
res = dp[v];
}
}
}
return res;
}
# 最长上升子序列
https://leetcode-cn.com/problems/longest-increasing-subsequence/ (opens new window)
/**
* @param {number[]} nums
* @return {number}
*/
// 入参是一个数字序列
const lengthOfLIS = function (nums) {
// 缓存序列的长度
const len = nums.length;
// 处理边界条件
if (!len) {
return 0;
}
// 初始化数组里面每一个索引位的状态值
const dp = new Array(len).fill(1);
// 初始化最大上升子序列的长度为1
let maxLen = 1;
// 从第2个元素开始，遍历整个数组
for (let i = 1; i < len; i++) {
// 每遍历一个新元素，都要“回头看”，看看能不能延长原有的上升子序列
for (let j = 0; j < i; j++) {
// 若遇到了一个比当前元素小的值，则意味着遇到了一个可以延长的上升子序列，故更新当前元素索引位对应的状态
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 及时更新上升子序列长度的最大值
if (dp[i] > maxLen) {
maxLen = dp[i];
}
}
// 遍历完毕，最后到手的就是最大上升子序列的长度
return maxLen;
};
# 谷歌真题
# 最长回文子串问题
编辑 (opens new window)
上次更新: 2025/03/11, 11:29:39