由于面试需要，决定从零开始刷 LeetCode Hot 100，记录一下刷题过程。
问题都很长，所以只记录题目和解题思路，当前进度（32/100 + 6），因为写了很多题没记录所以等下一遍刷 hot 100 再更新了 = =（很快，一个月内）
准备
先简单了解下数据结构，很不错的视频
然后上 LeetCode 注册账号，开始刷题。
哈希
1. 两数之和
最直接的是使用两层 for 循环，遍历判断两数之和是否等于 target，时间复杂度 O(n^2)
更好的思路是使用哈希表（Map），A + B = C，这里是去找 C - A 的值，如果这个值在哈希表中存在，就说明找到了 A 和 B，时间复杂度为 O(n)
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
const map = new Map()
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i]
if (map.has(need)) return [map.get(need), i]
map.set(nums[i], i)
}
return []
}49. 字母异位词分组
字母异位词就是两个单词的组成字母完全相同，如 abc 和 cba 是异位词
思路：对每个字符串字母排序，判断排序后字符串是否相等，然后对原字符进行分组
思路有了就找结构，要存原字符串，然后原字符串要对应排序后的字符串，所以哈希表（Map）最好不过了
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function (strs) {
const map = new Map()
for (const s of strs) {
const key = s.split('').sort().join('')
if (!map.has(key)) {
map.set(key, [])
}
map.get(key).push(s)
}
return [...map.values()]
}128. 最长连续序列
思路：先对数组去重排序，存两个值：一个当前连续长度，一个最长连续长度，然后遍历一遍新数组，连续的就加当前长度，不连续就重置当前长度，最后返回最长长度
这里去重用的是 Set 结构，去除重复元素，排序用数组的 sort 方法。
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
if (nums.length === 0) return 0
const snums = [...new Set(nums)].sort((a, b) => a - b)
let current = 1
let result = 1
for (let i = 0; i < snums.length - 1; i++) {
const a = snums[i]
const b = snums[i + 1]
if (b - a === 1) {
current++
result = Math.max(current, result)
} else {
current = 1
}
}
return result
}最开始漏掉了判断数组长度为 0 的情况，每道题都应该去考虑边界情况。
这个能够 AC（Accepted），但是时间复杂度是 O(n logn)，题目要求 O(n) 的时间复杂度，所以这个解法不符合要求。
看了题解，是在判断是否连续时，判断当前元素的上一个元素是否存在，如果不存在则说明当前元素是连续序列的起点，然后从当前元素去向后找连续的元素。
更改后：
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
if (nums.length === 0) return 0
const set = new Set(nums)
let longest = 0
for (const num of set) {
// 连续起始
if (!set.has(num - 1)) {
let current = num
let length = 1
while (set.has(current + 1)) {
current++
length++
}
longest = Math.max(length, longest)
}
}
return longest
}双指针
283. 移动零
思路：将所有零后移，可以使用双指针，一个指针遍历数组，另一个指针记录非零元素位置，当遍历到非零元素时，将其放到非零元素位置指针上，然后指针后移，直到遍历完数组，最后将非零元素位置指针之后的元素全部设为 0。
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function (nums) {
let slow = 0
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast] !== 0) {
nums[slow] = nums[fast]
slow++
}
}
while (slow < nums.length) {
nums[slow] = 0
slow++
}
}11. 盛最多水的容器
暴力思路：容积最大，就是 x * y 最大，那就挨个遍历所有可能的组合，取最大值，时间复杂度 O(n^2)
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
let max = 0
for (let i = 0; i < height.length; i++) {
for (let j = i + 1; j < height.length; j++) {
const x = j - i
const y = Math.min(height[i], height[j])
max = Math.max(max, x * y)
}
}
return max
}这个解法最无脑，但是超时了
思路：原理依旧是 x * y 最大，使用双指针分别指向最左侧和最右侧，这样的话就是 x 最大，接下来指针向内移动，每次移动 x 都会减小，所以要让 y 尽可能大，将两个指针所在的高度比较，将较小的指针向内移动，直到两个指针相遇，时间复杂度 O(n)
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
let left = 0
let right = height.length - 1
let ans = 0
while (left < right) {
const h = Math.min(height[left], height[right])
const w = right - left
ans = Math.max(ans, h * w)
if (height[left] < height[right]) {
left++
} else {
right--
}
}
return ans
}这里用到了贪心算法，贪心算法就是局部最优 -> 全局最优。
15. 三数之和
虽然这个依然能暴力，但是 3 个 for 循环，时间复杂度飙到 O(n^3)了，所以还是要用双指针。
思路：固定一个数，然后使用双指针找另外两个数，跟 11. 盛最多水的容器 类似，两个指针向内移动。
容易漏的点是去重，外层 for 索引和两个指针都要去重。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
const ans = []
let snums = nums.sort((a, b) => a - b)
for (let i = 0; i < snums.length; i++) {
if (i > 0 && snums[i] === snums[i - 1]) continue
const a = snums[i]
let left = i + 1
let right = snums.length - 1
while (left < right) {
const b = snums[left]
const c = snums[right]
const sum = a + b + c
if (sum === 0) {
ans.push([a, b, c])
while (left < right && snums[left] === snums[left + 1]) left++
while (left < right && snums[right] === snums[right - 1]) right--
left++
right--
} else if (sum < 0) {
left++
} else {
right--
}
}
}
return ans
}42. 接雨水
思路：每个位置的雨水是被两侧围住的，能分析出来每个位置的雨水量 = min(左边最高高度, 右边最高高度) - 当前高度。
暴力解法是每个位置向两侧遍历找最高高度，时间复杂度 O(n^2)；稍微好一点的话，遍历一遍数组，用两个数组分别存储每个位置的左边最高高度和右边最高高度，然后再遍历一遍数组计算雨水量，时间复杂度 O(n)。
更好的办法是使用双指针，两个指针分别指向数组的两端，在线更新左右两侧的最高高度，移动较低的指针，直到两个指针相遇。因为从最左侧和从最右侧出发，对于一侧经过的位置是逐渐增加的，所以可以在线更新最高高度。
/**
* @param {number[]} height
* @return {number}
*/
var trap = function (height) {
let l = 0
let r = height.length - 1
let leftMax = 0
let rightMax = 0
let ans = 0
while (l < r) {
if (height[l] <= height[r]) {
if (height[l] >= leftMax) {
leftMax = height[l]
} else {
ans += leftMax - height[l]
}
l++
} else {
if (height[r] >= rightMax) {
rightMax = height[r]
} else {
ans += rightMax - height[r]
}
r--
}
}
return ans
}滑动窗口
3. 无重复字符的最长子串
思路：滑动窗口，[left, right]，找连续无重复最长子串，让 left 先固定，right 向右移动，right 移动过程用 Map 记录字符索引，这样当 right 移动到重复字符时，将 left 移动到重复字符的下一个位置，名副其实的 “滑动窗口”。
有个容易漏的点，移动 left 应该比较重复字符的索引和 left 当前大小，取最大值，这样才能保证 left 不会回退过去。
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
if (s.length <= 1) return s.length
let ans = 0
const map = new Map()
let left = 0
for (let right = 0; right < s.length; right++) {
if (map.has(s[right])) {
left = Math.max(left, map.get(s[right]) + 1)
}
map.set(s[right], right)
ans = Math.max(ans, right - left + 1)
}
return ans
}438. 找到字符串中所有字母异位词
首先是最无脑打法：
/**
* @param {string} s
* @param {string} p
* @return {number[]}
*/
var findAnagrams = function (s, p) {
const n = p.length
const target = p.split('').sort().join()
let left = 0
const ans = []
for (let right = n - 1; right < s.length; right++) {
if (
s
.slice(left, right + 1)
.split('')
.sort()
.join() == target
) {
ans.push(left)
}
left++
}
return ans
}提交运行，超出时间限制，只好另寻方法
看了题解，使用滑动窗口的同时统计字符频次，一个 need Map + 一个 window Map + 一个 valid 计数器，滑动窗口的同时更新 window Map，然后对 valid++ 或 valid—，当 valid === need Map 大小 (need.size) 时，说明找到了一个异位词。
/**
* @param {string} s
* @param {string} p
* @return {number[]}
*/
var findAnagrams = function (s, p) {
const ans = []
const need = new Map()
const window = new Map()
for (const ch of p) {
need.set(ch, (need.get(ch) || 0) + 1)
}
let left = 0
let right = 0
let valid = 0
while (right < s.length) {
const ch = s[right]
if (need.has(ch)) {
window.set(ch, (window.get(ch) || 0) + 1)
if (need.get(ch) === window.get(ch)) {
valid++
}
}
right++
if (right - left === p.length) {
if (valid === need.size && right - left === p.length) {
ans.push(left)
}
const l = s[left]
if (need.has(l)) {
if (need.get(l) === window.get(l)) {
valid--
}
window.set(l, window.get(l) - 1)
}
left++
}
}
return ans
}子串
560. 和为 K 的子数组
思路：前缀和 + 哈希表，遍历数组，计算前缀和 sum，同时把前缀和记录到哈希表，值是出现的次数，然后判断 sum - k 是否在哈希表中（看到了两数之和的影子），如果存在就 ans++。
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function (nums, k) {
let ans = 0
let sum = 0
const map = new Map()
map.set(0, 1)
for (const num of nums) {
sum += num
const target = sum - k
if (map.has(target)) {
ans += map.get(target)
}
map.set(sum, (map.get(sum) || 0) + 1)
}
return ans
}239. 滑动窗口最大值
~~休息一会～~ 休息完了，先来个暴力解法（bushi）
思路：又是新东西，这次用单调递减队列 q(ueue) 去获取最大值，最开始是用队列存的值，结果发现如果有重复值，删除的时候就会出问题，改成存索引简直完美。新增元素时，从队尾不断向前比较，然后填入元素，同时根据当前最大值的索引判断是否过期，在窗口成型后，每次推送 q[0] 的值到结果数组中。
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function (nums, k) {
const n = nums.length
if (n === 0 || k === 0) return []
const res = []
const q = []
for (let i = 0; i < n; i++) {
while (q.length && nums[i] >= nums[q[q.length - 1]]) {
q.pop()
}
q.push(i)
if (q[0] <= i - k) {
q.shift()
}
if (i >= k - 1) {
res.push(nums[q[0]])
}
}
return res
}76. 最小覆盖子串
思路：这一个跟找字母异位词类似…依旧使用滑动窗口 + 哈希表，统计字符频次，一个 need Map + 一个 window Map + 一个 valid 计数器，滑动窗口的同时更新 window Map，然后对 valid++ 或 valid—，当 valid === need Map 大小 (need.size) 时，说明找到了一个覆盖子串，然后左侧不断收缩，记录最小长度，直到 valid !== need.size 跳出循环，继续右侧扩张。
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function (s, t) {
if (s.length === 0 || t.length > s.length) return ''
const need = new Map()
const window = new Map()
let valid = 0
let start = 0
let minLen = Infinity
for (const s of t) {
need.set(s, (need.get(s) || 0) + 1)
}
let left = 0
let right = 0
while (right < s.length) {
const b = s[right]
if (need.has(b)) {
window.set(b, (window.get(b) || 0) + 1)
if (need.get(b) === window.get(b)) {
valid++
}
}
right++
while (valid === need.size) {
if (right - left < minLen) {
minLen = right - left
start = left
}
const a = s[left]
if (need.has(a)) {
if (window.get(a) === need.get(a)) {
valid--
}
window.set(a, window.get(a) - 1)
}
left++
}
}
if (minLen === Infinity) return ''
return s.substring(start, start + minLen)
}普通数组
53. 最大子数组和
思路：找到连续子数组最大的和，想到前缀和，这个和一定是一个前缀和减去前面最小的前缀和。那就很简单了，for 遍历一遍数组，计算前缀和 pre，同时记录最小前缀和 min，取 pre - min 的最大值。
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
let max = -Infinity
let min = 0
let pre = 0
for (let i = 0; i < nums.length; i++) {
pre += nums[i]
max = Math.max(max, pre - min)
min = Math.min(min, pre)
}
return max
}还有一种思路是动态规划，dp[i] 表示以 nums[i] 结尾的最大子数组和，那么 dp[i] = max(dp[i - 1] + nums[i], nums[i])，也就是让当前元素加上前一个最大子数组和，与当前元素本身比较，取最大值。有点像走楼梯问题，走楼梯只能走一阶或者两阶，那么走最后一阶的时候一定是从倒数第二阶或倒数第一阶走上来的。
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
let cur = nums[0]
let res = nums[0]
for (let i = 1; i < nums.length; i++) {
cur = Math.max(cur + nums[i], nums[i])
res = Math.max(res, cur)
}
return res
}56. 合并区间
思路：先对区间左端点排序，然后遍历区间数组，这里用 ans 存储合并后的区间。
这里有个点是 last 是对 ans 的最后一个数组元素的引用，直接修改 last[1] 就是修改了 ans 中的最后一个区间。原本一股脑写了 ans.pop()，然后再 push()
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function (intervals) {
if (intervals.length === 0) return []
const ans = []
intervals.sort((a, b) => a[0] - b[0])
ans.push(intervals[0])
for (let i = 1; i < intervals.length; i++) {
const cur = intervals[i]
const last = ans[ans.length - 1]
if (cur[0] <= last[1]) {
last[1] = Math.max(last[1], cur[1])
} else {
ans.push(cur)
}
}
return ans
}189. 轮转数组
思路：用一个额外数组存储轮转后的数组，很简单直接
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function (nums, k) {
const n = nums.length
k = k % n
const res = new Array(n)
for (let i = 0; i < n; i++) {
res[(i + k) % n] = nums[i]
}
for (let i = 0; i < n; i++) {
nums[i] = res[i]
}
}看题解还有原地反转算法，空间复杂度为 O(1)，先将整个数组反转，然后将前 k 个元素反转，再将后 n - k 个元素反转。反转函数用的是双指针。
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function (nums, k) {
const n = nums.length
k = k % n
if (k === 0) return
const reverse = (arr, l, r) => {
while (l < r) {
const tmp = arr[l]
arr[l] = arr[r]
arr[r] = tmp
l++
r--
}
}
reverse(nums, 0, n - 1)
reverse(nums, 0, k - 1)
reverse(nums, k, n - 1)
}238. 除了自身以外数组的乘积
思路：不让用除法，拆解问题，除了自身以外数组的乘积，也就是左侧数乘积 * 右侧数乘积，先遍历一遍数组，声明 pre 前缀乘积变量，把左侧数乘积放到 ans 结果数组中，ans[0] 就是 nums[0] 左侧数的乘积，没有问题。然后是 suf 后缀乘积，将 suf 乘进 ans 数组里。
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function (nums) {
const ans = new Array(nums.length)
let pre = 1
for (let i = 0; i < nums.length; i++) {
ans[i] = pre
pre *= nums[i]
}
let suf = 1
for (let i = nums.length - 1; i >= 0; i--) {
ans[i] *= suf
suf *= nums[i]
}
return ans
}41. 缺失的第一个正数
接下来转变下策略，先刷高频题，不按顺序刷了 = =
矩阵
73. 矩阵置零
54. 螺旋矩阵
48. 旋转图像
240. 搜索二维矩阵 II
链表
160. 相交链表
206. 反转链表
思路：一个 prev 一个 curr，用 temp 存中间值
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
let prev = null
let curr = head
while (curr) {
const temp = curr.next
curr.next = prev
prev = curr
curr = temp
}
return prev
}234. 回文链表
141. 环形链表
哈希表思路：用 Set 存储访问过的节点，如果访问过就说明有环，直到访问到 null 说明没有环。
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
const visited = new Set()
let cur = head
while (cur !== null) {
if (visited.has(cur)) {
return true
}
visited.add(cur)
cur = cur.next
}
return false
}快慢指针思路：快指针每次走两步，慢指针每次走一步，如果有环，快指针一定会追上慢指针，如果没有环，快指针会先到 null。
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
if (head === null || head.next === null) {
return false
}
let slow = head
let fast = head
while (fast !== null && fast.next !== null) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
return true
}
}
return false
}142. 环形链表 II
21. 合并两个有序链表
思路：新建一个链表 + 两个指针，两个指针分别指向两个列表的头部，比较值然后在新链表中插入较小的值，指针后移，直到一个链表遍历完，然后将另一个链表剩余的部分接到新链表后面。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function (list1, list2) {
const dummy = new ListNode(-1)
let curr = dummy
let p1 = list1
let p2 = list2
while (p1 && p2) {
if (p1.val < p2.val) {
curr.next = p1
p1 = p1.next
} else {
curr.next = p2
p2 = p2.next
}
curr = curr.next
}
curr.next = p1 ? p1 : p2
return dummy.next
}2. 两数相加
19. 删除链表的倒数第 N 个结点
24. 两两交换链表中的节点
25. K 个一组翻转链表
思路：分段 + 反转链表 + 拼接
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function (head, k) {
if (!head || k === 1) return head
const dummy = new ListNode(0, head)
let pre = dummy
while (true) {
// 1. 从 pre 开始向后走 k 步，看看够不够一组
let end = pre
for (let i = 0; i < k && end !== null; i++) {
end = end.next
}
if (end === null) break
// 2. 记录这一组的开始和下一组的开始
let start = pre.next
let nextGroupStart = end.next
// 3. 断开这一段，单独反转 [start, end]
end.next = null
// 反转整段，返回新头
let newHead = reverseList(start)
// 4. 接回到原链表
pre.next = newHead
start.next = nextGroupStart
// 5. pre 移动到当前组的尾部
pre = start
}
return dummy.next
}
// 反转整条链表：返回新头
function reverseList(head) {
let prev = null
let curr = head
while (curr !== null) {
const temp = curr.next
curr.next = prev
prev = curr
curr = temp
}
return prev
}138. 随机链表的复制
148. 排序链表
23. 合并 K 个升序链表
146. LRU 缓存
思路：LRU 要存的值是 key-value，然后要求删除最早未使用的元素，所以这道题用 Map 再合适不过。这里获取最早使用元素用的是 map.keys() 方法，返回一个迭代器对象，用 next() 方法获取第一个元素。
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.map = new Map()
this.cap = capacity
}
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
const map = this.map
if (!map.has(key)) return -1
const value = map.get(key)
map.delete(key)
map.set(key, value)
return value
}
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
const map = this.map
if (map.has(key)) {
map.delete(key)
}
map.set(key, value)
if (map.size > this.cap) {
const first = map.keys().next().value
map.delete(first)
}
}还有经典解法，哈希表 + 双向链表，两个头尾哨兵节点，但是没有 Map 简单好用，这里不写了。
二叉树
94. 二叉树的中序遍历
递归思路：中序遍历的顺序是左子树 -> 根节点 -> 右子树，所以先递归访问左子树，然后访问根节点，最后递归访问右子树。
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
const res = []
function dfs(node) {
if (!node) return
dfs(node.left)
res.push(node.val)
dfs(node.right)
}
dfs(root)
return res
}迭代思路：使用栈，先将左子树入栈，然后访问根节点，最后访问右子树。
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
const res = []
const stack = []
let cur = root
while (cur || stack.length) {
if (cur) {
stack.push(cur)
cur = cur.left
} else {
cur = stack.pop()
res.push(cur.val)
cur = cur.right
}
}
return res
}104. 二叉树的最大深度
226. 翻转二叉树
101. 对称二叉树
543. 二叉树的直径
102. 二叉树的层序遍历
108. 将有序数组转换为二叉搜索树
98. 验证二叉搜索树
230. 二叉搜索树中第 K 小的元素
思路：二叉搜索树中左子树 < 根节点 < 右子树，这里递归访问左子树 -> 根节点 -> 右子树，访问的顺序就是从小到大，使用 visited 计数器记录访问了多少个节点，当 visited === k 时，说明找到了第 k 小的元素。
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function (root, k) {
let ans = null
let visited = 0
function dfs(node) {
if (!node || visited >= k) return
dfs(node.left)
visited++
if (visited === k) {
ans = node.val
return
}
dfs(node.right)
}
dfs(root)
return ans
}199. 二叉树的右视图
114. 二叉树展开为链表
105. 从前序与中序遍历序列构造二叉树
思路：理解前序和中序遍历的特点，前序遍历的第一个元素是根节点，然后在中序遍历中找到根节点的位置，左边的就是左子树，右边的就是右子树，然后递归构建左右子树。利用哈希表存储中序遍历的值和索引，方便快速查找根节点在中序遍历中的位置。
/**
* 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 {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function (preorder, inorder) {
if (preorder.length === 0) return null
const indexMap = new Map()
for (let i = 0; i < inorder.length; i++) {
indexMap.set(inorder[i], i)
}
function build(preL, preR, inL, inR) {
if (preL > preR) return null
const rootVal = preorder[preL]
const root = new TreeNode(rootVal)
const idx = indexMap.get(rootVal)
const leftSize = idx - inL
root.left = build(preL + 1, preL + leftSize, inL, idx - 1)
root.right = build(preL + leftSize + 1, preR, idx + 1, inR)
return root
}
return build(0, preorder.length - 1, 0, inorder.length - 1)
}437. 路径总和 III
236. 二叉树的最近公共祖先
124. 二叉树中的最大路径和
图论
200. 岛屿数量
思路：深度优先搜索 DFS + “淹没”岛屿，遍历访问，遇到 1 则将周围的 1 都淹没成 0，岛屿数量 +1。
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function (grid) {
if (!grid || grid.length === 0) return 0
const m = grid.length
const n = grid[0].length
let count = 0
const dfs = (i, j) => {
if (i < 0 || i >= m || j < 0 || j >= n) return
if (grid[i][j] === '0') return
grid[i][j] = '0'
dfs(i - 1, j)
dfs(i + 1, j)
dfs(i, j - 1)
dfs(i, j + 1)
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1') {
count++
dfs(i, j)
}
}
}
return count
}994. 腐烂的橘子
207. 课程表
208. 实现 Trie (前缀树)
回溯
回溯算法是一种通过尝试所有可能的解决方案来解决问题的算法。它通常用于组合、排列、子集等问题。回溯算法的核心思想是通过递归来构建解空间树，并在每个节点上做出选择，然后继续递归探索，直到达到终止条件。如果当前路径不满足条件，就回溯到上一个节点，尝试其他选择。
46. 全排列
思路：用回溯生成全排列。用 path 记录当前排列，用 used 标记每个元素是否已在本轮使用。每次递归，当 path 长度等于 nums 长度时，将 path 的拷贝加入结果集；否则遍历 nums，对于未使用的元素，将其加入 path 并标记 used 后继续递归，回溯时再撤销选择（从 path 移除并重置 used）。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
const res = []
const path = []
const used = new Array(nums.length).fill(false)
function backtrack() {
if (path.length === nums.length) {
// 推送拷贝
res.push(path.slice())
return
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) {
continue
}
used[i] = true
path.push(nums[i])
backtrack()
// 撤销选择：恢复状态，回到上一层
path.pop()
used[i] = false
}
}
backtrack()
return res
}78. 子集
17. 电话号码的字母组合
39. 组合总和
22. 括号生成
79. 单词搜索
131. 分割回文串
51. N 皇后
二分查找
35. 搜索插入位置
74. 搜索二维矩阵
34. 在排序数组中查找元素的第一个和最后一个位置
33. 搜索旋转排序数组
153. 寻找旋转排序数组中的最小值
4. 寻找两个正序数组的中位数
栈
20. 有效的括号
思路：栈的基本应用，先进后出，比较括号是否匹配就是与栈顶比较
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
if (s.length % 2 === 1) return false
const stack = []
const map = {
')': '(',
']': '[',
'}': '{',
}
for (const ch of s) {
if (ch in map) {
const top = stack.length ? stack.pop() : '#'
if (top !== map[ch]) {
return false
}
} else {
stack.push(ch)
}
}
return stack.length === 0
}155. 最小栈
394. 字符串解码
思路：栈的应用，遇到数字和字符就存储下来，遇到 [ 就把当前数字和字符串入栈，遇到 ] 就出栈，拼接字符串。
/**
* @param {string} s
* @return {string}
*/
var decodeString = function (s) {
const nums = []
const strs = []
let num = ''
let str = ''
for (const ch of s) {
if (ch >= '0' && ch <= '9') {
num += ch
} else if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {
str += ch
} else if (ch === '[') {
nums.push(Number(num))
strs.push(str)
num = ''
str = ''
} else if (ch === ']') {
str = strs.pop() + str.repeat(nums.pop())
}
}
return str
}739. 每日温度
84. 柱状图中最大的矩形
堆
215. 数组中的第 K 个最大元素
思路：nums.sort，然后返回 nums[k - 1] O(n) 复杂度要用到堆排序，建立大根堆，堆顶就是最大值，第 K 个最大值就弹出堆顶 K - 1 次，之后堆顶就是第 K 个最大值。重点在于 heapify() 函数，倒着排序建堆，理解原理就能看明白函数了。
堆排序，看的这个视频：堆与堆排序 | bilibili
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function (nums, k) {
const n = nums.length
function heapify(i, heapSize) {
while (true) {
let largest = i
let left = 2 * i + 1
let right = 2 * i + 2
if (left < heapSize && nums[left] > nums[largest]) {
largest = left
}
if (right < heapSize && nums[right] > nums[largest]) {
largest = right
}
if (i === largest) break
;[nums[i], nums[largest]] = [nums[largest], nums[i]]
i = largest
}
}
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(i, n)
}
let heapSize = n
for (let i = 0; i < k - 1; i++) {
;[nums[0], nums[heapSize - 1]] = [nums[heapSize - 1], nums[0]]
heapSize--
heapify(0, heapSize)
}
return nums[0]
}347. 前 K 个高频元素
295. 数据流的中位数
贪心算法
121. 买卖股票的最佳时机
思路：记录购入最小价格，遍历更新最小价格以及计算利润。
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
let minPrice = prices[0]
let maxProfit = 0
for (let i = 1; i < prices.length; i++) {
const profit = prices[i] - minPrice
maxProfit = Math.max(profit, maxProfit)
minPrice = Math.min(prices[i], minPrice)
}
return maxProfit
}55. 跳跃游戏
45. 跳跃游戏 II
763. 划分字母区间
动态规划
70. 爬楼梯
118. 杨辉三角
198. 打家劫舍
279. 完全平方数
322. 零钱兑换
139. 单词拆分
300. 最长递增子序列
思路：二分查找 + 贪心算法。lowerBound() 函数是二分查找，返回第一个大于等于 target 的索引，tail 数组存储当前最长递增子序列的末尾元素，遍历 nums 数组，使用 lowerBound() 找到 x 在 tail 中的位置 i，如果 i === tail.length，说明 x 比 tail 中所有元素都大，将 x 添加到 tail 末尾，否则将 tail[i] 替换为 x，这样可以保证 tail 中的元素尽可能小，从而为后续的元素提供更多的选择。最后返回 tail.length 即为最长递增子序列的长度。
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
const lowerBound = (nums, target) => {
let left = 0
let right = nums.length
while (left < right) {
const mid = left + Math.floor((right - left) / 2)
if (nums[mid] < target) {
left = mid + 1
} else {
right = mid
}
}
return left
}
const tail = []
for (const x of nums) {
const i = lowerBound(tail, x)
if (i === tail.length) {
tail.push(x)
} else {
tail[i] = x
}
}
return tail.length
}152. 乘积最大子数组
416. 分割等和子集
32. 最长有效括号
思路：栈存储左括号的索引，遇到右括号就弹出栈顶索引，如果栈为空，说明当前右括号没有匹配的左括号，将当前索引入栈作为新的起点（分界线），否则计算当前有效括号长度为 i - stack[stack.length - 1]，更新最大长度 maxLen。
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function (s) {
const stack = [-1]
let maxLen = 0
for (let i = 0; i < s.length; i++) {
const ch = s[i]
if (ch === '(') {
stack.push(i)
} else {
stack.pop()
if (stack.length === 0) {
stack.push(i)
} else {
const currLen = i - stack[stack.length - 1]
maxLen = Math.max(currLen, maxLen)
}
}
}
return maxLen
}多维动态规划
62. 不同路径
64. 最小路径和
思路：动态规划，dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]，先计算第一行和第一列的最小路径和，然后从 (1, 1) 开始计算每个位置的最小路径和，最后返回右下角的值。
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function (grid) {
const m = grid.length
const n = grid[0].length
for (let i = 1; i < m; i++) {
grid[i][0] += grid[i - 1][0]
}
for (let j = 1; j < n; j++) {
grid[0][j] += grid[0][j - 1]
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1])
}
}
return grid[m - 1][n - 1]
}5. 最长回文子串
1143. 最长公共子序列
72. 编辑距离
技巧
136. 只出现一次的数字
169. 多数元素
75. 颜色分类
31. 下一个排列
287. 寻找重复数
其他（非 Hot 100）
8. 字符串转换整数 (atoi)
思路：题目说的很明白了，trim() 去零，用 sign 记录正负号，res 存储结果，遍历字符串，遇到非数字就 break，遇到数字就计算 res = res * 10 + digit，同时判断是否溢出。这里判断溢出原理是每次 res = res * 10 + digit，就是 res * 10 + digit > INT_MAX，变形一下就是 res > (INT_MAX - digit) / 10，floor() 是因为 res 是整数，INT_MAX - digit 可能不是 10 的倍数。
/**
* @param {string} s
* @return {number}
*/
var myAtoi = function (s) {
s = s.trim()
if (s === '') return 0
const INT_MAX = 2 ** 31 - 1
const INT_MIN = -(2 ** 31)
const n = s.length
let i = 0
let sign = 1
if (s[i] === '-') {
sign = -1
i++
} else if (s[i] === '+') {
i++
}
let res = 0
while (i < n) {
const ch = s[i]
if (ch < '0' || ch > '9') break
const digit = ch.charCodeAt(0) - '0'.charCodeAt(0)
if (res > Math.floor((INT_MAX - digit) / 10)) {
return sign === 1 ? INT_MAX : INT_MIN
}
res = res * 10 + digit
i++
}
return sign * res
}43. 字符串相乘
思路：模拟竖式乘法，创建 n1 + n2 长度（最大位）的数组 res，其中 res[i + j + 1] 为计算中当前位，res[i + j] 为进位，最后将 res 前置 0 去除。
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var multiply = function (num1, num2) {
if (num1 === '0' || num2 === '0') return '0'
const n1 = num1.length
const n2 = num2.length
const res = new Array(n1 + n2).fill(0)
for (let i = n1 - 1; i >= 0; i--) {
const x = num1.charCodeAt(i) - '0'.charCodeAt(0)
for (let j = n2 - 1; j >= 0; j--) {
const y = num2.charCodeAt(j) - '0'.charCodeAt(0)
const sum = res[i + j + 1] + x * y
res[i + j + 1] = sum % 10
res[i + j] += Math.floor(sum / 10)
}
}
let k = 0
while (k < res.length - 1 && res[k] === 0) k++
return res.slice(k).join('')
}93. 复原 IP 地址
思路：回溯递归，利用 path.pop() 进行回溯，同时递归终止条件是 path 长度为 4 且 start === n，说明已经找到了一个合法的 IP 地址。同时判断剩余字符数是否满足剩余段数的要求，如果不满足就直接返回，剪枝优化。
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function (s) {
const res = []
const n = s.length
if (n < 4 || n > 12) return res
function backtrack(start, path) {
if (path.length === 4) {
if (start === n) {
res.push(path.join('.'))
}
return
}
const remainChars = n - start
const remainSegs = 4 - path.length
if (remainChars < remainSegs || remainChars > 3 * remainSegs) {
return
}
for (let len = 1; len <= 3; len++) {
if (start + len > n) break
const part = s.substring(start, start + len)
if (part[0] === '0' && part.length > 1) break
const num = Number(part)
if (num < 0 || num > 255) break
path.push(part)
backtrack(start + len, path)
path.pop()
}
}
backtrack(0, [])
return res
}165. 比较版本号
思路：先将版本号按 ’.’ 分割成数组，然后同时遍历两个数组，获取当前版本号的整数值，如果遍历到长度外就用 0 补，根据大小返回结果。
/**
* @param {string} version1
* @param {string} version2
* @return {number}
*/
var compareVersion = function (version1, version2) {
const a = version1.split('.')
const b = version2.split('.')
const n = Math.max(a.length, b.length)
for (let i = 0; i < n; i++) {
const v1 = i < a.length ? parseInt(a[i], 10) : 0
const v2 = i < b.length ? parseInt(b[i], 10) : 0
if (v1 > v2) return 1
if (v1 < v2) return -1
}
return 0
}442. 数组中重复的数据
思路：根据题目限制，数组中的整数都在 1 到 n 之间，这里用原数组标记是否访问，很巧妙地不改变数组的（绝对）值，同时能够标记访问过的元素，遍历数组，根据值获取索引 x - 1，如果 nums[x - 1] < 0，说明 x 已经访问过了，将 x 添加到结果数组中，否则将 nums[x - 1] 取负数标记访问过。
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDuplicates = function (nums) {
const res = []
for (let i = 0; i < nums.length; i++) {
const x = Math.abs(nums[i])
if (nums[x - 1] < 0) {
res.push(x)
} else {
nums[x - 1] = -nums[x - 1]
}
}
return res
}LCR 180.文件组合
思路：滑动窗口
/**
* @param {number} target
* @return {number[][]}
*/
var fileCombination = function (target) {
const res = []
let l = 1,
r = 1,
sum = 0
while (r < target) {
sum += r
while (sum > target) {
sum -= l
l++
}
if (sum === target && r > l) {
const temp = []
for (let x = l; x <= r; x++) {
temp.push(x)
}
res.push(temp)
}
r++
}
return res
}122. 买卖股票的最佳时机 II
思路：利润累计，遍历价格数组，如果当前价格大于前一天的价格，就卖出，累加利润。
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
let profit = 0
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1]
}
}
return profit
}
加载中...