imber

Appearance

LeetCode 热题 100

哈希-001 两数之和 ​

js
var twoSum = function (nums, target) {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    const item = nums[i]
    const diff = target - item // 转为差值
    if (map.has(diff)) {
      return [map.get(diff), i]
    }
    map.set(item, i)
  }
}

console.log(twoSum([2, 7, 11, 15], 9))
var twoSum = function (nums, target) {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    const item = nums[i]
    const diff = target - item // 转为差值
    if (map.has(diff)) {
      return [map.get(diff), i]
    }
    map.set(item, i)
  }
}

console.log(twoSum([2, 7, 11, 15], 9))

哈希-049 字母异位分组 ​

排序，map 存数组，然后 map.values() 取答案

js
var groupAnagrams = function (strs) {
  // map
  const map = new Map()

  // 遍历数组
  for (let str of strs) {
    // 转为数组
    let array = Array.from(str)
    // 排序
    array.sort()
    // 转为字符串
    let key = array.toString()
    // value list
    let list = map.get(key) ? map.get(key) : []
    // 放进。value list 里
    list.push(str)
    // 放进 map
    map.set(key, list)
  }

  // 返回 map 的值
  return Array.from(map.values())
}

groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat'])
var groupAnagrams = function (strs) {
  // map
  const map = new Map()

  // 遍历数组
  for (let str of strs) {
    // 转为数组
    let array = Array.from(str)
    // 排序
    array.sort()
    // 转为字符串
    let key = array.toString()
    // value list
    let list = map.get(key) ? map.get(key) : []
    // 放进。value list 里
    list.push(str)
    // 放进 map
    map.set(key, list)
  }

  // 返回 map 的值
  return Array.from(map.values())
}

groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat'])

哈希-128 最长连续序列 ​

放 nums 进 set，右边没有元素 !numSet.has(num - 1) 开始遍历 set

numSet.has(currentNum + 1) 就一直 set 里找有没有下一个，然后 currentNum++ countLength++

有可能多段 length，再比较取最大的

放进 set 里，然后没有左边的情况开始遍历，中间计数，可能出现多段长度，对比找最大长度

时间复杂度 On，空间复杂度 On

js
var longestConsecutive = function (nums) {
  if (nums.length === 0) return 0
  const numSet = new Set(nums)
  let maxLength = 0

  for (const num of numSet) {
    // 没有当前项 - 1 才是起点
    if (!numSet.has(num - 1)) {
      let currentNum = num
      let countLength = 1
      while (numSet.has(currentNum + 1)) {
        currentNum++
        countLength++
      }

      maxLength = Math.max(maxLength, countLength) // cur不再有右邻居，检查count是否最大
    }
  }

  return maxLength
}

console.log(longestConsecutive([0, 1, 2, 3, 5, 6, 7]))
var longestConsecutive = function (nums) {
  if (nums.length === 0) return 0
  const numSet = new Set(nums)
  let maxLength = 0

  for (const num of numSet) {
    // 没有当前项 - 1 才是起点
    if (!numSet.has(num - 1)) {
      let currentNum = num
      let countLength = 1
      while (numSet.has(currentNum + 1)) {
        currentNum++
        countLength++
      }

      maxLength = Math.max(maxLength, countLength) // cur不再有右邻居，检查count是否最大
    }
  }

  return maxLength
}

console.log(longestConsecutive([0, 1, 2, 3, 5, 6, 7]))

双指针-283 移动零 ​

跟双指针没关系，用的栈，记录 size，不是 0 则依次赋值，最后补 0

js
var moveZeroes = function (nums) {
  // 栈长度
  let size = 0
  // 遍历数组
  for (let num of nums) {
    // 如果不是0
    if (num !== 0) {
      // 重新赋值
      nums[size] = num
      size = size + 1
    }
  }
  // 补 0
  return nums.fill(0, size)
}

console.log(moveZeroes([0, 1, 0, 3, 12]))
var moveZeroes = function (nums) {
  // 栈长度
  let size = 0
  // 遍历数组
  for (let num of nums) {
    // 如果不是0
    if (num !== 0) {
      // 重新赋值
      nums[size] = num
      size = size + 1
    }
  }
  // 补 0
  return nums.fill(0, size)
}

console.log(moveZeroes([0, 1, 0, 3, 12]))

双指针-011 盛最多水的容器 ​

左右两边双指针，每次比较左右两边的高度，取小的那个，然后计算面积，然后移动小的那个指针，直到两个指针相遇

js
var maxArea = function (height) {
  let left = 0
  let right = height.length - 1
  let containerLength = height.length - 1
  let max = 0
  while (left < right) {
    max = Math.max(max, containerLength * Math.min(height[left], height[right]))
    if (height[left] < height[right]) {
      left++
    } else {
      right--
    }
    containerLength--
  }
  return max
}

console.log(maxArea([8, 7, 2, 1]))
var maxArea = function (height) {
  let left = 0
  let right = height.length - 1
  let containerLength = height.length - 1
  let max = 0
  while (left < right) {
    max = Math.max(max, containerLength * Math.min(height[left], height[right]))
    if (height[left] < height[right]) {
      left++
    } else {
      right--
    }
    containerLength--
  }
  return max
}

console.log(maxArea([8, 7, 2, 1]))

双指针-015 三数之和 ​

排序，然后遍历，每次遍历一个数，然后左右指针找另外两个数，如果三个数之和为 0，则加入结果，如果大于 0，则右指针左移，如果小于 0，则左指针右移

js
var threeSum = function (nums) {
  nums.sort((a, b) => a - b) // 排序
  let target = [] // 排序后[-2,0,1,1,2]

  for (let i = 0; i < nums.length - 2; i++) {
    const item = nums[i]
    let left = i + 1
    let right = nums.length - 1

    if (i > 0 && nums[i] === nums[i - 1]) {
      continue
    }

    while (left < right) {
      let sum = item + nums[right] + nums[left]

      if (sum === 0) {
        target.push([item, nums[left], nums[right]])

        while (nums[left] === nums[left + 1]) {
          left++
        }

        while (nums[right] === nums[right - 1]) {
          right--
        }

        left++
        right--
      }

      if (sum > 0) {
        right--
      }

      if (sum < 0) {
        left++
      }
    }
  }

  return target
}

console.log(threeSum([-1, 0, 1, 2, -1, -4]))
var threeSum = function (nums) {
  nums.sort((a, b) => a - b) // 排序
  let target = [] // 排序后[-2,0,1,1,2]

  for (let i = 0; i < nums.length - 2; i++) {
    const item = nums[i]
    let left = i + 1
    let right = nums.length - 1

    if (i > 0 && nums[i] === nums[i - 1]) {
      continue
    }

    while (left < right) {
      let sum = item + nums[right] + nums[left]

      if (sum === 0) {
        target.push([item, nums[left], nums[right]])

        while (nums[left] === nums[left + 1]) {
          left++
        }

        while (nums[right] === nums[right - 1]) {
          right--
        }

        left++
        right--
      }

      if (sum > 0) {
        right--
      }

      if (sum < 0) {
        left++
      }
    }
  }

  return target
}

console.log(threeSum([-1, 0, 1, 2, -1, -4]))

双指针-042 接雨水 ​

左右两边双指针，每次比较左右两边的高度，取大的那个，然后计算面积，然后移动小的那个指针，直到两个指针相遇

js
var trap = function (height) {
  let ans = 0
  let left = 0,
    right = height.length - 1 // 双指针：左右两端
  let leftMax = 0,
    rightMax = 0 // 记录左右两边的最高值

  while (left < right) {
    // 更新左右两边见过的最高值
    leftMax = Math.max(leftMax, height[left])
    rightMax = Math.max(rightMax, height[right])

    if (height[left] < height[right]) {
      // 左边更低，处理左边的积水
      ans += leftMax - height[left] // 积水 = 左边最高 - 当前高度
      left++
    } else {
      // 右边更低，处理右边的积水
      ans += rightMax - height[right] // 积水 = 右边最高 - 当前高度
      right--
    }
  }
  return ans
}

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
var trap = function (height) {
  let ans = 0
  let left = 0,
    right = height.length - 1 // 双指针：左右两端
  let leftMax = 0,
    rightMax = 0 // 记录左右两边的最高值

  while (left < right) {
    // 更新左右两边见过的最高值
    leftMax = Math.max(leftMax, height[left])
    rightMax = Math.max(rightMax, height[right])

    if (height[left] < height[right]) {
      // 左边更低，处理左边的积水
      ans += leftMax - height[left] // 积水 = 左边最高 - 当前高度
      left++
    } else {
      // 右边更低，处理右边的积水
      ans += rightMax - height[right] // 积水 = 右边最高 - 当前高度
      right--
    }
  }
  return ans
}

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

滑动窗口-003 无重复字符的最长子串 ​

滑动窗口，维护一个窗口，窗口内没有重复字符，如果有重复字符，则缩小窗口，直到没有重复字符，关键是 ans 这个值一直保留最大值

js
var lengthOfLongestSubstring = function (s) {
  let ans = 0
  let left = 0
  const window = new Set() // 维护从下标 left 到下标 right 的字符
  for (let right = 0; right < s.length; right++) {
    const c = s[right]
    // 如果窗口内已经包含 c，那么再加入一个 c 会导致窗口内有重复元素
    // 所以要在加入 c 之前，先移出窗口内的 c
    while (window.has(c)) {
      // 窗口内有 c
      window.delete(s[left])
      left++ // 缩小窗口
    }
    window.add(c) // 加入 c
    ans = Math.max(ans, right - left + 1) // 更新窗口长度最大值
  }
  return ans
}

console.log(lengthOfLongestSubstring('abcabcbb'))
var lengthOfLongestSubstring = function (s) {
  let ans = 0
  let left = 0
  const window = new Set() // 维护从下标 left 到下标 right 的字符
  for (let right = 0; right < s.length; right++) {
    const c = s[right]
    // 如果窗口内已经包含 c，那么再加入一个 c 会导致窗口内有重复元素
    // 所以要在加入 c 之前，先移出窗口内的 c
    while (window.has(c)) {
      // 窗口内有 c
      window.delete(s[left])
      left++ // 缩小窗口
    }
    window.add(c) // 加入 c
    ans = Math.max(ans, right - left + 1) // 更新窗口长度最大值
  }
  return ans
}

console.log(lengthOfLongestSubstring('abcabcbb'))

滑动窗口-438 找到字符串中所有字母异位词 ​

这个解法超时了，但是容易看懂

双指针，先排序，然后遍历，每次遍历一个字符串，然后比较是否相等，相等则加入结果，不相等则继续遍历

js
const toOrder = (str) => Array.from(str).sort().join('')

var findAnagrams = function (s, p) {
  if (s.length < p.length) {
    return []
  }

  let left = 0
  const result = new Set()

  let key = toOrder(p)

  let pLen = p.length

  let sLen = s.length + 1

  for (let right = pLen; right < sLen; right++) {
    let str = s.slice(left, right)
    let sub = toOrder(str)
    if (sub === key) {
      result.add(left)
    }
    left++
  }

  return Array.from(result.values())
}
const toOrder = (str) => Array.from(str).sort().join('')

var findAnagrams = function (s, p) {
  if (s.length < p.length) {
    return []
  }

  let left = 0
  const result = new Set()

  let key = toOrder(p)

  let pLen = p.length

  let sLen = s.length + 1

  for (let right = pLen; right < sLen; right++) {
    let str = s.slice(left, right)
    let sub = toOrder(str)
    if (sub === key) {
      result.add(left)
    }
    left++
  }

  return Array.from(result.values())
}

子串-560 和为 K 的子数组 ​

暴力解法，两层循环，第一层循环是子数组的起始位置，第二层循环是子数组的结束位置(因为要求子数组是连续的)，然后计算子数组的和，如果和为 k，则计数加一

还有一种解法是用 Set，转差值，然后判断差值是否在 Set 中，在则计数加一，不在则加入 Set

js
var subarraySum = function (nums, k) {
  let count = 0
  for (let i = 0; i < nums.length; i++) {
    let sum = 0
    for (let j = i; j < nums.length; j++) {
      sum += nums[j]
      if (sum === k) count++
    }
  }
  return count
}
var subarraySum = function (nums, k) {
  let count = 0
  for (let i = 0; i < nums.length; i++) {
    let sum = 0
    for (let j = i; j < nums.length; j++) {
      sum += nums[j]
      if (sum === k) count++
    }
  }
  return count
}

子串-239 滑动窗口最大值 ​

这是一个超时的解法

双指针，左指针是窗口的起始位置，右指针是窗口的结束位置，每次计算窗口内的最大值，然后左指针右移，右指针右移

js
// 缓存数组的长度
const len = nums.length
// 定义结果数组
const res = []
// 初始化左指针
let left = 0
// 初始化右指针
let right = k - 1
// 当数组没有被遍历完时，执行循环体内的逻辑
while (right < len) {
  // 计算当前窗口内的最大值
  const max = Math.max(...nums.slice(left, right + 1))
  // 将最大值推入结果数组
  res.push(max)
  // 左指针前进一步
  left++
  // 右指针前进一步
  right++
}
// 返回结果数组
return res
// 缓存数组的长度
const len = nums.length
// 定义结果数组
const res = []
// 初始化左指针
let left = 0
// 初始化右指针
let right = k - 1
// 当数组没有被遍历完时，执行循环体内的逻辑
while (right < len) {
  // 计算当前窗口内的最大值
  const max = Math.max(...nums.slice(left, right + 1))
  // 将最大值推入结果数组
  res.push(max)
  // 左指针前进一步
  left++
  // 右指针前进一步
  right++
}
// 返回结果数组
return res

字串-076 最小覆盖子串 ​

困难题，略过了～

普通数组-053 最大子数组和 ​

动态规划暂时还不太理解，先略过

js
var maxSubArray = function (nums) {
  // 表示以当前元素结尾的最大子数组和
  let pre = 0
  // 记录到目前为止遇到的全局最大值
  let maxAns = nums[0]

  nums.forEach((item) => {
    // 如果 pre + item 大于 item，则说明 pre + item 是当前元素结尾的最大子数组和
    pre = Math.max(pre + item, item)
    // 更新全局最大值
    maxAns = Math.max(maxAns, pre)
  })
  return maxAns
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
var maxSubArray = function (nums) {
  // 表示以当前元素结尾的最大子数组和
  let pre = 0
  // 记录到目前为止遇到的全局最大值
  let maxAns = nums[0]

  nums.forEach((item) => {
    // 如果 pre + item 大于 item，则说明 pre + item 是当前元素结尾的最大子数组和
    pre = Math.max(pre + item, item)
    // 更新全局最大值
    maxAns = Math.max(maxAns, pre)
  })
  return maxAns
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

普通数组-056 合并区间 ​

排序，然后遍历，如果当前元素的左边界小于等于上一个元素的右边界，则合并，否则直接加入结果

js
var merge = function (intervals) {
  let res = []
  intervals.sort((a, b) => a[0] - b[0])

  let prev = intervals[0]

  for (let i = 1; i < intervals.length; i++) {
    let cur = intervals[i]
    if (prev[1] >= cur[0]) {
      // 有重合
      prev[1] = Math.max(cur[1], prev[1])
    } else {
      // 不重合，prev推入res数组
      res.push(prev)
      prev = cur // 更新 prev
    }
  }

  res.push(prev)
  return res
}

console.log(
  merge([
    [1, 3],
    [2, 6],
    [8, 10],
    [15, 18]
  ])
)
var merge = function (intervals) {
  let res = []
  intervals.sort((a, b) => a[0] - b[0])

  let prev = intervals[0]

  for (let i = 1; i < intervals.length; i++) {
    let cur = intervals[i]
    if (prev[1] >= cur[0]) {
      // 有重合
      prev[1] = Math.max(cur[1], prev[1])
    } else {
      // 不重合，prev推入res数组
      res.push(prev)
      prev = cur // 更新 prev
    }
  }

  res.push(prev)
  return res
}

console.log(
  merge([
    [1, 3],
    [2, 6],
    [8, 10],
    [15, 18]
  ])
)

普通数组-189 轮转数组 ​

暴力解，超时了，前面加一个后面删一个

js
var rotate = function (nums, k) {
  const len = nums.length

  let temp = nums[len - 1]
  let count = 0
  for (let i = 0; i < k; i++) {
    temp = nums[len - i - 1 + count]
    nums.unshift(temp)
    nums.pop()
    count++
  }
  return nums
}

console.log(rotate([1, 2, 3, 4, 5], 3))
var rotate = function (nums, k) {
  const len = nums.length

  let temp = nums[len - 1]
  let count = 0
  for (let i = 0; i < k; i++) {
    temp = nums[len - i - 1 + count]
    nums.unshift(temp)
    nums.pop()
    count++
  }
  return nums
}

console.log(rotate([1, 2, 3, 4, 5], 3))

取余，然后直接赋值

js
var rotate = function (nums, k) {
  const n = nums.length
  const newArr = new Array(n)
  for (let i = 0; i < n; ++i) {
    newArr[(i + k) % n] = nums[i] // 重点
  }
  for (let i = 0; i < n; ++i) {
    nums[i] = newArr[i]
  }
}

console.log(rotate([1, 2, 3, 4, 5], 3))
var rotate = function (nums, k) {
  const n = nums.length
  const newArr = new Array(n)
  for (let i = 0; i < n; ++i) {
    newArr[(i + k) % n] = nums[i] // 重点
  }
  for (let i = 0; i < n; ++i) {
    nums[i] = newArr[i]
  }
}

console.log(rotate([1, 2, 3, 4, 5], 3))

普通数组-238 除自身以外数组的乘积 ​

左右乘积列表，L 和 R 分别表示左右两侧的乘积列表，然后遍历，L[i] 为索引 i 左侧所有元素的乘积，R[i] 为索引 i 右侧所有元素的乘积，然后遍历，answer[i] = L[i] * R[i]

js
var productExceptSelf = function (nums) {
  const length = nums.length

  // L 和 R 分别表示左右两侧的乘积列表
  const L = new Array(length)
  const R = new Array(length)

  const answer = new Array(length)

  // L[i] 为索引 i 左侧所有元素的乘积
  // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
  L[0] = 1
  for (let i = 1; i < length; i++) {
    L[i] = nums[i - 1] * L[i - 1] // 重点 L[i] 和 L[i - 1]可以表示为前面的累乘
  }

  // R[i] 为索引 i 右侧所有元素的乘积
  // 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
  R[length - 1] = 1
  for (let i = length - 2; i >= 0; i--) {
    R[i] = nums[i + 1] * R[i + 1]
  }

  // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
  for (let i = 0; i < length; i++) {
    answer[i] = L[i] * R[i]
  }

  return answer
}

console.log(productExceptSelf([1, 2, 3, 4]))
var productExceptSelf = function (nums) {
  const length = nums.length

  // L 和 R 分别表示左右两侧的乘积列表
  const L = new Array(length)
  const R = new Array(length)

  const answer = new Array(length)

  // L[i] 为索引 i 左侧所有元素的乘积
  // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
  L[0] = 1
  for (let i = 1; i < length; i++) {
    L[i] = nums[i - 1] * L[i - 1] // 重点 L[i] 和 L[i - 1]可以表示为前面的累乘
  }

  // R[i] 为索引 i 右侧所有元素的乘积
  // 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
  R[length - 1] = 1
  for (let i = length - 2; i >= 0; i--) {
    R[i] = nums[i + 1] * R[i + 1]
  }

  // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
  for (let i = 0; i < length; i++) {
    answer[i] = L[i] * R[i]
  }

  return answer
}

console.log(productExceptSelf([1, 2, 3, 4]))

普通数组-041 缺失的第一个正数 ​

暴力解法，超时了

js
var firstMissingPositive = function (nums) {
  const len = nums.length
  let result = 1
  while (true) {
    if (nums.includes(result)) {
      result++
    } else {
      return result
    }
  }
}

console.log(firstMissingPositive([1, 2, 0]))
var firstMissingPositive = function (nums) {
  const len = nums.length
  let result = 1
  while (true) {
    if (nums.includes(result)) {
      result++
    } else {
      return result
    }
  }
}

console.log(firstMissingPositive([1, 2, 0]))

链表-160 相交链表 ​

用 set 存一个链表，然后遍历另一个链表，如果 set 中包含当前节点，则返回当前节点

js
var getIntersectionNode = function (headA, headB) {
  const set = new Set()
  let temp = headA
  while (temp !== null) {
    set.add(temp)
    temp = temp.next
  }

  temp = headB
  while (temp !== null) {
    if (set.has(temp)) {
      return temp
    }
    temp = temp.next
  }
  return null
}
var getIntersectionNode = function (headA, headB) {
  const set = new Set()
  let temp = headA
  while (temp !== null) {
    set.add(temp)
    temp = temp.next
  }

  temp = headB
  while (temp !== null) {
    if (set.has(temp)) {
      return temp
    }
    temp = temp.next
  }
  return null
}

链表-206 反转链表 ​

pre 是前一个节点，cur 是当前节点，next 是下一个节点，每次将当前节点指向前一个节点，然后前一个节点向后移动，当前节点向后移动

js
var reverseList = function (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(
  reverseList({
    value: 1,
    next: {
      value: 2,
      next: {
        value: 3,
        next: null
      }
    }
  })
)
var reverseList = function (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(
  reverseList({
    value: 1,
    next: {
      value: 2,
      next: {
        value: 3,
        next: null
      }
    }
  })
)

链表-234 回文链表 ​

用数组存链表，然后遍历数组，双指针从两边到中间，如果数组中元素不等于数组中元素的倒序，则返回 false

js
var isPalindrome = function (head) {
  let arr = []
  let left = head

  let right

  while (head) {
    arr.push(head.val)
    head = head.next
  }

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== arr[arr.length - 1 - i]) {
      return false
    }
  }

  return true
}

console.log(
  isPalindrome({
    value: 1,
    next: {
      value: 2
      next: {
        value: 1,
        next: null
      }
    }
  })
)
var isPalindrome = function (head) {
  let arr = []
  let left = head

  let right

  while (head) {
    arr.push(head.val)
    head = head.next
  }

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== arr[arr.length - 1 - i]) {
      return false
    }
  }

  return true
}

console.log(
  isPalindrome({
    value: 1,
    next: {
      value: 2
      next: {
        value: 1,
        next: null
      }
    }
  })
)

链表-141 环形链表 ​

每个遍历到的元素都给 flag，如果遍历到了 flag 则有环

或者快慢指针，因为有环的话一定会重合

js
var hasCycle = function (head) {
  while (head) {
    if (head.flag) {
      return true
    } else {
      head.flag = true
      head = head.next
    }
  }

  return false
}

var hasCycle = function (head) {
  let slow = head
  let fast = head // 乌龟和兔子同时从起点出发
  while (fast && fast.next) {
    // 如果有环的话会一直走环，一定会追上
    slow = slow.next // 乌龟走一步
    fast = fast.next.next // 兔子走两步
    if (fast === slow) {
      // 兔子追上乌龟（套圈），说明有环
      return true
    }
  }
  return false // 访问到了链表末尾，无环
}
var hasCycle = function (head) {
  while (head) {
    if (head.flag) {
      return true
    } else {
      head.flag = true
      head = head.next
    }
  }

  return false
}

var hasCycle = function (head) {
  let slow = head
  let fast = head // 乌龟和兔子同时从起点出发
  while (fast && fast.next) {
    // 如果有环的话会一直走环，一定会追上
    slow = slow.next // 乌龟走一步
    fast = fast.next.next // 兔子走两步
    if (fast === slow) {
      // 兔子追上乌龟（套圈），说明有环
      return true
    }
  }
  return false // 访问到了链表末尾，无环
}

链表-142 环形链表 2 ​

返回第一个节点

js
var detectCycle = function (head) {
  while (head) {
    if (head.flag) {
      return head
    } else {
      head.flag = true
      head = head.next
    }
  }
  return null
}
var detectCycle = function (head) {
  while (head) {
    if (head.flag) {
      return head
    } else {
      head.flag = true
      head = head.next
    }
  }
  return null
}

链表-021 合并两个有序链表 ​

js
//穿针引线
var mergeTwoLists = function (list1, list2) {
  let head = new ListNode()
  let cur = head
  while (list1 && list2) {
    // 如果list1的值更小，穿list1，并且list1++
    if (list1.val <= list2.val) {
      cur.next = list1
      list1 = list1.next
    } else {
      cur.next = list2
      list2 = list2.next
    }
    // 针也要移动一位
    cur = cur.next
  }

  // 链表不等长的时候，因为是有序的，可以直接拼接
  cur.next = list1 !== null ? list1 : list2

  return head.next
}
//穿针引线
var mergeTwoLists = function (list1, list2) {
  let head = new ListNode()
  let cur = head
  while (list1 && list2) {
    // 如果list1的值更小，穿list1，并且list1++
    if (list1.val <= list2.val) {
      cur.next = list1
      list1 = list1.next
    } else {
      cur.next = list2
      list2 = list2.next
    }
    // 针也要移动一位
    cur = cur.next
  }

  // 链表不等长的时候，因为是有序的，可以直接拼接
  cur.next = list1 !== null ? list1 : list2

  return head.next
}

链表-002 两数相加 ​

迭代，哨兵节点，进位，累加

js
var addTwoNumbers = function (l1, l2) {
  const dummy = new ListNode() // 哨兵节点
  let cur = dummy
  let carry = 0 // 进位
  while (l1 || l2 || carry) {
    if (l1) {
      carry += l1.val // 节点值和进位加在一起
      l1 = l1.next // 下一个节点
    }
    if (l2) {
      carry += l2.val // 节点值和进位加在一起
      l2 = l2.next // 下一个节点
    }
    // cur = cur.next = new ListNode(carry % 10) // 每个节点保存一个数位
    let newNode = new ListNode(carry % 10) // 创建新节点
    cur.next = newNode // 连接到当前节点后面
    cur = newNode // 移动指针

    carry = Math.floor(carry / 10) // 新的进位
  }
  return dummy.next // 哨兵节点的下一个节点就是头节点
}
var addTwoNumbers = function (l1, l2) {
  const dummy = new ListNode() // 哨兵节点
  let cur = dummy
  let carry = 0 // 进位
  while (l1 || l2 || carry) {
    if (l1) {
      carry += l1.val // 节点值和进位加在一起
      l1 = l1.next // 下一个节点
    }
    if (l2) {
      carry += l2.val // 节点值和进位加在一起
      l2 = l2.next // 下一个节点
    }
    // cur = cur.next = new ListNode(carry % 10) // 每个节点保存一个数位
    let newNode = new ListNode(carry % 10) // 创建新节点
    cur.next = newNode // 连接到当前节点后面
    cur = newNode // 移动指针

    carry = Math.floor(carry / 10) // 新的进位
  }
  return dummy.next // 哨兵节点的下一个节点就是头节点
}

链表-019 删除链表的倒数第 N 个节点 ​

快慢指针，先走 n 步，然后同时走到底，这是 snow 指针就是 n 的地方

js
var removeNthFromEnd = function (head, n) {
  let dummy = new ListNode()
  dummy.next = head

  let snow = dummy
  let fast = dummy

  while (n !== 0) {
    fast = fast.next
    n--
  }

  while (fast.next) {
    snow = snow.next
    fast = fast.next
  }

  snow.next = snow.next.next

  return dummy.next
}
var removeNthFromEnd = function (head, n) {
  let dummy = new ListNode()
  dummy.next = head

  let snow = dummy
  let fast = dummy

  while (n !== 0) {
    fast = fast.next
    n--
  }

  while (fast.next) {
    snow = snow.next
    fast = fast.next
  }

  snow.next = snow.next.next

  return dummy.next
}

链表-024 两两交换链表中的节点 ​

js
var swapPairs = function (head) {
  if (head === null || head.next === null) {
    return head
  }

  const node1 = head
  const node2 = head.next
  const node3 = node2.next

  node1.next = swapPairs(node3) // 1 指向递归返回的链表头
  node2.next = node1 // 2 指向 1

  return node2 // 返回交换后的链表头节点
}
var swapPairs = function (head) {
  if (head === null || head.next === null) {
    return head
  }

  const node1 = head
  const node2 = head.next
  const node3 = node2.next

  node1.next = swapPairs(node3) // 1 指向递归返回的链表头
  node2.next = node1 // 2 指向 1

  return node2 // 返回交换后的链表头节点
}

链表-146LRU 缓存 ​

js
var LRUCache = function (capacity) {
  this.map = new Map()
  this.len = capacity
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  // 如果没有返回-1
  if (!this.map.has(key)) {
    return -1
  } else {
    let temp = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, temp)
    return this.map.get(key)
  }
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  // 如果有，删除原来的，然后放入到尾部
  // 如果没有，如果map.size = len 则删除头部，放到尾部
  if (this.map.has(key)) {
    let temp = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, value)
  } else {
    // 到缓存极限，删除头部
    if (this.map.size === this.len) {
      this.map.delete(this.map.keys().next().value)
    }
  }
  this.map.set(key, value)
}
var LRUCache = function (capacity) {
  this.map = new Map()
  this.len = capacity
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  // 如果没有返回-1
  if (!this.map.has(key)) {
    return -1
  } else {
    let temp = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, temp)
    return this.map.get(key)
  }
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  // 如果有，删除原来的，然后放入到尾部
  // 如果没有，如果map.size = len 则删除头部，放到尾部
  if (this.map.has(key)) {
    let temp = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, value)
  } else {
    // 到缓存极限，删除头部
    if (this.map.size === this.len) {
      this.map.delete(this.map.keys().next().value)
    }
  }
  this.map.set(key, value)
}

二叉树-094 二叉树的中序遍历 ​

普通就是递归，迭代的话使用栈解决

js
var inorderTraversal = function (root) {
  let arr = []
  function inorder(root) {
    if (!root) {
      return
    }

    inorder(root.left)

    arr.push(root.val)

    inorder(root.right)
  }

  inorder(root)

  return arr
}
var inorderTraversal = function (root) {
  let arr = []
  function inorder(root) {
    if (!root) {
      return
    }

    inorder(root.left)

    arr.push(root.val)

    inorder(root.right)
  }

  inorder(root)

  return arr
}

二叉树-102 二叉树的层序遍历 ​

层序遍历，使用队列，每次遍历一层，然后下一层入队，然后 cur 和 next 指针调换

js
var levelOrder = function (root) {
  if (!root) {
    return []
  }
  const ret = []
  let cur = [root]
  while (cur.length) {
    let next = []
    const vals = []
    for (let i = 0; i < cur.length; i++) {
      vals.push(cur[i].val)
      if (cur[i].left) {
        next.push(cur[i].left)
      }
      if (cur[i].right) {
        next.push(cur[i].right)
      }
    }
    cur = next
    ret.push(vals)
  }
  return ret
}
var levelOrder = function (root) {
  if (!root) {
    return []
  }
  const ret = []
  let cur = [root]
  while (cur.length) {
    let next = []
    const vals = []
    for (let i = 0; i < cur.length; i++) {
      vals.push(cur[i].val)
      if (cur[i].left) {
        next.push(cur[i].left)
      }
      if (cur[i].right) {
        next.push(cur[i].right)
      }
    }
    cur = next
    ret.push(vals)
  }
  return ret
}

二叉树-104 二叉树的最大深度 ​

递归解法

js
var maxDepth = function (root) {
  if (!root) return 0
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}
var maxDepth = function (root) {
  if (!root) return 0
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}

二叉树-226 翻转二叉树 ​

递归解法

js
var invertTree = function (root) {
  if (root === null) {
    return null
  }
  let left = invertTree(root.left)
  let right = invertTree(root.right)
  root.right = left
  root.left = right
  return root
}
var invertTree = function (root) {
  if (root === null) {
    return null
  }
  let left = invertTree(root.left)
  let right = invertTree(root.right)
  root.right = left
  root.left = right
  return root
}

二叉树-101 对称二叉树 ​

js
var isSymmetric = function (root) {
  if (!root) return true

  // 判断两个节点是否对称
  function isMirror(left, right) {
    // 如果两个节点都为空，则对称
    if (!left && !right) return true
    // 如果只有一个节点为空，则不对称
    if (!left || !right) return false
    // 如果两个节点的值不相等，则不对称
    if (left.val !== right.val) return false

    // 递归判断：左节点的左子树与右节点的右子树对称
    // 左节点的右子树与右节点的左子树对称
    return isMirror(left.left, right.right) && isMirror(left.right, right.left)
  }

  return isMirror(root.left, root.right)
}
var isSymmetric = function (root) {
  if (!root) return true

  // 判断两个节点是否对称
  function isMirror(left, right) {
    // 如果两个节点都为空，则对称
    if (!left && !right) return true
    // 如果只有一个节点为空，则不对称
    if (!left || !right) return false
    // 如果两个节点的值不相等，则不对称
    if (left.val !== right.val) return false

    // 递归判断：左节点的左子树与右节点的右子树对称
    // 左节点的右子树与右节点的左子树对称
    return isMirror(left.left, right.right) && isMirror(left.right, right.left)
  }

  return isMirror(root.left, root.right)
}

二叉树-543 二叉树的直径 ​

递归解法

js
var diameterOfBinaryTree = function (root) {
  let ans = 0
  function dfs(node) {
    if (node === null) {
      return -1 // 对于叶子节点，链长就是-1+1=0
    }
    const lLen = dfs(node.left) + 1
    const rLen = dfs(node.right) + 1
    ans = Math.max(lLen, lLen + rLen)
    return Math.max(lLen, rLen)
  }
  dfs(root)
  return ans
}
var diameterOfBinaryTree = function (root) {
  let ans = 0
  function dfs(node) {
    if (node === null) {
      return -1 // 对于叶子节点，链长就是-1+1=0
    }
    const lLen = dfs(node.left) + 1
    const rLen = dfs(node.right) + 1
    ans = Math.max(lLen, lLen + rLen)
    return Math.max(lLen, rLen)
  }
  dfs(root)
  return ans
}

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

递归解法

js
var sortedArrayToBST = function (nums) {
  function dfs(left, right) {
    if (left === right) {
      return null
    }
    const m = Math.floor((left + right) / 2)
    return new TreeNode(nums[m], dfs(left, m), dfs(m + 1, right))
  }
  return dfs(0, nums.length)
}
var sortedArrayToBST = function (nums) {
  function dfs(left, right) {
    if (left === right) {
      return null
    }
    const m = Math.floor((left + right) / 2)
    return new TreeNode(nums[m], dfs(left, m), dfs(m + 1, right))
  }
  return dfs(0, nums.length)
}

二叉树-098 验证二叉搜索树 ​

递归解法

js
const helper = (root, lower, upper) => {
  if (root === null) {
    return true
  }
  if (root.val <= lower || root.val >= upper) {
    return false
  }
  return (
    helper(root.left, lower, root.val) && helper(root.right, root.val, upper)
  )
}

var isValidBST = function (root) {
  return helper(root, -Infinity, Infinity)
}

中序遍历解法

var isValidBST = function (root) {
  let prev = -Infinity

  function inorder(node) {
    if (!node) return true

    // 遍历左子树
    if (!inorder(node.left)) return false

    // 检查当前节点
    if (node.val <= prev) return false
    prev = node.val

    // 遍历右子树
    return inorder(node.right)
  }

  return inorder(root)
}
const helper = (root, lower, upper) => {
  if (root === null) {
    return true
  }
  if (root.val <= lower || root.val >= upper) {
    return false
  }
  return (
    helper(root.left, lower, root.val) && helper(root.right, root.val, upper)
  )
}

var isValidBST = function (root) {
  return helper(root, -Infinity, Infinity)
}

中序遍历解法

var isValidBST = function (root) {
  let prev = -Infinity

  function inorder(node) {
    if (!node) return true

    // 遍历左子树
    if (!inorder(node.left)) return false

    // 检查当前节点
    if (node.val <= prev) return false
    prev = node.val

    // 遍历右子树
    return inorder(node.right)
  }

  return inorder(root)
}

回溯-046 全排列 ​

js
var permute = function (nums) {
  const len = nums.length
  const cur = [] // 当前排列内容
  const res = [] // 所有排列顺序
  const visited = {} // 避免重复使用同于个数字
  function dfs(nth) {
    if (nth === len) {
      res.push(cur.slice())
      return
    }
    // 检查剩下的数字有哪些
    for (let i = 0; i < len; i++) {
      if (!visited[nums[i]]) {
        visited[nums[i]] = 1
        cur.push(nums[i])
        dfs(nth + 1)
        cur.pop()
        visited[nums[i]] = 0
      }
    }
  }
  dfs(0) // 索引为0开始
  return res
}

permute([1, 2, 3])

// 树形结构，不变的是 len = 3，递归的边界也是走到了3，重复检查手里剩下的数字有哪些，选取其中一个填坑

// 抽象成树
// root
// 1 2 3
// 23 13 12
// 32 31 21

// 第一次传入索引 0，没到边界，进入循环 i1=0，没有用过则标记1并且放进 Cur，递归，此时 cur = [1]
// 没到边界，i2 = 0 不满足，i2 = 1，满足条件，标记2放进Cur，递归，此时cur = [1,2]
// i3 = 0/i3= 1 都不满足，i3 = 2满足没被标记，标记3，放进Cur，此时Cur = [1,2,3]，进入递归满足边界 nth === len，放进 res，此时res = [[1,2,3]]，然后pop cur = [1,2]，3取消标记

// 继续 i2 = 1，pop 后 cur = [1]，2取消标记
// i2 = 2，满足没被标记，cur = [1,3]，进入递归，找到满足条件的[1,3,2]
var permute = function (nums) {
  const len = nums.length
  const cur = [] // 当前排列内容
  const res = [] // 所有排列顺序
  const visited = {} // 避免重复使用同于个数字
  function dfs(nth) {
    if (nth === len) {
      res.push(cur.slice())
      return
    }
    // 检查剩下的数字有哪些
    for (let i = 0; i < len; i++) {
      if (!visited[nums[i]]) {
        visited[nums[i]] = 1
        cur.push(nums[i])
        dfs(nth + 1)
        cur.pop()
        visited[nums[i]] = 0
      }
    }
  }
  dfs(0) // 索引为0开始
  return res
}

permute([1, 2, 3])

// 树形结构，不变的是 len = 3，递归的边界也是走到了3，重复检查手里剩下的数字有哪些，选取其中一个填坑

// 抽象成树
// root
// 1 2 3
// 23 13 12
// 32 31 21

// 第一次传入索引 0，没到边界，进入循环 i1=0，没有用过则标记1并且放进 Cur，递归，此时 cur = [1]
// 没到边界，i2 = 0 不满足，i2 = 1，满足条件，标记2放进Cur，递归，此时cur = [1,2]
// i3 = 0/i3= 1 都不满足，i3 = 2满足没被标记，标记3，放进Cur，此时Cur = [1,2,3]，进入递归满足边界 nth === len，放进 res，此时res = [[1,2,3]]，然后pop cur = [1,2]，3取消标记

// 继续 i2 = 1，pop 后 cur = [1]，2取消标记
// i2 = 2，满足没被标记，cur = [1,3]，进入递归，找到满足条件的[1,3,2]