由于面试需要，决定从零开始刷 LeetCode Hot 100，记录一下刷题过程。

问题都很长，所以只记录题目和解题思路，当前进度（32/100 + 6）上次更新 7.28

准备

先简单了解下数据结构，很不错的视频

你是天才，所以不用学数据结构 | bilibili

然后上 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
}