算法打卡

粉刷房子

地址(opens new window)

function minCost(costs: number[][]): number {
    const len = costs.length
    let [red, blue, pink] = [0, 0, 0]

    for (let i = 0; i < len; i++) {
        [red, blue, pink] = [Math.min(blue, pink) + costs[i][0], Math.min(red, pink) + costs[i][1], Math.min(red, blue) + costs[i][2]]
    }

    return Math.min(red, blue, pink)
};

移动零

地址(opens new window)

// 时间复杂度为O(n)、空间复杂度为O(1)
function moveZeroes(nums: number[]): void {
    let prev = 0
    let next = 1
    const len = nums.length
    while (next < len) {
        if (nums[prev]) {
           prev++
           if (prev === next) {
               next++
           }
           continue
        }

        while (nums[next] === 0) {
            next++
        }

        if (next >= len) {
            break
        }

        nums[prev++] = nums[next]
        nums[next++] = 0
    }
};

// 时间复杂度为O(n)、空间复杂度为O(1)
function moveZeroes(nums: number[]): void {
    let prev = 0
    let next = 0

    while(next < nums.length) {
        if (!nums[next]) {
            next++
            continue
        }
        nums[prev++] = nums[next++]
    }

    for(let i = prev; i < nums.length; i++) {
        nums[i] = 0
    }
};

function moveZeroes(nums: number[]): void {
    const len = nums.length
    if (len === 1) {
        return
    }
    let slow = 0
    for (let i = 0; i < len; i++) {
        if (nums[i]) {
            let mid = nums[i]
            nums[i] = nums[slow]
            nums[slow++] = mid
        }
    }
};

独一无二的出现次数

地址(opens new window)

// 先获取值然后去重对比
function uniqueOccurrences(arr: number[]): boolean {
    const map = new Map()

    for (const num of arr) {
        map.set(num, (map.get(num) || 0) + 1)
    }

    const values = Array.from(map.values())
    return values.length === [...new Set(values)].length
};

有效的山脉数组

地址(opens new window)

function validMountainArray(arr: number[]): boolean {
    const len = arr.length

    // 数组小于2或第2个小于前一个的时候
    if (len <= 2 || arr[1] <= arr[0] || arr[len-2] <= arr[len-1]) {
        return false
    }

    let prev = 2
    let next = len - 3

    while (prev <= next) {
        if (arr[prev] === arr[prev-1] || arr[next] === arr[next+1]) {
            return false
        }

        if (arr[prev] > arr[prev-1]) {
            prev++
            continue
        }

        if (arr[next] > arr[next+1]) {
            next--
            continue
        }

        return false
    }
    return true
};

有多少小于当前数字的数字

地址(opens new window)

function smallerNumbersThanCurrent(nums: number[]): number[] {
    let numMap = [...nums].sort((prev, next) => prev - next).reduce((prev, next, i) => {
        if (!prev.has(next)) {
            prev.set(next, i)
        }
        return prev
    }, new Map())
    let result: number[] = []

    for (const num of nums) {
        result.push(numMap.get(num))
    }

    return result
};

水壶问题

地址(opens new window)

function canMeasureWater(jug1Capacity: number, jug2Capacity: number, targetCapacity: number): boolean {
  let max = Math.max(jug1Capacity, jug2Capacity)
  let min = Math.min(jug1Capacity, jug2Capacity)

  // 1. 两个都装了还不够
  if (max + min < targetCapacity) {
    return false
  }

  let result = max + min
  let set = new Set()
  while (result > targetCapacity) {

    // 先倒掉min
    result -= min

    if (result < targetCapacity) {
      // 注水
      result += max
    }

    if (set.has(result)) {
      return false
    }

    set.add(result)
  }

  return result === targetCapacity
}

轮转数组

地址(opens new window)

function rotate(nums: number[], k: number): void {
  // 先计算nums的长度，比较k的长度，如果k>len则需要减去len的倍数
  const len = nums.length
  const offset = len - k % len

  // 然后移动
  for (let i = len - 1; i >= offset; i--) {
      nums.unshift(nums.pop())
  }
};

最后一个单词的长度

地址(opens new window)

function lengthOfLastWord(s: string): number {
  let result = 0
  s = s.trim()
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === ' ') {
      return result
    }
    result++
  }
  return result
};

最长公共前缀

地址(opens new window)

// 两重循环
function longestCommonPrefix(strs: string[]): string {
  if (!strs.length) {
    return ''
  }

  let str = ''
  for (let i = 0; i < strs[0].length; i++) {
    for (let j = 1; j < strs.length; j++) {
      if (strs[j][i] !== strs[0][i]) {
        return str
      }
    }

    str += strs[0][i]
  }

  return str
}

柱状图中最大的矩形

地址(opens new window)

// 双指针，超出了时间限制
function largestRectangleArea(heights: number[]): number {
  const len = heights.length
  // 大于当前值的最大index
  let maxIndex = 0

  // 大于当前值的最小index
  let minIndex = 0
  let result = 0

  for (let i = 0; i < len; i++) {
    maxIndex = i
    minIndex = i
    for (let j = i + 1; j < len; j++) {
     if (heights[j] < heights[i]) {
       break
      }
      maxIndex = j
    }

    for (let j = i - 1; j >= 0; j--) {
      if (heights[j] < heights[i]) {
        break
      }
      minIndex = j
    }

    result = Math.max(result, (maxIndex - minIndex + 1) * heights[i])
  }

  return result
};

// 动态规划
function largestRectangleArea(heights: number[]): number {
  const len = heights.length
  let result = heights[0]

  // leftIndex[i] 代表heights[i]时左边的index
  let leftIndex: number[] = [-1]
  let rightIndex: number[] = []

  for (let i = 1; i < len; i++) {
    let j = i - 1
    while (j >= 0 && heights[j] >= heights[i]) {
      // leftIndex[j]表示左边第一个小于该值的坐标
      j = leftIndex[j]
    }

    leftIndex[i] = j
  }

  rightIndex[len-1] = len
  for (let i = len - 2; i >= 0; i--) {
    let j = i + 1
    while(j < len && heights[j] >= heights[i]) {
      j = rightIndex[j]
    }

    rightIndex[i] = j
  }

  for (let i = 0; i < len; i++) {
    result = Math.max(result, heights[i] * (rightIndex[i] - leftIndex[i] - 1))
  }
  return result
};

// 计算凸槽，接雨水时计算凹槽
// 单调栈
function largestRectangleArea(heights: number[]): number {
  heights.unshift(0)
  heights.push(0)
  const len = heights.length
  let result = 0
  const stack: number[] = [0]

  for (let i = 1; i < len; i++) {
    // 1. 小于情况，可以去除
    if (heights[i] > heights[stack[0]]) {
      stack.unshift(i)
      continue
    }

    // 2. 等于情况
    if (heights[i] === heights[stack[0]]) {
      stack.shift()
      stack.unshift(i)
      continue
    }

    while(heights[i] < heights[stack[0]]) {
      let index = stack.shift()
      result = Math.max(result, heights[index] * (i - stack[0] - 1))
    }
    stack.unshift(i)
  }

  return result
};

function largestRectangleArea(heights: number[]): number {
    let len = heights.length
    if (!len) {
        return 0
    }

    heights.unshift(0)
    heights.push(0)
    len = heights.length
    const stack: number[] = [0]
    let result: number = 0

    for (let i = 1; i < len; i++) {
        while (heights[i] < heights[stack[stack.length - 1]]) {
            const mid = stack.pop()
            const left = stack[stack.length - 1]
            result = Math.max(result, (i - left - 1) * heights[mid])
        }
        stack.push(i)
    }

    return result
};

接雨水

地址(opens new window)

// 从左到右计算
// 一遇到大元素就减去栈头元素
function trap(height: number[]): number {
  const len = height.length
  if (!len) {
    return 0
  }

  let result = 0
  const caculate = (arr: number[]) => {
    const dp: number[] = [0]
    for (let i = 1; i < arr.length; i++) {
      // 查看元素是否大于栈顶，假设小于栈顶
      if (arr[i] < arr[dp[0]]) {
        dp.push(i)
        continue
      }

      // 计算接到的雨水面积
      let sum = (i - dp[0]) * Math.min(arr[i], arr[dp[0]])
      while (dp.length) {
        sum -= arr[dp.pop()]
      }
      result += sum
      dp.push(i)
    }

    return dp.length
  }

  let dpLen = caculate(height)

  // 这里的目的是截取剩余数组进行反向查询
  caculate(height.reverse().slice(0, dpLen))

  return result
};

// 使用双指针法
// 从左边找到最大的，从右边找到最大的，然后取最小的，计算该坐标点的雨水面积
function trap(height: number[]): number {
  const len = height.length
  if (!len) {
    return 0
  }

  let result = 0

  for (let i = 1; i < len - 1; i++) {
    let leftMax = 0
    let rightMax = 0
    for (let j = i - 1; j >= 0; j--) {
      if (height[j] > height[i]) {
        leftMax = Math.max(leftMax, height[j])
      }
    }

    for (let j = i + 1; j < len; j++) {
      if (height[j] > height[i]) {
        rightMax = Math.max(rightMax, height[j])
      }
    }

    let val = Math.min(leftMax, rightMax) - height[i]
    if (val > 0) {
      result += val
    }
  }

  return result
};

// 使用动态规划
// 思路和双指针一致，找到左边最大值和右边最大值
function trap(height: number[]): number {
  const len = height.length
  if (!len) {
    return 0
  }

  let result = 0
  let leftMax = height[0]
  let rightMax = height[len-1]
  const maxArr: number[][] = Array.from({ length: len }, () => [leftMax, rightMax])

  for (let i = 1; i < len; i++) {
    leftMax = Math.max(leftMax, height[i])
    rightMax = Math.max(rightMax, height[len-i-1])
    maxArr[i][0] = leftMax
    maxArr[len-i-1][1] = rightMax
  }

  for (let i = 1; i < len - 1; i++) {
    let val = Math.min(maxArr[i][0], maxArr[i][1]) - height[i]
    if (val > 0) {
      result += val
    }
  }

  return result
};

// 使用单调栈
function trap(height: number[]): number {
  const len = height.length
  if (len <= 2) {
    return 0
  }

  let result = 0
  const stack: number[] = [0]

  for (let i = 1; i < len; i++) {
    // 查看值
    if (height[i] < height[stack[0]]) {
      stack.unshift(i)
      continue
    }

    // 相等时赋值后面的原因是后面较大的值应该减去的是最右边的相等值
    if (height[i] === height[stack[0]]) {
      stack.shift()
      stack.unshift(i)
      continue
    }

    while(stack.length > 0) {
      let index = stack.shift()

      // 如果还存在值，那么计算凹槽内雨水面积
      if (stack.length) {
        result += (i - stack[0] - 1) * (Math.min(height[stack[0]], height[i]) - height[index])
      }

      // 如果小于栈顶元素，那么退出
      if (height[stack[0]] > height[i]) {
        break
      }
    }

    stack.unshift(i)
  }

  return result
};

// 使用单调栈优化
function trap(height: number[]): number {
  const len = height.length
  if (len <= 2) {
    return 0
  }

  let result = 0
  const stack: number[] = [0]

  for (let i = 1; i < len; i++) {
    while(stack.length > 0 && height[i] > height[stack[0]]) {
      let index = stack.shift()

      // 如果还存在值，那么计算凹槽内雨水面积
      if (stack.length) {
        result += (i - stack[0] - 1) * (Math.min(height[stack[0]], height[i]) - height[index])
      }
    }

    stack.unshift(i)
  }

  return result
}

// 使用单调栈
function trap(height: number[]): number {
    const len = height.length
    if (!len) {
        return 0
    }

    const stack: number[] = [0]
    let result: number = 0

    for (let i = 1; i < len; i++) {
        while (height[i] > height[stack[stack.length - 1]]) {
            let mid = stack.pop()
            if (stack.length) {
                let prev = stack[stack.length - 1]
                result += (Math.min(height[prev], height[i]) - height[mid]) * (i - prev - 1)
            }
        }
        stack.push(i)
    }

    return result
};

下一个更大元素 II

地址(opens new window)

// 暴力破解
function nextGreaterElements(nums: number[]): number[] {
  const len = nums.length
  const dp: number[] = Array(len)

  for (let i = 0; i < len; i++) {

    // 从前往后遍历
    for (let j = i + 1; j < len; j++) {
      if (nums[j] > nums[i]) {
        dp[i] = nums[j]
        break
      }
    }

    if (typeof dp[i] === 'undefined') {
      // 从前往后遍历
      for (let j = 0; j < i; j++) {
        if (nums[j] > nums[i]) {
          dp[i] = nums[j]
          break
        }
      }
    }

    if (typeof dp[i] === 'undefined') {
      dp[i] = -1
    }
  }

  return dp
};

// 单调栈，思路参考之前的下一个更大元素1
function nextGreaterElements(nums: number[]): number[] {
  // 除最后一项外同一连接
  const nums2 = nums.concat(nums.slice(0, -1))
  const len = nums.length
  const result: number[] = Array(nums2.length).fill(-1)
  const stack: number[] = [0]

  for (let i = 1; i < nums2.length; i++) {
    // 大于栈顶元素
    if (nums2[i] > nums2[stack[0]]) {
      while(stack.length && nums2[stack[0]] < nums2[i]) {
        let index = stack.shift()
        result[index] = nums2[i]
      }
    }


    stack.unshift(i)
  }

  return result.slice(0, len)
};

// 走两遍，优化上一种扩充方法
function nextGreaterElements(nums: number[]): number[] {
    const stack: number[] = []
    const len = nums.length
    const result: number[] = Array(len).fill(-1)
    for (let i = 0, len1 = len * 2; i < len1; i++) {
        while (stack.length && nums[i % len] > nums[stack[stack.length-1]]) {
            result[stack.pop()] = nums[i % len]
        }
        stack.push(i % len)
    }

    return result
};

下一个更大元素 I

地址(opens new window)

// 思想和每日温度差不多
function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  // 记录栈序号
  const stack: number[] = [nums2[0]]
  const result: number[] = []
  // 记录结果
  const map = new Map([
    [nums2[0], -1]
  ])

  for (let i = 1; i < nums2.length; i++) {
    map.set(nums2[i], -1)

    while(stack.length && stack[stack.length-1] < nums2[i]) {
      map.set(stack.pop(), nums2[i])
    }

    stack.push(nums2[i])
  }

  for (let i = 0; i < nums1.length; i++) {
    result[i] = map.get(nums1[i])
  }

  return result
}

每日温度

地址(opens new window)

// 栈方法
function dailyTemperatures(temperatures: number[]): number[] {
  // 记录温度序号
  const stack: number[] = [0]

  // 记录结果
  const result: number[] = [0]

  for (let i = 1; i < temperatures.length; i++) {
    result[i] = 0

    while(stack.length && temperatures[stack[stack.length-1]] < temperatures[i]) {
      let index = stack.pop()
      result[index] = i - index
    }

    stack.push(i)
  }

  return result
};

最长回文子序列

地址(opens new window)

// dp[i][j] 代表i到j中最长的回文字符串
// 如果s[i] !== s[j] 那么dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j])
// 如果s[i] === s[j]  1. j - i < 2 dp[i][j] = j - i + 1
//                    2. dp[i+1][j-1] + 2
function longestPalindromeSubseq(s: string): number {
  const len = s.length
  if (!len) {
    return 0
  }
  const dp: number[][] = Array.from({ length: len + 1 }, () => Array(len+1).fill(0))

  for (let i = len; i > 0; i--) {
    for (let j = i; j <= len; j++) {
      if (s[i-1] !== s[j-1]) {
        dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j])
        continue
      }

      if (j - i < 2) {
        dp[i][j] = j - i + 1
      } else {
        dp[i][j] = dp[i+1][j-1] + 2
      }
    }
  }

  return dp[1][len]
};

function longestPalindromeSubseq(s: string): number {
    const len = s.length
    const dp: number[][] = Array.from({ length: len }, () => Array(len).fill(0))
    let result = 0

    for (let i = len - 1; i >= 0; i--) {
        for (let j = i; j < len; j++) {
            if (j === i) {
                dp[i][j] = 1
            } else {
                if (s[i] === s[j]) {
                    dp[i][j] = dp[i+1][j-1] + 2
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j])
                }
            }

            if (dp[i][j] > result) {
                result = dp[i][j]
            }
        }
    }

    return result
};

回文子串

地址(opens new window)

// 动态规划
// dp[i][j] 为第i个字符与第j个字符间是否为回文
// 1. s[i] !== s[j]，那么不为回文
// 2. s[i] === s[j] i === j，那么是回文
//                  j - i === 1，也是回文
//                  中间是否为回文，如果dp[i+1][j-1]
function countSubstrings(s: string): number {
  const len = s.length
  const dp: boolean[][] = Array.from({ length: len + 1}, () => Array(len+1).fill(false))

  let result = 0
  for (let i = len; i > 0; i--) {
    for (let j = i; j <= len; j++) {
      if (s[i-1] !== s[j-1]) {
        dp[i][j] = false
        continue
      }

      if (j - i < 2 || dp[i+1][j-1]) {
        result++
        dp[i][j] = true
        continue
      }

      dp[i][j] = false
    }
  }

  return result
};

// 双指针法
function countSubstrings(s: string): number {
  const len = s.length
  let result = 0

  // 1个中心点或2个中心点
  const extend = (s: string, prev: number, next: number, len: number) => {
    let res = 0
    while(prev >= 0 && next < len && s[prev] === s[next]) {
      prev--
      next++
      res++
    }
    return res
  }
  for (let i = 0; i < len; i++) {
    result += extend(s, i, i, len)
    result += extend(s, i, i+1, len)
  }

  return result
};

编辑距离

地址(opens new window)

// dp[i][j]
// 1. 相等情况 dp[i][j] = dp[i-1][j-1]
// 2. 不相等情况 dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
// dp[i-1][j-1] 替换操作 dp[i-1][j] 插入操作 dp[i][j-1] 删除操作
function minDistance(word1: string, word2: string): number {
  const dp: number[][] = [Array.from({ length: word1.length + 1 }, (i, index) => index)]

  for (let i = 1; i <= word2.length; i++) {
    dp[i] = [i]
    for (let j = 1; j <= word1.length; j++) {
      // 相等的情况
      if (word2[i-1] === word1[j-1]) {
        dp[i][j] = dp[i-1][j-1]
      } else {
        dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
      }
    }
  }

  return dp[word2.length][word1.length]
}

function minDistance(word1: string, word2: string): number {
    const len1 = word1.length
    const len2 = word2.length
    if (!len1) {
        return len2
    }

    if (!len2) {
        return len1
    }

    const dp: number[][] = Array.from({ length: len1 + 1 }, () => Array(len2 + 1).fill(0))
    for (let i = 1; i <= len2; i++) {
        dp[0][i] = i
    }

    for (let i = 1; i <= len1; i++) {
        dp[i][0] = i
    }

    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            if (word1[i-1] === word2[j-1]) {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = Math.min(dp[i-1][j-1] + 1, dp[i-1][j] + 1, dp[i][j-1] + 1)
            }
        }
    }

    return dp[len1][len2]
};

不同的子序列

地址(opens new window)

// dp[i][j]
// 1. 匹配到之前的个数 + 当前匹配的个数 dp[i-1][j-1](上一个字符串匹配的个数) + dp[i][j-1](当前字符串在之前的匹配个数)
// 2. dp[i][j-1]
function numDistinct(s: string, t: string): number {
  if (t.length > s.length) {
    return 0
  }
  const dp: number[][] = [Array(s.length + 1).fill(1)]

  for (let i = 1; i <= t.length; i++) {
    dp[i] = [0]
    for (let j = 1; j <= s.length; j++) {
      if (t[i-1] === s[j-1]) {
        dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
      } else {
        dp[i][j] = dp[i][j-1]
      }
    }
  }
  return dp[t.length][s.length]
};

// dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
// dp[i][j] = dp[i-1][j]
function numDistinct(s: string, t: string): number {
    const sLen = s.length
    const tLen = t.length
    if (sLen < tLen) {
        return 0
    }

    const dp: number[][] = Array.from({ length: sLen + 1 }, () => Array(tLen + 1).fill(0))
    dp[0][0] = 1

    for (let i = 1; i <= sLen; i++) {
        dp[i][0] = 1
        for (let j = 1; j <= tLen; j++) {
            if (s[i-1] === t[j-1]) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }

    return dp[sLen][tLen]
};

判断子序列

地址(opens new window)

// 思路和最长公共子序列相同
function isSubsequence(s: string, t: string): boolean {
  if (s.length > t.length) {
    return false
  }

  if (!s.length) {
    return true
  }

  const dp: number[][] = [...Array(t.length + 1).fill(0).map(() => Array(s.length + 1).fill(0))]

  for (let i = 1; i <= t.length; i++) {
    for (let j = 1; j <= s.length; j++) {
      if (t[i-1] !== s[j-1]) {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
        continue
      }
      dp[i][j] = dp[i-1][j-1] + 1

      if (dp[i][j] === s.length) {
        return true
      }
    }
  }

  return false
}

不相交的线

地址(opens new window)

// 思路、代码和最长公共子序列一致，只是修改变量即可
function maxUncrossedLines(nums1: number[], nums2: number[]): number {
  const len1 = nums1.length
  const len2 = nums2.length
  if (!len1 || !len2) {
    return 0
  }

  const dp: number[][] = [...Array(len1 + 1).fill(0).map(() => Array(len2 + 1).fill(0))]

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      // 判断字符是否相等
      if (nums1[i-1] !== nums2[j-1]) {
        dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])
        continue
      }
      dp[i][j] = dp[i-1][j-1] + 1
    }
  }
  return dp[len1][len2]
};

最长公共子序列

地址(opens new window)

// dp[i][j] 表示最长的公共子数组
// 1. 相等情况 dp[i][j] = dp[i-1][j-1]
// 2. 不相等情况 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
function longestCommonSubsequence(text1: string, text2: string): number {
  const len1 = text1.length
  const len2 = text2.length
  if (!len1 || !len2) {
    return 0
  }

  const dp: number[][] = [Array(len2).fill(1)]

  // 先遍历第一层
  for (let j = 0; j < len2; j++) {
    if (text2[j] === text1[0]) {
      break
    }
    dp[0][j] = 0
  }

  // 判断首个值
  for (let i = 1; i < len1; i++) {
    dp[i] = []
    if (text1[i] === text2[0] || dp[i-1][0]) {
      dp[i][0] = 1
    } else {
      dp[i][0] = 0
    }
  }

  for (let i = 1; i < len1; i++) {
    for (let j = 1; j < len2; j++) {
      // 判断字符是否相等
      if (text1[i] !== text2[j]) {
        dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])
        continue
      }
      dp[i][j] = dp[i-1][j-1] + 1
    }
  }

  return dp[len1-1][len2-1]
};

优化

function longestCommonSubsequence(text1: string, text2: string): number {
  const len1 = text1.length
  const len2 = text2.length
  if (!len1 || !len2) {
    return 0
  }

  const dp: number[][] = [...Array(len1 + 1).fill(0).map(() => Array(len2 + 1).fill(0))]

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      // 判断字符是否相等
      if (text1[i-1] !== text2[j-1]) {
        dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])
        continue
      }
      dp[i][j] = dp[i-1][j-1] + 1
    }
  }
  return dp[len1][len2]
}

最长重复子数组

地址(opens new window)

// dp[i][j] 表示匹配到时的长度
// dp[i][j]
// nums1[i] === nums[j] 匹配到了，则dp[i-1][j-1] + 1
// 未匹配到则dp[i][j] = 0
function findLength(nums1: number[], nums2: number[]): number {
  const num1Len = nums1.length
  const num2Len = nums2.length
  const dp: number[][] = []
  let maxLen = 0

  for (let i = 0; i < num1Len; i++) {
    dp[i] = []
    for (let j = 0; j < num2Len; j++) {
      if (nums1[i] !== nums2[j]) {
        dp[i][j] = 0
      } else {
        dp[i][j] = (i === 0 || j === 0 ? 0 : dp[i-1][j-1]) + 1
      }

      if (dp[i][j] > maxLen) {
        maxLen = dp[i][j]
      }
    }
  }

  return maxLen
};

最长连续递增序列

地址(opens new window)

// dp[i] 表示第i个时最大的子序列长度
// dp[i] = dp[i-1] + 1 || 1
function findLengthOfLCIS(nums: number[]): number {
  const len = nums.length
  const dp: number[] = Array(len).fill(1)
  let result = 1
  for (let i = 1; i < len; i++) {
    dp[i] = nums[i] > nums[i-1] ? dp[i-1] + 1 : 1

    if (dp[i] > result) {
      result = dp[i]
    }
  }
  return result
};

// 优化空间
function findLengthOfLCIS(nums: number[]): number {
    const len = nums.length
    let prev = 1
    let result = 1
    for (let i = 1; i < len; i++) {
        prev = nums[i] > nums[i-1] ? prev + 1 : 1
        if (prev > result) {
            result = prev
        }
    }

    return result
}

最长递增子序列

地址(opens new window)

// 动态规划
// dp[i] 表示第i个时最大的子序列长度
// dp[i] = Math.max(dp[i], dp[j] + 1)
function lengthOfLIS(nums: number[]): number {
  const len = nums.length
  const dp: number[] = Array(len).fill(1)
  let result = 1
  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }

    if (dp[i] > result) {
      result = dp[i]
    }
  }

  return result
}

解题思路(opens new window)

// 贪心 + 二分
function lengthOfLIS(nums: number[]): number {
    const dp: number[] = [nums[0]]

    for (let i = 1; i < nums.length; i++) {
        const len = dp.length - 1
        if (nums[i] > dp[dp.length - 1]) {
            dp.push(nums[i])
        } else {
            // 二分查找

            let left = 0
            let right = len
            while(left <= right) {
                const mid = Math.floor((left + right) / 2)
                if (dp[mid] >= nums[i]) {
                    right = mid - 1
                } else {
                    left = mid + 1
                }
            }

            dp[left] = nums[i]
        }
    }

    return dp.length
};

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

地址(opens new window)

// 持有
// dp[i][0]
// 要么继续持有dp[i-1][0]
// 要么买入冰冻期前 dp[i-2][1] - prices[i]

// 不持有
// dp[i][1]
// 继续保持不持有 dp[i-1][1]
// 卖出 dp[i-1][0] + prices[i]
function maxProfit(prices: number[]): number {
  const len = prices.length
  if (!len) {
    return 0
  }

  const dp: number[][] = [[-prices[0], 0]]
  dp[-1] = [0, 0]

  for (let i = 1; i < len; i++) {
    dp[i] = []
    dp[i][0] = Math.max(dp[i-1][0], dp[i-2][1] - prices[i])
    dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
  }

  return dp[len-1][1]
}

// dp[i][0] 持有股票
// dp[i][1] 不持有股票
// dp[i][2] 冷冻期
function maxProfit(prices: number[]): number {
    const len = prices.length
    const dp: [number, number, number][] = Array.from({ length: len }, () => [0, 0, 0])
    dp[0] = [-prices[0], 0, 0]
    for (let i = 1; i < len; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i - 1][2] - prices[i])
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
        dp[i][2] = dp[i-1][1]
    }

    return dp[len-1][1]
};

买卖股票的最佳时机 IV

地址(opens new window)

// 参考股票买卖3
function maxProfit(k: number, prices: number[]): number {
  const len = prices.length
  // 注意特殊场景
  if (!len || !k) {
    return 0
  }
  const kLen = Math.min(k * 2, len * 2)
  const dp: number[][] = Array(len)
  dp[0] = []
  for (let i = 0; i < kLen; i++) {
    dp[0][i] = i % 2 ? 0 : -prices[0]
  }

  for (let i = 1; i < len; i++) {
    dp[i] = []
    dp[i][0] = Math.max(dp[i-1][0], -prices[i])
    for (let j = 1; j < kLen; j++) {
      dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] + prices[i] * (j % 2 ? 1 : -1))
    }
  }

  return dp[len-1][kLen-1]
}

买卖股票的最佳时机 III

地址(opens new window)

// 持有(第一次)  不持有  持有(第二次)  不持有

// 0 代表第一次持有
// dp[i][0] = Math.max(dp[i-1][0], -prices[i])

// 1 代表第一次不持有
// dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])

// 2 代表第二次持有
// dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] - prices[i])

// 3 代表第二次不持有
// dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i])

function maxProfit(prices: number[]): number {
  const len = prices.length
  const dp: number[][] = Array(len).fill([])

  // 1. 持有
  // dp[0][0] = -prices[0]

  // // 1. 不持有
  // dp[0][1] = 0

  // // 2. 持有
  // dp[0][2] = -prices[0]

  // // 3. 不持有
  // dp[0][3] = 0
  dp[0] = [-prices[0], 0, -prices[0], 0]

  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.max(dp[i-1][0], -prices[i])
    dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
    dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] - prices[i])
    dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i])
  }

  return dp[len-1][3]
}

买卖股票的最佳时机

地址(opens new window)

// p[i]代表第i天卖出时的最大利润
// 1. 第i天的股票卖出最大 prices[i] - 极小值
// 2. 第i天的股票不买最大 p[i-1]
function maxProfit(prices: number[]): number {
  let min = prices[0]
  const len = prices.length
  const dp: number[] = Array(len).fill(0)
  dp[0] = 0

  for (let i = 1; i < len; i++) {
    dp[i] = Math.max(dp[i-1], prices[i] - min)
    min = Math.min(prices[i], min)
  }

  return dp[len-1]
}

优化变量

// 贪心
function maxProfit(prices: number[]): number {
  const len = prices.length
  if (len <= 1) {
    return 0
  }
  let next = 0
  let min = prices[0]

  for (let i = 1; i < len; i++) {
    next = Math.max(next, prices[i] - min)
    min = Math.min(prices[i], min)
  }

  return next
}

动态规划

// dp[i][0] 表示第i天持有股票所得最多现金
// i-1持有股票，所得现金就是昨天持有股票所得现金 dp[i-1][0]
// 第i天买入股票，所得现金就是买入股票后所得现金 -prices[i]

// dp[i][1] 表示第i天不持有股票所得最多现金
// i-1天不持有 dp[i-1][1]
// 第i天卖出 prices[i] + dp[i-1][0]

// dp[0][0] = -prices[0]
// dp[0][1] = 0

function maxProfit(prices: number[]): number {
  const len = prices.length
  const dp: number[][] = Array(len).fill([])

  // 持有
  dp[0][0] = -prices[0]

  // 不持有
  dp[0][1] = 0

  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.max(dp[i-1][0], -prices[i])
    dp[i][1] = Math.max(dp[i-1][1], prices[i] + dp[i-1][0])
  }

  return dp[len-1][1]
}

// 还有一种动态加贪心
function maxProfit(prices: number[]): number {
    const len = prices.length
    const dp: number[] = Array(len).fill(0)
    let min = prices[0]

    for (let i = 1; i < len; i++) {
        dp[i] = Math.max(dp[i-1], prices[i] - min)
        if (prices[i] < min) {
            min = prices[i]
        }
    }

    return dp[len-1]
};

打家劫舍 III

地址(opens new window)

// 暴力破解
function rob(root: TreeNode | null): number {
  const map = new Map()
  const cascader = (root: TreeNode | null) => {
    if (!root) {
      return 0
    }

    if (map.has(root)) {
      return map.get(root)
    }

    let val1 = root.val
    if (root.left) {
      val1 += cascader(root.left.left) + cascader(root.left.right)
    }
    if (root.right) {
      val1 += cascader(root.right.left) + cascader(root.right.right)
    }

    let val2 = cascader(root.left) + cascader(root.right)
    map.set(root, Math.max(val1, val2))

    return map.get(root)
  }

  cascader(root)
  return map.get(root)
}

// 动态规划
function rob(root: TreeNode | null): number {
  // 前面一个返回参数代表不偷当前节点，后一个代表偷当前节点
  const cascader = (root: TreeNode | null): [number, number] => {
    if (!root) {
      return [0, 0]
    }

    const left = cascader(root.left)
    const right = cascader(root.right)

    return [Math.max(...left) + Math.max(...right), root.val + left[0] + right[0]]
  }

  return Math.max(...cascader(root))
}

打家劫舍 II

地址(opens new window)

// p[i] 代表在i时盗窃的最大金额
// p[i] = Math.max(p[i-1], p[i-2] + nums[i-1])
// 1. 排除最后一个房屋
// 2. 排除第一个房屋
// 比较最大值
function rob(nums: number[]): number {
  const len = nums.length

  if (len === 0) {
    return 0
  }
  if (len === 1) {
    return nums[0]
  }

  const dp: number[] = [0, nums[0]]
  // 排除最后一个
  for (let i = 2; i <= len - 1; i++) {
    dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1])
  }

  // 排除第一个
  const dp2: number[] = [0, nums[1]]
  for (let i = 2; i <= len - 1; i++) {
    dp2[i] = Math.max(dp2[i-1], dp2[i-2] + nums[i])
  }

  return Math.max(dp[len-1], dp2[len-1])
}

// 采用打家劫舍1的方式进行比较
function rob(nums: number[]): number {
  const len = nums.length

  if (len === 0) {
    return 0
  }

  if (len === 1) {
    return nums[0]
  }

  const robResult = (nums: number[]) => {
    const len = nums.length
    let [prev, next] = [0, nums[0]]
    for (let i = 2; i <= len; i++) {
      [prev, next] = [next, Math.max(next, prev + nums[i-1])]
    }
    return next
  }

  return Math.max(robResult(nums.slice(0, -1)), robResult(nums.slice(1)))
}

打家劫舍

地址(opens new window)

// p[i] 代表在i时盗窃的最大金额
// 1. 该房间不盗窃p[i-1]
// 2. 该房间盗窃p[i-2] + nums[i-1]，这个根据长度取得，因此需要i-1才能表示具体的房间
// p[i] = Math.max(p[i-1], p[i-2] + nums[i-1])
function rob(nums: number[]): number {
  const len = nums.length
  const dp: number[] = [0, nums[0]]
  for (let i = 2; i <= len; i++) {
    dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1])
  }

  return dp[len]
}

// 不包含0个的情况
function rob(nums: number[]): number {
  const len = nums.length
  const dp: number[] = [nums[0], Math.max(nums[0], nums[1])]
  for (let i = 2; i < len; i++) {
    dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
  }
  return dp[len-1]
}

// 动态规划优化
function rob(nums: number[]): number {
  const len = nums.length
  let [prev, next] = [0, nums[0]]
  for (let i = 2; i <= len; i++) {
    [prev, next] = [next, Math.max(next, prev + nums[i-1])]
  }

  return next
}

单词拆分

地址(opens new window)

// 回溯算法，暴力破解，超出时间限制
function wordBreak(s: string, wordDict: string[]): boolean {
  if (!s) {
    return true
  }

  for (let i = 0, len = wordDict.length; i < len; i++) {
    if (s.startsWith(wordDict[i])) {
      if(wordBreak(s.slice(wordDict[i].length), wordDict)) {
        return true
      }
    }
  }

  return false
}

// 回溯+记忆化
function wordBreak(s: string, wordDict: string[]): boolean {
  const len = s.length
  const memory: boolean[] = Array(len)

  const cascader = (start: number = 0) => {
    if (start >= len) {
      return true
    }

    if (memory[start] !== undefined) {
      return memory[start]
    }

    for (let i = 0, len = wordDict.length; i < len; i++) {
      if (s.startsWith(wordDict[i], start)) {
        if (cascader(start + wordDict[i].length)) {
          memory[start] = true
          return true
        }
      }
    }

    memory[start] = false
    return false
  }

  return cascader()
}

动态规划

// dp[j] 为 true，[j, i] 出现在字典里，那么dp[i]为true
function wordBreak(s: string, wordDict: string[]): boolean {
  const len = s.length
  const dp: boolean[] = Array(len + 1).fill(false)
  dp[0] = true

  for (let i = 1; i <= len; i++) {
    for (let j = 0, wLen = wordDict.length; j < wLen; j++) {
      let jLen = wordDict[j].length
      if (i >= jLen && s.startsWith(wordDict[j], i - jLen) && dp[i-jLen]) {
        dp[i] = true
      }
    }
  }

  return dp[len]
}

完全平方数

地址(opens new window)

// dp[j] = Math.min(dp[j], dp[j-num]+1)
function numSquares(n: number): number {
  // 最小开根号值
  const sqrtNum = Math.floor(Math.sqrt(n))
  const value: number[] = []
  for (let i = 1; i <= sqrtNum; i++) {
    value.push(i ** 2)
  }

  const dp: number[] = Array(n + 1).fill(Infinity)
  dp[0] = 0

  for (const num of value) {
    for (let j = num; j <= n; j++) {
      dp[j] = Math.min(dp[j-num] + 1, dp[j])
    }
  }

  return dp[n]
}

// dp[i] = Math.min(dp[i], dp[i - j * j] + 1)
function numSquares(n: number): number {
  const dp: number[] = Array(n+1).fill(Infinity)
  dp[0] = 0
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i - j * j] + 1, dp[i])
    }
  }

  return dp[n]
}

组合总和 Ⅳ

地址(opens new window)

// 排列
// dp[i] += dp[i - nums[j]]
function combinationSum4(nums: number[], target: number): number {
  const dp: number[] = Array(target + 1).fill(0)
  dp[0] = 1

  for (let i = 0; i <= target; i++) {
    for (const num of nums) {
      if (i >= num) {
        dp[i] += dp[i-num]
      }
    }
  }

  return dp[target]
}

零钱兑换 II

地址(opens new window)

// 组合
// dp[j] += dp[j-coins[i]]
function change(amount: number, coins: number[]): number {
  const dp: number[] = Array(amount + 1).fill(0)
  // 表示背包重量为0时只有1种
  dp[0] = 1

  for (let i = 0, len = coins.length; i < len; i++) {
    for (let j = coins[i]; j <= amount; j++) {
      dp[j] += dp[j-coins[i]]
    }
  }

  return dp[amount]
}

// for of
function change(amount: number, coins: number[]): number {
  const dp: number[] = Array(amount + 1).fill(0)
  dp[0] = 1

  for (const coin of coins) {
    for (let j = coin; j <= amount; j++) {
      dp[j] += dp[j-coin]
    }
  }

  return dp[amount]
}

目标和

地址(opens new window)

/*
 * 分成两堆 m 和 n
 * m + n = sum
 * m - n = target
 * 因此 2m = sum + target -> m = (sum + target) / 2
 * 其实可以拆除其中有多少个值之和等于m，可以使用回溯算法
 */

function findTargetSumWays(nums: number[], target: number): number {
  const sum = nums.reduce((p, n) => p + n, 0)
  const addSum = sum + target
  if (addSum % 2 || target > sum) {
    return 0
  }

  const m = addSum / 2
  const len = nums.length
  let result = 0
  let value = 0

  const cascader = (nums: number[], start: number = 0) => {
    if (value === m) {
      result++
    }

    if (start >= len) {
      return
    }

    for (let i = start; i < len; i++) {
      value += nums[i]
      cascader(nums, i + 1)
      value -= nums[i]
    }
  }

  cascader(nums)

  return result
}

动态规划法

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

function findTargetSumWays(nums: number[], target: number): number {
  const sum = nums.reduce((p, n) => p + n, 0)
  const addSum = sum + target
  if (addSum % 2 || Math.abs(target) > sum) {
    return 0
  }

  const m = addSum / 2
  const len = nums.length
  const dp: number[] = Array(m + 1).fill(0)
  dp[0] = 1
  for (let i = 0; i < len; i++) {
    for (let j = m; j >= nums[i]; j--) {
      dp[j] += dp[j - nums[i]]
    }
  }

  return dp[m]
}

一和零

地址(opens new window)

// 其实就是算m个0和n个1时所能得的最大子数组
// dp[m][n] = Math.max(dp[m][n], dp[m-strs[i](0)][n-strs[i](1)] + 1)
function findMaxForm(strs: string[], m: number, n: number): number {
  const dp: number[][] = []
  for (let i = 0; i <= m; i++) {
    dp[i] = Array(n+1).fill(0)
  }

  for (let i = 0, len = strs.length; i < len; i++) {
    // 计算有多少个0和1
    const zeroLen = strs[i].match(/0/g)?.length || 0
    const oneLen = strs[i].length - zeroLen
    if (zeroLen > m || oneLen > n) {
      continue
    }

    for (let j = m; j >= zeroLen; j--) {
      for (let h = n; h >= oneLen; h--) {
        dp[j][h] = Math.max(dp[j][h], dp[j - zeroLen][h - oneLen] +1)
      }
    }
  }

  return dp[m][n]
}

最后一块石头的重量 II

地址(opens new window)

// 其实就是分成两堆石头
// dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i])
function lastStoneWeightII(stones: number[]): number {
  const dp: number[] = Array(100 * 30 / 2 + 1).fill(0)
  const sum = stones.reduce((prev, next) => prev + next, 0)
  const target = Math.floor(sum / 2)
  for (let i = 0, len = stones.length; i < len; i++) {
    for (let j = target; j >= stones[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i])
    }
  }

  // 一堆为sum - dp[target]，一堆为dp[target]
  return sum - 2 * dp[target]
}

分割等和子集

地址(opens new window)

// p[i][j] = Math.max(p[i-1][j], weight[i] + p[i-1][j-weight[i]])
function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((prev, next) => prev + next, 0)

  // 如果是奇数，那么肯定不可分
  if (sum % 2) {
    return false
  }

  const half = sum / 2
  const len = nums.length
  let sumArr: number[] = Array(half + 1).fill(0)
  const curArr: number[] = []
  for (let i = 0; i < len; i++) {

    // 如果当前值大于循环值，那么直接返回
    if (nums[i] > half) {
      return false
    }

    // 取一半值，然后分别类似背包问题填充
    for (let j = 0; j <= half; j++) {
      if (nums[i] > j) {
        curArr[j] = sumArr[j]
        continue
      }

      curArr[j] = Math.max(nums[i] + sumArr[j-nums[i]], sumArr[j])
    }

    sumArr = [...curArr]
  }

  // 查看最后的值是否完全填充
  return sumArr.pop() === half
};

function canPartition(nums: number[]): boolean {
    const sum = nums.reduce((s, num) => s + num, 0)

    // 奇数不可分
    if (sum % 2) {
        return false
    }

    const half = sum / 2
    const dp: number[] = Array(half + 1).fill(0)
    for (const num of nums) {
        for (let j = half; j >= 0; j--) {
            if (j >= num) {
                dp[j] = Math.max(dp[j], dp[j - num] + num)
            }

            if (dp[j] === half) {
                return true
            }
        }
    }

    return false
};

背包问题

// p[i][j] = Math.max(p[i-1][j], weight[i] + p[i-1][j-weight[i]])
// p[i-1][j] 代表不需要当前物品
// weight[i] + p[i-1][j-weight[i]] 表示需要当前物品
function testWeightBagProblem(value: number[][], weight: number): number {
  let arr: number[] = [0, ...Array(weight).fill(value[0][1])]
  let curArr: number[] = []
  for (let i = 1, len = value.length; i < len; i++) {
    for (let j = 0; j <= weight; j++) {
      if (value[i][0] > j) {
        curArr[j] = arr[j]
        continue
      }

      curArr[j] = Math.max(arr[j], value[i][1] + arr[j-value[i][0]])
    }

    arr = [...curArr]
  }

  return arr.pop()
}

不同的二叉搜索树 II

地址(opens new window)

// 采用了递归的方式生成
function generateTrees(n: number): Array<TreeNode | null> {
    const cascader = (start: number, end: number) => {
        if (start > end) {
            return [null]
        }

        if (start === end) {
            return [new TreeNode(start)]
        }

        let result: TreeNode[] = []

        for (let i = start; i <= end; i++) {
            const left = cascader(start, i - 1)
            const right = cascader(i + 1, end)
            for (let l = 0; l < left.length; l++) {
                for (let r = 0; r < right.length; r++) {
                    const root = new TreeNode(i)
                    root.left = left[l]
                    root.right = right[r]
                    result.push(root)
                }
            }
        }

        return result
    }

    return cascader(1, n)
};

不同的二叉搜索树

地址(opens new window)

// n = 1 1
// n = 2 2
// n = 3 5
// n = 4 14
// n = 5 42
/**
 * *  1    2   3    4   5  6
 * 1  1    0   0    0   0  0
 * 2  1    1   0    0   0  0
 * 3  2    1   2    0   0  0
 * 4  5    2   2    5   0  0
 * 5  14   5   4    5  14  0
 * 6  42   14  10   10 14  42
 */
// p[i] = p[j-1] * p[i-j]
// 例如p[5] 以3为树的根节点，左边有1,2，右边有3,4，然后其实就是dp[2] * dp[2]
function numTrees(n: number): number {
  const p: number[] = [1, 1, 2]

  for (let i = 3; i <= n; i++) {
    p[i] = 0
    for (let j = 1; j <= i; j++) {
      p[i] += p[j-1] * p[i-j]
    }
  }
  return p[n]
}

整数拆分

地址(opens new window)

// 2 = 1 + 1
// 3 = 1 + 2
// 4 = 2 + 2
// 5 = 2 + 3
// 6 = 3 + 3
// 7 = 3 + 2 + 2
// 8 = 3 + 3 + 2
// 9 = 3 + 3 + 3
// 10 = 3 + 3 + 2 + 2
// 11 = 3 + 3 + 3 + 2
function integerBreak(n: number): number {
  if (n <= 3) {
    return n - 1
  }

  // 计算3有多少个
  const threeNum = Math.floor(n / 3)

  // 正好整除
  if (threeNum * 3 === n) {
    return 3 ** threeNum
  }

  // 计算2有多少个
  const twoNum = Math.floor((n - threeNum * 3) / 2)

  // 正好整除2
  if (twoNum * 2 + threeNum * 3 === n) {
    return 2 ** twoNum * 3 ** threeNum
  }

  return 3 ** (threeNum - 1) * 4
}

// 优化
function integerBreak(n: number): number {
  let result = 1

  // 正好整除
  while (n > 4) {
    n -= 3
    result *= 3
  }

  return result * n
}

// 动态规划
// dp[i] = Math.max(dp[i], (i - j) * j, (i - j) * dp[j])
function integerBreak(n: number): number {
    const dp: number[] = [,1,1]

    for (let i = 2; i <= n; i++) {
        for (let j = 1; j < i - 1; j++) {
            dp[i] = Math.max(dp[i] || 1, (i - j) * j, (i - j) * dp[j])
        }
    }

    return dp[n]
}

不同路径 II

地址(opens new window)

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const m = obstacleGrid.length
  const n = obstacleGrid[0].length

  // 第一行判断步数
  // 判断之后是否都等于0
  obstacleGrid[0][0] = obstacleGrid[0][0] === 1 ? 0 : 1
  for (let i = 1; i < n; i++) {
    obstacleGrid[0][i] = obstacleGrid[0][i] === 1 || !obstacleGrid[0][i-1]  ? 0 : 1
  }

  // 从第二行起判断
  for (let i = 1; i < m; i++) {

    // 判断上一行元素已经该行第一个元素是否挡路
    obstacleGrid[i][0] = (obstacleGrid[i][0] === 1 || !obstacleGrid[i-1][0]) ? 0 : 1

    for (let j = 1; j < n; j++) {

      // 表示挡路了
      if (obstacleGrid[i][j] === 1) {
        obstacleGrid[i][j] = 0
        continue
      }

      obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
    }
  }

  return obstacleGrid[m-1][n-1]
}

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    // 判断第一个点是否有石头
    if (obstacleGrid[0][0] === 1) {
        return 0
    }

    const m = obstacleGrid[0].length
    const n = obstacleGrid.length
    obstacleGrid[0][0] = 1

    // 第一层遍历，查看有多少种方式
    for (let i = 1; i < m; i++) {
        if (obstacleGrid[0][i] === 1) {
            obstacleGrid[0][i] = 0
        } else {
            obstacleGrid[0][i] = obstacleGrid[0][i-1]
        }
    }

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (obstacleGrid[i][j] === 1) {
                obstacleGrid[i][j] = 0
            } else {
                obstacleGrid[i][j] = obstacleGrid[i-1][j] + (obstacleGrid[i][j-1] || 0)
            }
        }
    }
    return obstacleGrid[n-1][m-1]
};

不同路径

地址(opens new window)

// dp[i][j]表示第i * j所走的路径
// dp[i][j] = dp[i-1][j] + dp[i][j-1]
function uniquePaths(m: number, n: number): number {
    const dp : number[][] = []
    // 第一层
    for (let i = 0; i < m; i++) {
        if (!dp[0]) {
            dp[0] = []
        }
        dp[0][i] = 1
    }
    for (let i = 1; i < n; i++) {
        if (!dp[i]) {
            dp[i] = []
        }
        dp[i][0] = 1
    }

    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }

    return dp[n-1][m-1]
};

function uniquePaths(m: number, n: number): number {
  let prev: number[] = Array(n).fill(1)
  const cur: number[] = [...prev]

  // 上一个+前一个的总和
  for (let j = 1; j < m; j++) {
    for (let i = 1; i < n; i++) {
      cur[i] = prev[i] + cur[i-1]
    }

    prev = [...cur]
  }

  return cur[n-1]
}

// 优化
function uniquePaths(m: number, n: number): number {
  const cur: number[] = Array(n).fill(1)

  // 上一个+前一个的总和
  for (let j = 1; j < m; j++) {
    for (let i = 1; i < n; i++) {
      cur[i] += cur[i-1]
    }
  }

  return cur[n-1]
}

// 一共需要走m+n-2步，其中m-1步向下
// C m-1
// C m + n - 2
// C(m+n-2, m-1) = A(m+n-2,m-1)/(m-1)! = (m+n-2)!/(m-1)!(m+n-2-(m - 1))! = n * ... (m+n-2) / (m-1)!
function uniquePaths(m: number, n: number): number {
  let result = 1
  let i = 1
  let start = n
  const pathNum = m + n - 2
  while (start <= pathNum) {
    result *= start
    if (i < m) {
      result /= i
      i++
    }
    start++
  }

  while (i < m) {
    result /= i
    i++
  }

  return result
}

使用最小花费爬楼梯

地址(opens new window)

function minCostClimbingStairs(cost: number[]): number {
  // 存储爬到此楼梯所花费的最小步数
  let p: number[] = [cost[0], cost[1]]
  let len = cost.length

  for (let i = 2; i < len; i++) {
    // 1. 前两节楼梯+当前花费
    // 2. 前1节楼梯+当前花费
    p[i] = Math.min(p[i-2], p[i-1]) + cost[i]
  }

  return Math.min(p[len-1], p[len-2])
}

function minCostClimbingStairs(cost: number[]): number {
  // 存储爬到此楼梯所花费的最小步数
  let [prev, cur] = [cost[0], cost[1]]
  let len = cost.length

  for (let i = 2; i < len; i++) {
    // 1. 前两节楼梯+当前花费
    // 2. 前1节楼梯+当前花费
    [prev, cur] = [cur, Math.min(prev, cur) + cost[i]]
  }

  return Math.min(prev, cur)
}

爬楼梯

地址(opens new window)

function climbStairs(n: number): number {
  if (n <= 2) {
    return n
  }

  let result = 0
  let prev = 1
  let current = 2
  for (let i = 2; i < n; i++) {
    result = prev + current
    prev = current
    current = result
  }

  return result
}

// 另一种写法
function climbStairs(n: number): number {
    if (n <= 2) {
        return n
    }
    let prev = 1
    let cur = 2
    for (let i = 3; i <= n; i++) {
        [prev, cur] = [cur, cur + prev]
    }
    return cur
};

斐波那契数

地址(opens new window)

function fib(n: number): number {
  if (n === 0) {
    return 0
  }

  if (n === 1) {
    return 1
  }

  let result = 0
  let prev = 0
  let current = 1
  for (let i = 2; i <= n; i++) {
    result = prev + current
    prev = current
    current = result
  }

  return result
}

function fib(n: number): number {
    if (n <= 1) {
        return n
    }
    let prev = 0
    let cur = 1
    for (let i = 2; i <= n; i++) {
        [prev, cur] = [cur, cur + prev]
    }
    return cur
};

监控二叉树

地址(opens new window)

// 0 该节点无摄像头覆盖
// 1 该节点是摄像头
// 2 该节点被摄像头覆盖
function minCameraCover(root: TreeNode | null): number {
  if (!root) {
    return 0
  }
  let result = 0

  // 判断子元素需要需要
  const cascader = (root: TreeNode | null) => {
    // 不存在节点
    if (!root) {
      return 2
    }

    const left = cascader(root.left) // 左
    const right = cascader(root.right) // 右

    // 中
    if (left === 2 && right === 2) {
      return 0
    }

    if (left === 0 || right === 0) {
      result++
      return 1
    }

    if (left === 1 || right === 1) {
      return 2
    }
  }

  if(!cascader(root)) {
    ++result
  }
  return result
}

function minCameraCover(root: TreeNode | null): number {
    let result = 0
    const cascader = (root: TreeNode | null) => {
        if (!root) {
            return 0
        }

        if (!root.left && !root.right) {
            return -1
        }

        const left = cascader(root.left)
        const right = cascader(root.right)

        // 需要装
        if (left === -1 || right === -1) {
            result++
            return 1
        }

        // 不装
        if (left === 1 || right === 1) {
            return 0
        }

        return -1
    }

    if (cascader(root) === -1) {
        result++
    }

    return result
};

Tips: 创建二叉树

function createTree(arr: (number | null)[]) {
  const tree = new TreeNode(arr[0])
  const newArr: TreeNode[] = [tree]
  const len = arr.length
  let i = 1
  while (i < len) {
    const len1 = newArr.length
    for (let j = 0; j < len1; j++) {
      const node = newArr.shift()
      if (arr[i++] !== null) {
        node.left = new TreeNode(arr[i])
        newArr.push(node.left)
      }

      if (arr[i++] !== null) {
        node.right = new TreeNode(arr[i++])
        newArr.push(node.right)
      }
    }
  }
  return tree
}

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

地址(opens new window)

// 贪心算法
// 1. 收获利润的这一天并不是收获利润的最后一天，之后还继续收获利润
// 2. 前一天是收获利润区间的最后1天，今天要重新记录最小价格
// 3. 不做操作
function maxProfit(prices: number[], fee: number): number {
  const len = prices.length
  let result = 0
  let minPrice = prices[0]

  for (let i = 1; i < len; i++) {
    // 2. 买入
    if (prices[i] < minPrice) {
      minPrice = prices[i]
    }

    // 3. 保持不动
    if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
      continue
    }

    // 计算利润
    if (prices[i] > minPrice + fee) {
      result += prices[i] - minPrice - fee
      minPrice = prices[i] - fee // 1. 超过该费用的最少价格
    }
  }

  return result
}

// 动态规划
// 持有
// dp[i][0]
// 要么继续持有dp[i-1][0]
// 要么买入要么 dp[i-1][1] - prices[i]

// 不持有
// dp[i][1]
// 继续保持不持有 dp[i-1][1]
// 卖出 dp[i-1][0] + prices[i] - fee

function maxProfit(prices: number[], fee: number): number {
  const len = prices.length
  if (!len) {
    return 0
  }

  const dp: number[][] = [[-prices[0], 0]]
  for (let i = 1; i < len; i++) {
    dp[i] = []
    dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i])
    dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
  }
  return dp[len-1][1]
}

单调递增的数字

地址(opens new window)

function monotoneIncreasingDigits(n: number): number {
  const str = n.toString()
  const arr: number[] = [+str[0]]
  let current = str[0]

  for (let i = 1; i < str.length; i++) {
    if (current === '10') {
      arr.push(9)
      continue
    }

    // 如果后面大于前面的值
    if (+str[i] >= +current) {
      arr.push(+str[i])
      current = str[i]
      continue
    }

    // 如果后面的值小于前面的值
    let j = arr.length - 1
    arr[j] -= 1
    while (j > 0) {
      if (arr[j] >= arr[j-1]) {
        break
      }
      arr[j] = 9
      arr[j-1] -= 1
      j--
    }

    current = '10'
    arr.push(9)
  }

  return +arr.join('')
}

// 改进
function monotoneIncreasingDigits(n: number): number {
  const str = n.toString()
  const len = str.length
  const arr: number[] = []
  for (let i = 0; i < len; i++) {
    arr.push(+str[i])
  }

  for (let i = 1; i < len; i++) {
    // 如果后面大于前面的值
    if (arr[i] >= arr[i-1]) {
      continue
    }

    // 如果后面的值小于前面的值
    let j = i - 1
    arr[j] -= 1
    while (j > 0) {
      if (arr[j] >= arr[j-1]) {
        break
      }
      arr[j] = 9
      arr[j-1] -= 1
      j--
    }

    return +(arr.slice(0, i).join('') + '9'.repeat(len - i))
  }

  return n
}

// 优化2
function monotoneIncreasingDigits(n: number): number {
  const str = n.toString()
  const len = str.length
  const arr: number[] = [+str[0]]

  for (let i = 1; i < len; i++) {
    // 如果后面大于前面的值
    if (+str[i] >= arr[i-1]) {
      arr.push(+str[i])
      continue
    }

    // 如果后面的值小于前面的值
    let j = i - 1
    arr[j] -= 1
    while (j > 0) {
      if (arr[j] >= arr[j-1]) {
        break
      }
      arr[j-1] -= 1
      j--
    }

    return +(arr.slice(0, j+1).join('') + '9'.repeat(len - j - 1))
  }

  return n
}

function monotoneIncreasingDigits(n: number): number {
  const str = n.toString().split('').map(item => +item)
  const len = str.length
  let start = len
  for (let i = len - 1; i > 0; i--) {
    if (str[i-1] > str[i]) {
      start = i
      str[i-1]--
    }
  }

  return +(str.slice(0, start).join('') + '9'.repeat(len - start))
}

合并区间

地址(opens new window)

function merge(intervals: number[][]): number[][] {
  const len = intervals.length
  if (!len) {
    return []
  }

  const result: number[][] = []

  intervals.sort((prev, next) => prev[0] - next[0])
  let current: number[] = intervals[0]

  for (let i = 0; i < len; i++) {
    if (current[1] < intervals[i][0]) {
      result.push(current)
      current = intervals[i]
      continue
    }

    current[1] = Math.max(current[1], intervals[i][1])
  }

  result.push(current)
  return result
}

划分字母区间

地址(opens new window)

function partitionLabels(s: string): number[] {
  const len = s.length
  const result: number[] = []
  let start = 0
  let last = 0
  for (let i = 0; i < len; i++) {

    // 从第一个开始找，找到最后一个该字母出现的位置
    for (let j = start; j < len; j++) {
      if (s[j] === s[i]) {
        start = Math.max(start, j)
      }
    }

    if (start === i) {
      result.push(start + 1 - last)
      last = i + 1
    }
  }

  return result
}

function partitionLabels(s: string): number[] {
  const len = s.length
  const result: number[] = []
  let start = 0
  let last = -1
  let pos = {}
  for (let i = 0; i < len; i++) {
    pos[s[i]] = i
  }

  for (let i = 0; i < len; i++) {
    start = Math.max(start, pos[s[i]])

    if (i === start) {
      result.push(start - last)
      last = start
    }
  }

  return result
}

无重叠区间

地址(opens new window)

function eraseOverlapIntervals(intervals: number[][]): number {
  // 排序，从小到大，区间从大到小
  let result = 0
  if (!intervals.length) {
    return result
  }
  intervals.sort((prev, next) => prev[0] - next[0] || next[1] - prev[1])

  // 取排序后的第一个
  let current: number[] = intervals[0]
  for (let i = 1, len = intervals.length; i < len; i++) {
    // 当前元素和前一个元素比较
    if (intervals[i][0] < current[1]) {
      result++

      // 比较应该舍弃哪一个，有时候需要舍弃后面一个
      if (intervals[i][1] < current[1]) {
        current = intervals[i]
      }
      continue
    }
    current = intervals[i]
  }

  return result
}

function eraseOverlapIntervals(intervals: number[][]): number {
  if (!intervals.length) {
    return 0
  }

  // 记录非交叉区间的个数
  let result = 1
  const len = intervals.length

  // 排序，按右边界排
  intervals.sort((prev, next) => prev[1] - next[1])
  // 取最后一个边界
  let end = intervals[0][1]
  for (let i = 1; i < len; i++) {
    // 看看是否有交叉
    if (intervals[i][0] >= end) {
      end = intervals[i][1]
      result++
    }
  }

  return len - result
}

用最少数量的箭引爆气球

地址(opens new window)

// 整体思路是排序，然后合并数值是否是包含关系
function findMinArrowShots(points: number[][]): number {
  // 先排序
  points.sort((prev, next) => prev[0] - next[0] || prev[1] - next[1])
  const len = points.length
  let result = 0
  let max = -Infinity

  for (let i = 0; i < len; i++) {
    // 取第一个的start
    if (points[i][0] > max) {
      result++
      max = points[i][1]
      continue
    }

    if (points[i][1] < max) {
      max = points[i][1]
      continue
    }
  }

  return result
}

function findMinArrowShots(points: number[][]): number {
    points.sort(([prevS, prevE], [nextS, nextE]) => prevS - nextS || prevE - nextE)
    let last: number[] = points[0]
    let result = 1

    for (let i = 1; i < points.length; i++) {
        // 相等的时候
        if (points[i][0] === last[0]) {
            continue
        }

        // 大于的时候
        if (points[i][0] > last[1]) {
            last = points[i]
            result++
            continue
        }

        // 有重叠的时候
        last[0] = points[i][0]
        last[1] = Math.min(last[1], points[i][1])
    }

    return result
};

根据身高重建队列

地址(opens new window)

function reconstructQueue(people: number[][]): number[][] {
  people.sort((prev, next) => prev[1] - next[1] || prev[0] - next[0])
  const len = people.length
  const result: number[][] = [people[0]]

  for (let i = 1; i < len; i++) {
    let j = 0
    let num = 0

    // 数值大的尽可能往后放
    while (j < len && num <= people[i][1]) {
      if (!result[j]) {
        break
      }

      if (result[j][0] >= people[i][0]) {
        num++

        if (num > people[i][1]) {
          break
        }
      }
      j++
    }

    result.splice(j, 0, people[i])
  }

  return result
}

function reconstructQueue(people: number[][]): number[][] {
  const len = people.length

  // 身高从大到小，属性值从小到大
  people.sort((prev, next) => next[0] - prev[0] || prev[1] - next[1])
  const result: number[][] = []

  for (let i = 0; i < len; i++) {
    result.splice(people[i][1], 0, people[i])
  }

  return result
}

柠檬水找零

地址(opens new window)

function lemonadeChange(bills: number[]): boolean {
  const len = bills.length
  let fiveDollor = 0
  let tenDollor = 0
  for (let i = 0; i < len; i++) {
    if (bills[i] === 5) {
      fiveDollor++
      continue
    }

    if (bills[i] === 10) {
      if (!fiveDollor) {
        return false
      }
      fiveDollor--
      tenDollor++
      continue
    }

    if (tenDollor > 0 && fiveDollor > 0) {
      tenDollor--
      fiveDollor--
      continue
    }

    if (fiveDollor >= 3) {
      fiveDollor -= 3
      continue
    }

    return false
  }
  return true
};

分发糖果

地址(opens new window)

function candy(ratings: number[]): number {
  let sum = 0
  let len = ratings.length
  let result = [1] // 保存糖果数

  for (let i = 1; i < len; i++) {
    if (ratings[i] > ratings[i-1]) {
      result[i] = result[i-1] + 1
      continue
    }

    let j = i

    result[i] = 1
    while (j - 1 >= 0 && ratings[j] < ratings[j-1] && result[j-1] < result[j] + 1) {
      j--
      result[j] += 1
    }

  }

  for (const i of result) {
    sum += i
  }

  return sum
}

// 可修改为
function candy(ratings: number[]): number {
  let sum = 1
  let len = ratings.length
  let result = [1] // 保存糖果数

  for (let i = 1; i < len; i++) {
    if (ratings[i] > ratings[i-1]) {
      result[i] = result[i-1] + 1
    } else {
      let j = i

      result[i] = 1
      while (j - 1 >= 0 && ratings[j] < ratings[j-1] && result[j-1] < result[j] + 1) {
        j--
        result[j] += 1
        ++sum
      }
    }

    sum += result[i]
  }

  return sum
}

function candy(ratings: number[]): number {
  let sum = 0
  let len = ratings.length
  let result = [...new Array(len).fill(1)] // 保存糖果数

  // 从前往后
  for (let i = 1; i < len; i++) {
    if (ratings[i] > ratings[i-1]) {
      result[i] += result[i-1]
    }
  }

  // 从后往前
  for (let i = len - 1; i >= 0; i--) {
    if (ratings[i] > ratings[i+1]) {
      result[i] = Math.max(result[i], result[i+1] + 1)
    }
  }

  for (const i of result) {
    sum += i
  }

  return sum
}

加油站

地址(opens new window)

function canCompleteCircuit(gas: number[], cost: number[]): number {
    let sum = 0
    let curSum = 0
    let start = 0
    for (let i = 0; i < gas.length; i++) {
        sum += gas[i] - cost[i]
        curSum += gas[i] - cost[i]

        // 布局大于0
        if (curSum < 0) {
            start = i + 1
            curSum = 0
        }
    }
    if (sum < 0) {
        return -1
    }

    return start
};

function canCompleteCircuit(gas: number[], cost: number[]): number {
  const len = gas.length
  let result = 0
  let sum = 0
  let subSum = 0

  for (let i = 0; i < len; i++) {
    let val = gas[i] - cost[i]
    sum += val

    if (subSum + val >= 0) {
      subSum += val
      continue
    }

    subSum = val
    result = val < 0 ? i + 1 : i
  }

  if (sum < 0) {
    return -1
  }

  return result
}

K 次取反后最大化的数组和

地址(opens new window)

function largestSumAfterKNegations(nums: number[], k: number): number {
  let sum = 0
  let min = Infinity

  // 先排序
  nums.sort((prev, next) => {
    return prev - next
  })

  for (let i = 0; i < nums.length; i++) {
    min = Math.min(min, Math.abs(nums[i]))

    if (k === 0 || nums[i] >= 0) {
      sum += nums[i]
      continue
    }

    sum -= nums[i]
    k--
  }

  if (k % 2 === 1) {
    sum -= 2 * Math.abs(min)
  }
  return sum
}

function largestSumAfterKNegations(nums: number[], k: number): number {
  // 先排序
  nums.sort((prev, next) => {
    return Math.abs(prev) - Math.abs(next)
  })

  // 反转负数
  for (let i = nums.length - 1; i >= 0; i--) {
    if (nums[i] < 0 && k > 0) {
      nums[i] = -nums[i]
      k--
    }
  }

  // 反转最小值
  if (k % 2 === 1) {
    nums[0] *= -1
  }

  let sum = 0
  for (const i of nums) {
    sum += i
  }

  return sum
}

跳跃游戏 II

地址(opens new window)

function jump(nums: number[]): number {
  const len = nums.length
  let i = 0
  let n = 0

  while (i < len - 1) {

    let val = 0 // 积累步数
    n++
    if (i + nums[i] >= len - 1) {
      return n
    }

    // 尽可能的多跳
    for (let j = i + 1, end = i + nums[i] + 1; j < end; j++) {
      if (j + nums[j] > val) {
        i = j
        val = j + nums[j]
      }
    }
  }

  return n
};

function jump(nums: number[]): number {
  const len = nums.length
  if (len === 1) {
    return 0
  }
  let n = 0
  let cur = 0
  let next = 0
  for (let i = 0; i < len - 1; i++) {

    // 下一次跳跃的步数
    next = Math.max(nums[i] + i, next)
    if (i === cur) {
      cur = next
      n++
    }
  }

  return n
}

跳跃游戏

地址(opens new window)

function canJump(nums: number[]): boolean {
  const len = nums.length
  let i = 0

  while (i < len - 1) {
    let val = 0 // 积累步数

    // 尽可能的多跳
    for (let j = i + 1, end = i + nums[i] + 1; j < end; j++) {
      if (j + nums[j] > val) {
        i = j
        val = j + nums[j]
      }
    }

    if (!val) {
      return false
    }
  }

  return true
}

function canJump(nums: number[]): boolean {
  const len = nums.length
  if (len === 1) {
    return true
  }

  let cover = 0
  for (let i = 0; i <= cover; i++) {
    cover = Math.max(cover, i + nums[i])
    if (cover >= len - 1) {
      return true
    }
  }

  return false
}

买卖股票的最佳时机 II

地址(opens new window)

// 贪心算法
function maxProfit(prices: number[]): number {
  let sum = 0
  let prev = Infinity

  // 后面的大值减去前面的小值
  for (let i = 0, len = prices.length; i < len; i++) {
    if (prices[i] - prev > 0) {
      sum += prices[i] - prev
    }
    prev = prices[i]
  }

  return sum
}

动态规划1

// 动态规划
// p[i]代表第i天卖出时的最大利润
// 1. 第i天的股票卖出最大 prices[i] - prices[i-1] + dp[i-1]
// 2. 第i天的股票不买最大 p[i-1]
function maxProfit(prices: number[]): number {
  const len = prices.length
  if (len <= 1) {
    return 0
  }
  const dp: number[] = Array(len).fill(0)

  for (let i = 1; i < len; i++) {
    dp[i] = Math.max(dp[i-1], prices[i] - prices[i-1] + dp[i-1])
  }

  return dp[len-1]
}

动态规划2

// dp[i][0] 表示第i天持有股票所得最多现金
// i-1持有股票，所得现金就是昨天持有股票所得现金 dp[i-1][0]
// 第i天买入股票，所得现金前一天卖出 dp[i-1][1]-prices[i]

// dp[i][1] 表示第i天不持有股票所得最多现金
// i-1天不持有 dp[i-1][1]
// 第i天卖出 prices[i] + dp[i-1][0]

// dp[0][0] = -prices[0]
// dp[0][1] = 0

function maxProfit(prices: number[]): number {
  const len = prices.length
  const dp: number[][] = Array(len).fill([])

  // 持有
  dp[0][0] = -prices[0]

  // 不持有
  dp[0][1] = 0

  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i])
    dp[i][1] = Math.max(dp[i-1][1], prices[i] + dp[i-1][0])
  }

  return dp[len-1][1]
}

最大子数组和

地址(opens new window)

贪心

function maxSubArray(nums: number[]): number {
  const len = nums.length
  let n = -Infinity
  let submax = -Infinity

  for (let i = 0; i < len; i++) {
    // 如果之前之和小于当前值，那么果断放弃之前之和
    submax = submax + nums[i] > nums[i] ? submax + nums[i] : nums[i]

    if (submax > n) {
      n = submax
    }
  }

  return n
}

动态规划

// dp[i]表示连续子数组的最大和
// 1. dp[i-1] + nums[i]为最大值
// 2. nums[i]为最大值
function maxSubArray(nums: number[]): number {
  const len = nums.length
  const dp: number[] = Array(len).fill(0)
  let max = nums[0]
  dp[0] = nums[0]
  for (let i = 1; i < len; i++) {
    dp[i] = Math.max(nums[i], dp[i-1] + nums[i])
    if (dp[i] > max) {
      max = dp[i]
    }
  }

  return max
}

摆动序列

地址(opens new window)

function wiggleMaxLength(nums: number[]): number {
  const len = nums.length
  if (len <= 1) {
    return len
  }

  let last = nums[0]
  let n = 1
  let isOverZero: boolean | undefined = undefined

  for (let i = 1; i < len; i++) {
    // 1. 相等的情况
    if (nums[i] === last) {
      continue
    }

    // 2. nums[i]大于last
    if (nums[i] > last) {

      // 如果isOverZero为undefined或者true
      if (isOverZero !== false) {
        n++
        isOverZero = false // 接下来需要小于0的
      }
      last = nums[i]
      continue
    }

    // 3. nums[i]小于last
    if (!isOverZero) {
      n++
      isOverZero = true // 接下来需要大于0的
    }
    last = nums[i]
  }

  return n
}

function wiggleMaxLength(nums: number[]): number {
  const len = nums.length
  if (len <= 1) {
    return len
  }

  let curDiff = 0 // 当前差值
  let preDiff = 0 // 前差值
  let n = 1

  for (let i = 1; i < len; i++) {
    curDiff = nums[i] - nums[i-1]

    // 不计算单调递增或单调递减的值
    if (curDiff > 0 && preDiff <= 0 || (preDiff >= 0 && curDiff < 0)) {
      n++
      preDiff = curDiff
    }
  }

  return n
}

分发饼干

地址(opens new window)

function findContentChildren(g: number[], s: number[]): number {
  g.sort((prev, next) => prev - next)
  s.sort((prev, next) => prev - next)
  let n = 0
  for (let i = 0; i < s.length; i++) {
    // 满足胃口最小的
    if (s[i] >= g[n]) {
      n++
    }
  }

  return n
}

解数独

地址(opens new window)

function solveSudoku(board: string[][]): void {
  const checkSudo = (depth: number, col: number, value: number, board: string[][]) => {

    // 横项、纵向是否有值
    for (let i = 0; i < 9; i++) {
      if (board[depth][i] === `${value}` || board[i][col] === `${value}`) {
        return false
      }
    }

    // 检查9宫格是否有相同的值
    let start = Math.floor(col / 3) * 3
    let depthStart = Math.floor(depth / 3) * 3
    for (let i = depthStart; i < depthStart + 3; i++) {
      for (let j = start; j < start + 3; j++) {
        if (board[i][j] === `${value}`) {
          return false
        }
      }
    }

    return true
  }
  const back = (board: string[][]) => {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] !== '.') {
          continue
        }

        for (let m = 1; m < 10; m++) {
          if (checkSudo(i, j, m, board)) {
            board[i][j] = `${m}`
            if (back(board)) {
              return true
            }
            board[i][j] = '.'
          }
        }

        return false
      }
    }

    return true
  }
  back(board)
}

N 皇后

地址(opens new window)

function solveNQueens(n: number): string[][] {
  const result: string[][] = []
  const path: string[] = []
  const used: number[][] = [...Array.from({ length: n }, () => [...Array.from({ length: n }, () => 0)])]

  const back = (n: number, depth = 0) => {
    if (path.length === n) {
      result.push(path.slice())
      return
    }

    for (let i = 0; i < n; i++) {

      // 绝对值小于2
      if (!used[depth][i]) {

        // 引用次数
        for (let m = depth + 1, j = i + 1, h = i - 1; m < n; m++) {
          j < n && (used[m][j++] += 1)
          h >= 0 && (used[m][h--] += 1)
          used[m][i] += 1
        }

        path.push('.'.repeat(i) + 'Q' + '.'.repeat(n - i - 1))

        back(n, depth + 1)

        // 去除引用次数
        for (let m = depth + 1, j = i + 1, h = i - 1; m < n; m++) {
          j < n && (used[m][j++] -= 1)
          h >= 0 && (used[m][h--] -= 1)
          used[m][i] -= 1
        }

        path.pop()
      }
    }
  }
  back(n)
  return result
}

function solveNQueens(n: number): string[][] {
  const result: string[][] = []
  const path: string[][] = [...Array.from({ length: n }, () => Array.from({ length: n }, () => '.'))]

  const checkQueen = (col: number, row: number, path: string[][]) => {
    for (let i = col - 1, m = row + 1, j = row - 1; i >= 0; i--) {
      // 检查45°有无Q
      if (m < n) {
        if (path[i][m++] === 'Q') {
          return false
        }
      }

      // 检查135°有无Q
      if (j >= 0) {
        if (path[i][j--] === 'Q') {
          return false
        }
      }

      // 检查纵列有没有Q
      if (path[i][row] === 'Q') {
        return false
      }
    }

    return true
  }

  const back = (n: number, depth = 0) => {
    if (depth >= n) {
      result.push(path.map(item => item.join('')))
      return
    }

    for (let i = 0; i < n; i++) {

      // 绝对值小于2
      if (checkQueen(depth, i, path)) {
        path[depth][i] = 'Q'
        back(n, depth + 1)
        path[depth][i] = '.'
      }
    }
  }
  back(n)
  return result
}

重新安排行程

地址(opens new window)

function findItinerary(tickets: string[][]): string[] {
  let result: string[] = ['JFK']
  const len = tickets.length
  const targets = {}
  for (const [source, target] of tickets.sort((prev, next) => prev[1].localeCompare(next[1]))) {
    if (!targets[source]) {
      targets[source] = {}
    }
    if (!targets[source][target]) {
      targets[source][target] = 0
    }
    targets[source][target] += 1
  }
  const back = (tickets: string[][], last = 'JFK') => {
    if (result.length === len + 1) {
      return true
    }

    for (const key in targets[last]) {
      if (targets[last][key]) {
        result.push(key)
        targets[last][key]--
        if (back(tickets, key)) {
          return true
        }
        result.pop()
        targets[last][key]++
      }
    }
  }
  back(tickets)
  return result
}

function findItinerary(tickets: string[][]): string[] {
  let result: string[] = []
  const path: string[] = ['JFK']
  const len = tickets.length
  const used = []

  const back = (tickets: string[][]) => {
    if (path.length === len + 1) {
      result = [...path]

      // 如果有数据了就返回
      return true
    }

    for (let i = 0; i < len; i++) {
      if (path[path.length - 1] === tickets[i][0] && !used[i]) {
        path.push(tickets[i][1])
        used[i] = true
        if (back(tickets)) {
          return true
        }
        path.pop()
        used[i] = false
      }
    }
  }

  // 注意排序
  back(tickets.sort((prev, next) => prev[1].localeCompare(next[1])))
  return result
}

全排列 II

地址(opens new window)

function permuteUnique(nums: number[]): number[][] {
  const result: number[][] = []
  const path = []
  const len = nums.length
  const set = new Set()

  const back = (nums: number[]) => {
    if (path.length >= len) {
      result.push(path.slice())
      return
    }

    // 一层一个值
    const set1 = new Set()
    for (let i = 0; i < nums.length; i++) {
      if (set.has(i) || set1.has(nums[i])) {
        continue
      }
      path.push(nums[i])
      set1.add(nums[i])
      set.add(i)
      back(nums)
      path.pop()
      set.delete(i)
    }
  }
  back(nums)
  return result
}

// 使用数组的效率更高
function permuteUnique(nums: number[]): number[][] {
  const result: number[][] = []
  const path = []
  const len = nums.length
  const used = []

  const back = (nums: number[]) => {
    if (path.length >= len) {
      result.push(path.slice())
      return
    }

    // 一层一个值
    const set1 = new Set()
    for (let i = 0; i < nums.length; i++) {
      if (used[i] || set1.has(nums[i])) {
        continue
      }
      path.push(nums[i])
      set1.add(nums[i])
      used[i] = true
      back(nums)
      path.pop()
      used[i] = false
    }
  }
  back(nums)
  return result
}

全排列

地址(opens new window)

function permute(nums: number[]): number[][] {
  const result: number[][] = []
  const path = []
  const len = nums.length

  const back = (nums: number[]) => {
    if (path.length >= len) {
      result.push(path.slice())
      return
    }

    for (let i = 0; i < nums.length; i++) {
      path.push(nums[i])
      back([...nums.slice(0, i), ...nums.slice(i + 1)])
      path.pop()
    }
  }
  back(nums)
  return result
}

function permute(nums: number[]): number[][] {
  const result: number[][] = []
  const path = []
  const len = nums.length
  const set = new Set()

  const back = (nums: number[]) => {
    if (path.length >= len) {
      result.push(path.slice())
      return
    }

    for (let i = 0; i < nums.length; i++) {
      // 判断元素是否已经选取
      if (set.has(nums[i])) {
        continue
      }
      path.push(nums[i])
      // 这里也可以加入i，不一定得nums[i]
      set.add(nums[i])
      back(nums)
      path.pop()
      set.delete(nums[i])
    }
  }
  back(nums)
  return result
}

递增子序列

地址(opens new window)

function findSubsequences(nums: number[]): number[][] {
  const result: number[][] = []
  const path = []
  const len = nums.length

  const back = (nums: number[], start: number = 0) => {
    if (path.length > 1) {
      result.push(path.slice())
    }

    if (start >= len) {
      return
    }

    // 不允许同一层使用相同元素
    const set = new Set()
    for (let i = start; i < len; i++) {
      if (path.length && nums[i] < path[path.length - 1] || set.has(nums[i])) {
        continue
      }
      set.add(nums[i])
      path.push(nums[i])
      back(nums, i + 1)
      path.pop()
    }

  }
  back(nums)
  return result
}

子集 II

地址(opens new window)

function subsetsWithDup(nums: number[]): number[][] {
  const result: number[][] = []
  const path = []
  const len = nums.length

  const back = (nums: number[], start: number = 0) => {
    result.push([...path])

    if (start >= len) {
      return
    }

    for (let i = start; i < len; i++) {
      if (i > start && nums[i] === nums[i-1]) {
        continue
      }
      path.push(nums[i])
      back(nums, i + 1)
      path.pop()
    }
  }

  // 注意排序
  back(nums.sort((a, b) => a - b))
  return result
}

子集

地址(opens new window)

function subsets(nums: number[]): number[][] {
  const result: number[][] = []
  const path = []
  const len = nums.length

  const back = (nums: number[], start: number = 0) => {
    result.push([...path])

    if (start >= len) {
      return
    }

    for (let i = start; i < len; i++) {
      path.push(nums[i])
      back(nums, i + 1)
      path.pop()
    }
  }
  back(nums)
  return result
}

复原 IP 地址

地址(opens new window)

function restoreIpAddresses(s: string): string[] {
  const len = s.length
  if (len < 4 || len > 12) {
    return []
  }
  const result: string[] = []
  const path: string[] = []

  const back = (s: string, start: number = 0) => {
    if (path.length >= 4) {
      start >= len && result.push(path.join('.'))
      return
    }

    for (let i = start; i < len; i++) {
      let val = s.slice(start, i + 1)

      // 第一个为0
      if (i > start && s[start] === '0') {
        break
      }

      if (i - start > 3 || +val > 255) {
        break
      }
      path.push(val)
      back(s, i + 1)
      path.pop()
    }
  }
  back(s)
  return result
}

function restoreIpAddresses(s: string): string[] {
  const len = s.length
  if (len < 4 || len > 12) {
    return []
  }
  const result: string[] = []
  let str = ''

  const back = (s: string, start: number = 0, dotNum = 0) => {
    // 有四个点了
    if (dotNum >= 4) {

      // 判断后三个字符串长度
      if (start >= len) {
        result.push(str.slice(0, -1));
      }
      return
    }

    for (let i = start, len1 = Math.min(start + 3, len); i < len1; i++) {

      // 如果截取的值大于255
      let value = s.slice(start, i + 1)
      if (+value > 255) {
        return
      }

      str += value + '.'
      back(s, i + 1, ++dotNum)
      dotNum--
      str = str.slice(0, start - i - 2)

      // 如果第一个为'0'
      if (s[start] === '0') {
        return
      }
    }
  }
  back(s, 0, 0)
  return result
}

分割回文串

地址(opens new window)

function partition(s: string): string[][] {
  const result: string[][] = []
  const path: string[] = []
  const len = s.length

  const back = (s: string, start: number = 0) => {
    if (start >= len) {
      result.push([...path])
      return
    }

    for (let i = start; i < len; i++) {
      // 判断是否是回文，然后推入
      let j = i
      let str = ''
      while (j >= start && s[j] === s[i-j+start]) {
        str += s[j--]
      }

      if (j === start - 1) {
        path.push(str)
        back(s, start + str.length)
        path.pop()
      }
    }
  }
  back(s)
  return result
}

function partition(s: string): string[][] {
    const isP = (s: string) => {
        let start = 0
        let end = s.length - 1
        while (start < end) {
            if (s[start++] !== s[end--]) {
                return false
            }
        }
        return true
    }

    const result: string[][] = []
    const content: string[] = []

    const cascader = (s: string, start = 0) => {
        if (start >= s.length) {
            result.push([...content])
            return
        }

        let str = ''
        for (let i = start; i < s.length; i++) {
            str += s[i]
            if (!isP(str)) {
                continue
            }

            content.push(str)
            cascader(s, i + 1)
            content.pop()
        }
    }

    cascader(s)

    return result
};

组合总和 II

地址(opens new window)

function combinationSum2(candidates: number[], target: number): number[][] {
  const result: number[][] = [] // 存放结果
  const path: number[] = [] // 存放单一路径
  const len = candidates.length

  const back = (candidates: number[], target: number, start: number = 0) => {

    // 终止条件
    if (target <= 0) {
      if (!target) {
        result.push([...path])
      }
      return
    }

    for (let i = start; i < len; i++) {
      if (i > start && candidates[i] === candidates[i - 1]) {
        continue
      }
      path.push(candidates[i])
      back(candidates, target - candidates[i], i + 1)
      path.pop()
    }
  }

  back(candidates.sort((prev, next) => prev - next), target)

  return result
};

组合总和

地址(opens new window)

function combinationSum(candidates: number[], target: number): number[][] {
  const result: number[][] = []
  const path: number[] = []
  const len = candidates.length

  const back = (candidates: number[], target: number, start: number = 0) => {
    if (target <= 0) {
      if (!target) {
        result.push([...path])
      }
      return
    }

    for (let i = start; i < len; i++) {
      path.push(candidates[i])
      back(candidates, target - candidates[i], i)
      path.pop()
    }
  }

  back(candidates, target)
  return result
};

优化：

function combinationSum(candidates: number[], target: number): number[][] {
  const result: number[][] = []
  const path: number[] = []
  const len = candidates.length

  const back = (candidates: number[], target: number, start: number = 0) => {
    if (target <= 0) {
      if (!target) {
        result.push([...path])
      }
      return
    }

    if (candidates[start] > target) {
      return
    }

    for (let i = start; i < len; i++) {
      path.push(candidates[i])
      back(candidates, target - candidates[i], i)
      path.pop()
    }
  }
  back(candidates.sort((prev, next) => prev - next), target)

  return result
}

电话号码的字母组合

地址(opens new window)

function letterCombinations(digits: string): string[] {
  if (!digits) {
    return []
  }

  const key = {
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz'
  }

  const result: string[] = []
  let str = ''
  const len = digits.length
  const back = (digits: string, start: number) => {
    if (start === len) {
      result.push(str)
      return
    }

    for (let i = 0; i < key[digits[start]].length; i++) {
      str += key[digits[start]][i]
      back(digits, start + 1)
      str = str.slice(0, -1)
    }
  }

  back(digits, 0)
  return result
}

function letterCombinations(digits: string): string[] {
    if (!digits) {
        return []
    }

    const obj = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz'
    }

    const arr: string[][] = []
    const result: string[] = []
    const len = digits.length

    for (let i = 0; i < len; i++) {
        arr.push(obj[digits[i]])
    }

    const cascader = (arr: string[][], start = 0, str = '') => {
        if (start >= len) {
            result.push(str)
            return
        }

        for (let i = 0; i < arr[start].length; i++) {
            cascader(arr, start + 1, str + arr[start][i])
        }
    }

    cascader(arr)
    return result
};

组合总和 III

地址(opens new window)

// 优化
function combinationSum3(k: number, n: number): number[][] {
  if (n > 45) {
    return []
  }
  const result: number[][] = [] // 存放结果
  const path: number[] = [] // 存放单一路径
  const minSize = Math.min(10, n)
  const back = (n: number, k: number, start: number) => {
    if (n < start) {
      return
    }

    // 终止条件
    if (path.length === k - 1) {
      if (n < 10) { result.push([...path, n]) }
      return
    }

    for (let i = start; i < minSize; i++) {
      path.push(i)
      back(n - i, k, i + 1)
      path.pop()
    }
  }
  back(n, k, 1)

  return result
}

function combinationSum3(k: number, n: number): number[][] {
    // 1. 如果n大于1-10之和
    if (n > 45) {
        return []
    }

    const result: number[][] = []
    const content: number[] = []
    let min = Math.min(n, 9)

    const cascader = (n: number, start: number = 1) => {
        if (n === 0 && content.length === k) {
            result.push([...content])
            return
        }

        if (start > min || n < 0) {
            return
        }

        for (let i = start; i <= min - (k - content.length) + 1; i++) {
            content.push(i)
            cascader(n - i, i + 1)
            content.pop()
        }
    }

    cascader(n)
    return result
};

function combinationSum3(k: number, n: number): number[][] {
  const result: number[][] = [] // 存放结果
  const path: number[] = [] // 存放单一路径
  const back = (n: number, k: number, start: number) => {
    if (n < 0) {
      return
    }

    // 终止条件
    if (path.length === k) {
      if (!n) {
        result.push([...path])
      }
      return
    }

    for (let i = start; i < 10; i++) {
      path.push(i)
      back(n - i, k, i + 1)
      path.pop()
    }
  }
  back(n, k, 1)
  return result
}

function combinationSum3(k: number, n: number): number[][] {
  if (n > 45) {
    return []
  }
  const result: number[][] = [] // 存放结果
  const path: number[] = [] // 存放单一路径

  const back = (n: number, k: number, left: number) => {

    if (left >= n) {
      return
    }

    // 终止条件
    if (path.length === k - 1 && n < 10) {
      result.push([...path, n])
      return
    }

    while (left < n && left < 10) {
      path.push(++left)
      back(n - left, k, left)
      path.pop()
    }
  }
  back(n, k, 0)
  return result
};

组合

地址(opens new window)

// 优化
function combine(n: number, k: number): number[][] {
  const result: number[][] = [] // 存放结果
  const path: number[] = [] // 存放单一路径

  const back = (n: number, k: number, start: number) => {

    // 终止条件
    if (path.length === k) {
      result.push([...path])
      return
    }

    // 例如n = 4 k = 2，第一层结尾为3，因此需要加1
    for (let i = start; i <= n - (k - path.length) + 1; i++) {
      path.push(i);
      back(n, k, i + 1)
      path.pop()
    }
  }
  back(n, k, 1)
  return result
}

function combine(n: number, k: number): number[][] {
  const result: number[][] = [] // 存放结果
  const path: number[] = [] // 存放单一路径

  const back = (n: number, k: number, start: number) => {

    // 终止条件
    if (path.length === k) {
      result.push([...path])
      return
    }

    for (let i = start; i <= n; i++) {
      path.push(i);
      back(n, k, i + 1)
      path.pop()
    }
  }
  back(n, k, 1)
  return result
}

回溯开始

递归结束

把二叉搜索树转换为累加树

地址(opens new window)

// 右中左
function convertBST(root: TreeNode | null): TreeNode | null {
  if (!root) {
    return null
  }

  let pre = 0
  const cascader = (root) => {
    if (!root) {
      return
    }

    cascader(root.right) // 右
    root.val += pre
    pre = root.val
    cascader(root.left)
  }

  cascader(root)
  return root
};

// 迭代法
function convertBST(root: TreeNode | null): TreeNode | null {
    if (!root) {
        return root
    }

    let stack: TreeNode[] = [root]
    let prev = 0
    while(stack.length) {
        const node = stack.pop()
        if (!node) {
            const node = stack.pop()
            node.val += prev
            prev = node.val
            continue
        }

        node.left && stack.push(node.left)
        stack.push(node, null)
        node.right && stack.push(node.right)
    }
    return root
};

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

地址(opens new window)

1. 直接递归

function sortedArrayToBST(nums: number[]): TreeNode | null {
  const halfLen = Math.floor(nums.length / 2)
  const root = new TreeNode(nums[halfLen])
  if (halfLen > 0) {
    root.left = sortedArrayToBST(nums.slice(0, halfLen))
  }

  if (halfLen < nums.length - 1) {
    root.right = sortedArrayToBST(nums.slice(halfLen + 1, nums.length))
  }

  return root
};

// 另一种写法
function sortedArrayToBST(nums: number[]): TreeNode | null {
    // 不断的取中间
    if (!nums.length) {
        return null
    }

    const half = Math.floor(nums.length / 2)
    const node = new TreeNode(nums[half])
    node.left = sortedArrayToBST(nums.slice(0, half))
    node.right = sortedArrayToBST(nums.slice(half + 1))
    return node
};

2. 使用取值的方式

function sortedArrayToBST(nums: number[]): TreeNode | null {
  const cascader = (nums: number[], start = 0, end) => {
    if (start >= end) {
      return null
    }
    const halfLen = Math.floor((end + start) / 2)
    const root = new TreeNode(nums[halfLen])
    root.left = cascader(nums, start, halfLen)
    root.right = cascader(nums, halfLen + 1, end)
    return root
  }

  return cascader(nums, 0, nums.length)
};

// 迭代
function sortedArrayToBST(nums: number[]): TreeNode | null {
    if (!nums.length) {
        return null
    }

    const node = new TreeNode(0)
    const stack: [TreeNode, number, number][] = [[node, 0, nums.length - 1]]
    while(stack.length) {
        const [node, left, right] = stack.shift()
        let mid = Math.floor((right + left) / 2)
        node.val = nums[mid]

        // 通过判断左边或者右边的边界来生成值，原理和递归一致
        if (left <= mid - 1) {
            node.left = new TreeNode(0)
            stack.push([node.left, left, mid - 1])
        }

        if (right >= mid + 1) {
            node.right = new TreeNode(0)
            stack.push([node.right, mid + 1, right])
        }
    }

    return node
};

修剪二叉搜索树

地址(opens new window)

function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
  if (!root) {
    return null
  }

  // 如果当前值小于最小值
  if (root.val < low) {
    return trimBST(root.right, low, high)
  }

  // 如果当前值大于最大值
  if (root.val > high) {
    return trimBST(root.left, low, high)
  }

  if (root.left) {
    root.left = trimBST(root.left, low, high)
  }

  if (root.right) {
    root.right = trimBST(root.right, low, high)
  }
  return root
}

// 迭代
function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
    if (!root) {
        return root
    }

    const stack: TreeNode[] = [root]

    while(stack.length) {
        const node = stack.shift()
        if (node.right && node.right.val > high) {
            node.right = node.right.left
            stack.push(node)
            continue
        }

        if (node.left && node.left.val < low) {
            node.left = node.left.right
            stack.push(node)
            continue
        }

        node.left && stack.push(node.left)
        node.right && stack.push(node.right)
    }

    while (root && root.val > high) {
        root = root.left
    }

    while (root && root.val < low) {
        root = root.right
    }

    return root
};

// 迭代2
function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
    if (!root) {
        return root
    }

    // 处理root节点

    while (root && (root.val < low || root.val > high)) {
        if (root.val < low) {
            root = root.right
        } else if(root.val > high) {
            root = root.left
        }
    }
    let cur = root
    // 处理左节点
    while (cur?.left) {
        if (cur.left.val < low) {
            cur.left = cur.left.right
            continue
        }

        cur = cur.left
    }

    cur = root
    while(cur?.right) {
        if (cur.right.val > high) {
            cur.right = cur.right.left
            continue
        }

        cur = cur.right
    }

    return root
};

删除二叉搜索树中的节点

地址(opens new window)

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  // 如果没有找到相关的节点，则直接返回null
  if (!root) {
    return null
  }

  if (root.val === key) {
    // 左树和右树都不存在
    if (!root.left && !root.right) {
      return null
    }

    // 左树存在，右树不存在
    if (root.left && !root.right) {
      return root.left
    }

    // 左树不存在右树存在
    if (root.right && !root.left) {
      return root.right
    }

    // 左树和右树都存在
    let cur = root.right
    while (cur?.left) {
      cur = cur.left
    }
    cur.left = root.left
    return root.right
  }

  // 查看遍历左树还是右树
  if (root.val > key) {
    root.left = deleteNode(root.left, key)
  }

  if (root.val < key) {
    root.right = deleteNode(root.right, key)
  }

  return root
}

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  if (!root) {
    return null
  }

  const insertKey = (root: TreeNode | null, insertEle: TreeNode | null) => {
    if (!insertEle) {
      return root
    }
    if (!root) {
      return insertKey
    }
    while (root) {
      if (root.val > insertEle.val) {
        if (root.left) {
          root = root.left
          continue
        }
        root.left = insertEle
        return root
      }
      if (root.right) {
        root = root.right
        continue
      }
      root.right = insertEle
      return root
    }
  }

  if (root.val === key) {
     insertKey(root.right, root.left)
    return root.right ? root.right : root.left
  }

  // 核心思想就是左树移到右树上
  let treeNode = root
  while(root) {
    if (root.left?.val === key) {
      insertKey(root.left.right, root.left.left)
      root.left = root.left.right || root.left.left
      break
    }
    if (root.right?.val === key) {
      insertKey(root.right.right, root.right.left)
      root.right = root.right.right || root.right.left
      break
    }
    root = root.val > key ? root.left : root.right
  }
  return treeNode
}

二叉搜索树中的插入操作

地址(opens new window)

function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
  // 插入到子元素中
  if (!root) {
    return new TreeNode(val)
  }
  const newNode = root
  let cur = newNode
  while (cur) {
    // 查看是向左插入还是向右插入
    if (cur.val > val) {
      if (cur.right) {
        cur = cur.right
        continue
      }
      cur.left = new TreeNode(val)
      return newNode
    }
    if (cur.left) {
      cur = cur.left
      continue
    }
    cur.right = new TreeNode(val)
    return newNode
  }
}

// 简化操作
function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
    const addNode = new TreeNode(val)
    if (!root) {
        return addNode
    }

    let node = root
    let parent = node
    while(node) {
        parent = node
        node = node.val > val ? node.left : node.right
    }

    parent.val > val ? (node.left = addNode) : (node.right = addNode)
    return root
};

// 递归
function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
    const addNode = new TreeNode(val)
    if (!root) {
        return addNode
    }

    let node = root
    const cascader = (root: TreeNode) => {
        if (!root) {
            return root
        }

        if (root.val > val) {
            if (root.left) {
                cascader(root.left)
                return
            }
            root.left = addNode
            return
        }

        if (root.val < val) {
            if (root.right) {
                cascader(root.right)
                return
            }

            root.right = addNode
        }
    }
    cascader(node)
    return root
};

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

地址(opens new window)

可以通过判断左右元素值来得到最近公共祖先

// 迭代
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    while(root) {
        if (root.val > p.val && root.val > q.val) {
            root = root.left
            continue
        }

        if (root.val < p.val && root.val < q.val) {
            root = root.right
            continue
        }

        return root
    }

    return root
}

// 递归
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
	if (!root) {
        return root
    }

    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q)
    }

    if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q)
    }

    return root
};

二叉树的最近公共祖先

地址(opens new window)

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
  if (root === p || root === q || !root) {
    return root
  }

  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)
  if (left && right) {
    return root
  }

  if (!left && right) {
    return right
  }

  return left
};

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
  let curP = p
  let curQ = q
	// 采用后序遍历
  const cascader = (root: TreeNode | null) => {
    if (!root) {
      return null;
    }

    cascader(root.left);
    cascader(root.right);

    // 查找左和右是否相等
    if (curP === curQ) {
      return;
    }

    if (root.left === curP || root.right === curP) {
      curP = root
    }
    if (root.left === curQ || root.right === curQ) {
      curQ = root
    }
  }
  cascader(root)
  return curP;
};

二叉搜索树中的众数

地址(opens new window)

// 其实思想上就是借助左中右递增的思路
// 如果count大于maxCount，那么重新赋值
// 如果count等于maxCount，那么push操作
function findMode(root: TreeNode | null): number[] {
  let maxCount = 0 // 最大频率
  let count = 1 // 统计频率
  let pre: TreeNode | null = null
  let result: number[] = []
  const searchBST = (cur: TreeNode | null) => {
    if (!cur) {
      return
    }

    searchBST(cur.left) // 左
    // 中
    if (!pre) {
      count = 1
    } else if (pre.val === cur.val) {
      count++
    } else {
      count = 1
    }
    pre = cur

    if (count === maxCount) {
      result.push(pre.val)
    } else if (count > maxCount) {
      result = [pre.val]
      maxCount = count
    }
    searchBST(cur.right) // 右
  }
  searchBST(root)
  return result
};

function findMode(root: TreeNode | null): number[] {
  const map = new Map<number, number>();
  let cascader = (root: TreeNode | null) => {
    if (!root) {
      return;
    }
    cascader(root.left);
    map.set(root.val, (map.get(root.val) || 0) + 1);
    cascader(root.right);
  }
  cascader(root);
  let maxTimes = 0;
  let value: number[] = [];
  for (let [key, val] of map.entries()) {
    if (val > maxTimes) {
      value = [key];
      maxTimes = val;
      continue;
    }

    if (val === maxTimes) {
      value.push(key);
    }
  }
  return value;
};

// 可以不排序，直接记录maxValue
function findMode(root: TreeNode | null): number[] {
    if (!root) {
        return []
    }

    let max = 0
    let map = new Map()

    const cascader = (root: TreeNode | null) => {
        if (!root) {
            return
        }
        cascader(root.left)
        let val = (map.get(root.val) || 0) + 1

        if (val) {
            max = Math.max(val, max)
        }
        map.set(root.val, val)
        cascader(root.right)
    }

    let result: number[] = []
    for (const [key, val] of map) {
        if (val === max) {
            result.push(key)
        }
    }

    return result
};

二叉搜索树的最小绝对差

地址(opens new window)

function getMinimumDifference(root: TreeNode | null): number {
  if (!root) {
    return 0
  }
  const arr: number[] = []
  let minVal = Number.MAX_SAFE_INTEGER
  // 中序遍历
  const cascader = (root: TreeNode | null) => {
    if (!root) {
      return;
    }
    cascader(root.left)
    arr.push(root.val)
    cascader(root.right)
  }
  cascader(root)
  for (let i = 1; i < arr.length; i++) {
    minVal = Math.min(arr[i] - arr[i-1], minVal)
  }
  return minVal
};

// 直接在递归中判断
function getMinimumDifference(root: TreeNode | null): number {
    if (!root) {
        return 0
    }

    let val = Infinity
    let prev = null
    let cascader = (root: TreeNode | null) => {
       if (!root) {
           return
       }

       cascader(root.left) // 左
       if (prev) {
           val = Math.min(val, root.val - prev.val)
       }
       prev = root // 中
       cascader(root.right) // 右
    }
    cascader(root)
    return val
};

// 迭代
function getMinimumDifference(root: TreeNode | null): number {
    if (!root) {
        return 0
    }

    let val = Infinity
    const stack: TreeNode[] = []
    let cur = root
    let prev = null
    while(stack.length || cur) {
        if (cur) {
            stack.push(cur)
            cur = cur.left
            continue
        }

        const node = stack.pop()
        if (prev) {
            val = Math.min(node.val - prev.val, val)
        }
        cur = node.right
        prev = node
    }

    return val
};

验证二叉搜索树

地址(opens new window)

function isValidBST(root: TreeNode | null): boolean {
  const arr: number[] = [];
  // 中序遍历
  const cascader = (root: TreeNode | null) => {
    if (!root) {
      return;
    }
    cascader(root.left);
    arr.push(root.val);
    cascader(root.right);
  }
  cascader(root);
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= arr[i-1]) {
      return false;
    }
  }
  return true;
};

// 迭代法
function isValidBST(root: TreeNode | null): boolean {
    if (!root) {
        return true
    }

    const result: number[] = []
    const stack: TreeNode[] = []
    let cur: TreeNode = root

    while(stack.length || cur) {
        if (cur) {
            stack.push(cur)
            cur = cur.left
            continue
        }

        const node = stack.pop()
        result.push(node.val)
        cur = node.right
    }

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

    return true
};

// 迭代法-标记
function isValidBST(root: TreeNode | null): boolean {
    if (!root) {
        return true
    }

    const result: number[] = []
    const stack: (TreeNode | null)[] = [root]

    while(stack.length) {
        const node = stack.pop()

        // 加入node为null
        if (!node) {
            result.push(stack.pop().val)
            continue
        }

        node.right && stack.push(node.right)
        stack.push(node, null)
        node.left && stack.push(node.left)
    }
    for (let i = 1; i < result.length; i++) {
        if (result[i] <= result[i-1]) {
            return false
        }
    }

    return true
};

二叉搜索树中的搜索

地址(opens new window)

// 递归
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  // 终止条件
  if (!root) {
    return null;
  }

  if (root.val === val) {
    return root;
  }
	// 二叉搜索树左树小于根节点，右树大于根节点
  return searchBST(root.val > val ? root.left : root.right, val);
};

// 迭代
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  while(root) {
    if (root.val === val) {
      return root;
    }
    root = root.val > val ? root.left : root.right;
  }
  return null;
};

合并二叉树

地址(opens new window)

function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
  // 终止条件
  if (!root1) {
    return root2;
  }

  if (!root2) {
    return root1;
  }

	// 赋值
  root1.val += root2.val;

	// 递归
  root1.left = mergeTrees(root1.left, root2.left);
  root1.right = mergeTrees(root1.right, root2.right);

  return root1;
};

// 迭代
function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
    if (!root1) {
        return root2;
    }

    if (!root2) {
        return root1;
    }

    const stack: TreeNode[] = [root1, root2];
    while (stack.length) {
        const node1 = stack.shift();
        const node2 = stack.shift();
        node1.val += node2.val;

        if (node1.left && node2.left) {
            stack.push(node1.left, node2.left);
        }

        if (node1.right && node2.right) {
            stack.push(node1.right, node2.right);
        }

        // 1. 左值
        if (!node1.left) {
            node1.left = node2.left;
        }

        // 2. 右值
        if (!node1.right) {
            node1.right = node2.right;
        }
    }

    return root1;
}

最大二叉树

地址(opens new window)

function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
  // 如果数组的大小为空，则为空节点
  if (!nums.length) {
    return null
  }

  // 找到最大的元素以及序号
  let maxArr = [nums[0], 0]
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > maxArr[0]) {
      maxArr = [nums[i], i]
    }
  }
  const root = new TreeNode(maxArr[0])

  // 左树递归
  root.left = constructMaximumBinaryTree(nums.slice(0, maxArr[1]))

  // 右树递归
  root.right = constructMaximumBinaryTree(nums.slice(maxArr[1] + 1, nums.length))
  return root
};

不切割数组的形式

function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
  const cascader = (nums: number[], left: number, right: number) => {
    // 如果数组的大小为空，则为空节点
    if (left >= right) {
      return null
    }

    // 找到最大的元素的序号
    let maxIdx = left
    for (let i = left + 1; i < right; i++) {
      if (nums[i] > nums[maxIdx]) {
        maxIdx = i
      }
    }

    const root = new TreeNode(nums[maxIdx])
    root.left = cascader(nums, left, maxIdx)
    root.right = cascader(nums, maxIdx + 1, right)

    return root
  }

  return cascader(nums, 0, nums.length)
}

// 优化
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
    if (!nums.length) {
        return null
    }

    const max = Math.max(...nums)
    const root = new TreeNode(max)
    const index = nums.findIndex(item => item === max)
    root.left = constructMaximumBinaryTree(nums.slice(0, index))
    root.right = constructMaximumBinaryTree(nums.slice(index + 1))
    return root
};

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

地址(opens new window)

思路：以前序数组的第一个元素为切割点，大概思路与中序与后序遍历序列构造二叉树一致

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  if (!preorder.length) {
    return null
  }

  const rootValue = preorder[0]
  const root = new TreeNode(rootValue)

  if (preorder.length === 1) {
    return root
  }

  const cutNum = inorder.findIndex(num => num === rootValue)
  root.left = buildTree(preorder.slice(1, cutNum + 1), inorder.slice(0, cutNum))
  root.right = buildTree(preorder.slice(cutNum + 1, preorder.length), inorder.slice(cutNum + 1, inorder.length))
  return root
}

// 递归2
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if (!preorder.length) {
        return null
    }

    const mid = preorder.shift()
    const root = new TreeNode(mid)
    const index = inorder.findIndex(item => item === mid)
    root.left = buildTree(preorder.slice(0, index), inorder.slice(0, index))
    root.right = buildTree(preorder.slice(index), inorder.slice(index+1))
    return root
};

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

地址(opens new window)

思路：以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，再切割后序数组，后序数组的左数组和中序数组的左数组一致

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
  // 如果数组大小为空，则为空节点
  if (!postorder.length) {
    return null
  }

  // 不为空，取后序数组最后一个元素
  const rootValue = postorder[postorder.length - 1]
  const root = new TreeNode(rootValue)

  // 只有一个元素
  if (postorder.length === 1) {
    return root
  }

  // 找到切割点
  const cutNum = inorder.findIndex(num => num === rootValue)

  // 后序数组的左数组长度和中序左数组长度一致

  // 切割中序数组，得到中序左数组和后序左数组
  root.left = buildTree(inorder.slice(0, cutNum), postorder.slice(0, cutNum))

  // 切割后序数组，得到中序右数组和后序右数组
  root.right = buildTree(inorder.slice(cutNum + 1, inorder.length), postorder.slice(cutNum, -1))

  return root;
};

// 改进
function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
    if (!postorder.length) {
        return null
    }
    const mid = postorder.pop()
    let root: TreeNode = new TreeNode(mid)

    // 取左边数量
    const leftIndex = inorder.findIndex(item => item === mid)
    root.left = buildTree(inorder.slice(0, leftIndex), postorder.slice(0, leftIndex))
    root.right = buildTree(inorder.slice(leftIndex+1), postorder.slice(leftIndex))
    return root
};

路径总和 II

地址(opens new window)

// 递归
function pathSum(root: TreeNode | null, targetSum: number): number[][] {
    let paths: number[][] = [];

    let cascader = (root: TreeNode | null, targetSum, path = []) => {
        if (!root) {
            return;
        }

        // 终止条件，但处于叶子节点时，那么判断是否需要推到paths下
        if (!root.left && !root.right) {
            targetSum === root.val && (paths.push(path.concat(root.val)));
            return;
        }

        // 左孩子
        cascader(root.left, targetSum - root.val, [].concat(...path, root.val));

        // 右孩子
        cascader(root.right, targetSum - root.val, [].concat(...path, root.val));
    }

    cascader(root, targetSum);
    return paths;
};

// 递归2
function pathSum(root: TreeNode | null, targetSum: number): number[][] {
    if (!root) {
        return []
    }

    const result: string[] = []

    const cascader = (root: TreeNode | null, targetSum, content = '') => {
        if (!root) {
            return
        }

        targetSum -= root.val

        if (!root.left && !root.right) {
            targetSum === 0 && result.push(content + root.val)
            return
        }
        content += root.val + ','
        cascader(root.left, targetSum, content)
        cascader(root.right, targetSum, content)
    }
    cascader(root, targetSum)

    return result.map(item => item.split(',').map(num => +num))
};

// 层序遍历
function pathSum(root: TreeNode | null, targetSum: number): number[][] {
    if (!root) {
        return []
    }

    const result: string[] = []
    const stack: [TreeNode, number, string][] = [[root, targetSum, '']]
    while(stack.length) {
        let [node, targetSum, content] = stack.shift()

        if (!node.left && !node.right) {
            targetSum === node.val && result.push(content + node.val)
            continue
        }

        targetSum -= node.val
        content += node.val + ','
        node.left && stack.push([node.left, targetSum, content])
        node.right && stack.push([node.right, targetSum, content])
    }

    return result.map(item => item.split(',').map(num => +num))
};

路径总和

地址(opens new window)

// 递归
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (!root) {
        return false;
    }

    // 终止条件，当没有叶子节点时，查看目标值是否等于叶子节点值
    if (!root.left && !root.right) {
        return targetSum === root.val;
    }

    let left = false;
    let right = false;

    // 查看左边叶子节点是否满足需求
    if (root.left) {
        left = hasPathSum(root.left, targetSum - root.val);
    }

    // 查看右边叶子节点是否满足需求
    if (root.right) {
        right = hasPathSum(root.right, targetSum - root.val);
    }

    return left || right;
};

// 优化
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (!root) {
        return false;
    }

    // 终止条件，当没有叶子节点时，查看目标值是否等于叶子节点值
    if (!root.left && !root.right) {
        return targetSum === root.val;
    }

    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
};

// 迭代
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (!root) {
        return false
    }

    const stack: [TreeNode, number][] = [[root, targetSum]]
    while(stack.length) {
        let [node, value] = stack.shift()

        value -= node.val

        // 终止了
        if (!node.left && !node.right) {
            if (!value) {
                return true
            }
        }

        node.left && stack.push([node.left, value])
        node.right && stack.push([node.right, value])
    }

    return false
};

找树左下角的值

地址(opens new window)

通过自定义depth，然后迭代解决

interface NodeAndDepth {
    depth: number;
    root: TreeNode;
}

function findBottomLeftValue(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }

    let nodeAndDepth: NodeAndDepth[] = [{ depth: 0, root }];
    let val = 0;
    let maxDepth = -1;
    while(nodeAndDepth.length) {
        let node = nodeAndDepth.shift();
        if (!node.root.left && !node.root.right) {
            if (node.depth > maxDepth) {
                val = node.root.val;
                maxDepth = node.depth;
            }
        }
        node.root.left && nodeAndDepth.push({ depth: node.depth + 1, root: node.root.left });
        node.root.right && nodeAndDepth.push({ depth: node.depth + 1, root: node.root.right });
    }
    return val;
};

直接迭代解决

function findBottomLeftValue(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }

    let nodes: TreeNode[] = [root];
    let val = 0;
    while(nodes.length) {
        let len = nodes.length;
        for (let i = 0; i < len; i++) {
            let node = nodes.shift();
            i === 0 && (val = node.val);
            node.left && nodes.push(node.left);
            node.right && nodes.push(node.right);
        }
    }
    return val;
};

// 递归解决
function findBottomLeftValue(root: TreeNode | null): number {
    if (!root) {
        return -1
    }
    let result = root.val
    let maxDepth = 0
    const cascader = (root: TreeNode, depth = 0) => {
        if (!root) {
            return depth
        }

        if (!root.left && !root.right) {
            if (depth > maxDepth) {
                maxDepth = depth
                result = root.val
            }
            return depth
        }

        const leftDepth = cascader(root.left, depth + 1)
        const rightDepth = cascader(root.right, depth + 1)

        return Math.max(leftDepth, rightDepth)
    }
    cascader(root)
    return result
};

左叶子之和

地址(opens new window)

左叶子概念：该节点有左节点，同时该左节点没有左右节点，则该节点为左叶子

递归

function sumOfLeftLeaves(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    let leftNum = sumOfLeftLeaves(root.left);
    let rightNum = sumOfLeftLeaves(root.right);
    let value = 0;
    if (root.left && !root.left.left && !root.left.right) {
        value = root.left.val;
    }

    return leftNum + rightNum + value;
};

迭代法

function sumOfLeftLeaves(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    const nodes: TreeNode[] = [root];
    let sum = 0;
    while(nodes.length) {
        let node = nodes.shift();
        if (node.left && !node.left.left && !node.left.right) {
            sum += node.left.val;
        }
        node.left && nodes.push(node.left);
        node.right && nodes.push(node.right);
    }

    return sum;
};

二叉树的所有路径

地址(opens new window)

function binaryTreePaths(root: TreeNode | null): string[] {
    let result: string[] = [];
    let getPath = (root: TreeNode | null, path: string, result: string[] = []) => {
        if (!root) {
            return result;
        }
        path += `${root.val}`;
        if (!root.left && !root.right) {
            return result.push(path);
        }
        root.left && getPath(root.left, path + '->', result);
        root.right && getPath(root.right, path + '->', result);
    }
    getPath(root, '', result)
    return result;
};

// 迭代的方式
function binaryTreePaths(root: TreeNode | null): string[] {
    if (!root) {
        return []
    }

    const result: string[] = []
    const stack: [TreeNode, string][] = [[root, '']]

    while(stack.length) {
        let [top, content] = stack.shift()

        if (!top.left && !top.right) {
            result.push(content + top.val)
            continue
        }

        content += top.val + '->'
        if (top.left) {
            stack.push([top.left, content])
        }

        if (top.right) {
            stack.push([top.right, content])
        }
    }

    return result
};

平衡二叉树

地址(opens new window)

function isBalanced(root: TreeNode | null): boolean {
    let getDepth = (root: TreeNode | null) => {
        if (!root) {
            return 0;
        }

        // 左树高度
        let leftDepth = getDepth(root.left);
        if (leftDepth === -1) {
            return -1;
        }

        // 右树高度
        let rightDepth = getDepth(root.right);
        if (rightDepth === -1) {
            return -1;
        }

        // 如果高度差大于1则直接返回-1
        return Math.abs(leftDepth - rightDepth) > 1 ? -1 : 1 + Math.max(leftDepth, rightDepth);
    }

    return getDepth(root) !== -1;
};

完全二叉树的节点个数

地址(opens new window)

递归 + 树结构特征

function countNodes(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    let leftDepth = 0;
    let rightDepth = 0;
    let left = root;
    let right = root;

    while(left) {
        left = left.left;
        leftDepth++;
    }

    while (right) {
        right = right.right;
        rightDepth++;
    }

    // 等比数列公式 Sn = a0 * (1 - q^n) / (1 - q)
    // 这里的目的是求取完全二叉树时获得的节点数
    leftDepth
    if (leftDepth === rightDepth) {
        return 2 ** leftDepth - 1;
    }
    return 1 + countNodes(root.right) + countNodes(root.left);
};

递归

function countNodes(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }

    if (!root.left && !root.right) {

        // root节点加1
        return 1;
    }

    if (!root.left) {
        return 1 + countNodes(root.right);
    }

    if (!root.right) {
        return 1 + countNodes(root.left);
    }

    return 1 + countNodes(root.right) + countNodes(root.left);
};

function countNodes(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    return 1 + countNodes(root.right) + countNodes(root.left);
};

迭代

function countNodes(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }

    let count = 0;
    let stack: TreeNode[] = [root];
    while(stack.length) {
        let len = stack.length;
        for (let i = 0; i < len; i++) {
            let node = stack.shift();
            node.left && stack.push(node.left);
            node.right && stack.push(node.right);
        }
        count += len;
    }
    return count;
};

二叉树的最小深度

地址(opens new window)

迭代

function minDepth(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }
    let depth = 0;
    let stack: TreeNode[] = [root];
    while(stack.length) {
        let len = stack.length;
        for (let i = 0; i < len; i++) {
            let node = stack.shift();

            if (node.left === null || node.right === null) {
                return depth + 1;
            }

            node.left && stack.push(node.left);
            node.right && stack.push(node.right);
        }
        depth++;
    }
    return depth;
};

递归

function minDepth(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }

    const cascader = (root: TreeNode | null, depth = 0) => {
        if (!root.left && !root.right) {
            return depth;
        }

        // 如果左树为null，那么需要计算右树的
        if (!root.left) {
            return cascader(root.right, depth + 1);
        }

        // 如果右树为null，那么计算左树的
        if (!root.right) {
            return cascader(root.left, depth + 1);
        }

        let leftDepth = cascader(root.left, depth + 1);
        let rightDepth = cascader(root.right, depth + 1);
        return Math.min(leftDepth, rightDepth);
    }
    return cascader(root, 0) + 1;
};


function minDepth(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }

    if (!root.left && !root.right) {
        return 1;
    }

    if (!root.left) {
        return 1 + minDepth(root.right);
    }

    if (!root.right) {
        return 1 + minDepth(root.left);
    }

    return 1 + Math.min(minDepth(root.right), minDepth(root.left));
};

N 叉树的最大深度

地址(opens new window)

递归

function maxDepth(root: Node | null): number {
    if (root === null) {
        return 0;
    }
    let depth = 0;
    if (root.children?.length > 0) {
        for (let i = 0; i < root.children.length; i++) {
            depth = Math.max(maxDepth(root.children[i]), depth);
        }
    }
    return 1 + depth;
};

迭代

function maxDepth(root: Node | null): number {
    if (root === null) {
        return 0;
    }
    let depth = 0;
    let stack: Node[] = [root];
    while(stack.length) {
        let len = stack.length;
        for (let i = 0; i < len; i++) {
            let node = stack.shift();
            if (node.children?.length > 0) {
                stack.push(...node.children);
            }
        }
        depth++;
    }
    return depth;
};

二叉树的最大深度

地址(opens new window)

迭代

function maxDepth(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }

    let stack: TreeNode[] = [root];
    let depth = 0;
    while(stack.length) {
        let size = stack.length;
        for (let i = 0; i < size; i++) {
            let node = stack.shift();
            node.left && stack.push(node.left);
            node.right && stack.push(node.right);
        }
        depth++;
    }
    return depth;
};

递归

function maxDepth(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }

    let cascaderTree = (root: TreeNode | null, depth = 0) => {
        if (root === null) {
            return depth;
        }
        let leftDepth = cascaderTree(root.left, depth + 1);
        let rightDepth = cascaderTree(root.right, depth + 1);
        return Math.max(leftDepth, rightDepth);
    }
    return cascaderTree(root);
};

function maxDepth(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

对称二叉树

地址(opens new window)

迭代

// 迭代1
function isSymmetric(root: TreeNode | null): boolean {
    if (root === null) {
        return true;
    }

    let stack: TreeNode[] = [root.left, root.right];
    while (stack.length) {
        let len = stack.length;
        let curNum: number[] = [];
        for (let i = 0, halfLen = len / 2; i < len; i++) {
            let node = stack.shift();

            // 前一半取值后一半去值
            if (i < halfLen) {
                curNum.push(node?.val);
            } else {
                if (curNum.pop() !== node?.val) {
                    return false;
                }
            }

            node && stack.push(node.left);
            node && stack.push(node.right);
        }
    }

    return true;
};

// 迭代2
function isSymmetric(root: TreeNode | null): boolean {
    if (root === null) {
        return true;
    }

    let queue: TreeNode[] = [root.left, root.right];
    while(queue.length) {
        let leftNode = queue.shift();
        let rightNode = queue.shift();

        // 都为null的情况
        if (!leftNode && !rightNode) {
            continue;
        }

        if (!leftNode && rightNode || (leftNode && !rightNode) || (leftNode.val !== rightNode.val)) {
            return false;
        }

        queue.push(leftNode.left);
        queue.push(rightNode.right);
        queue.push(leftNode.right);
        queue.push(rightNode.left);
    }
    return true;
};

递归

function isSymmetric(root: TreeNode | null): boolean {
    if (root === null) {
        return true;
    }

    const compare = (left: TreeNode | null, right: TreeNode | null) => {
        // 如果都为null
        if (!left && !right) {
            return true
        }

        // 只有一个为null或者值不相等
        if (!left || !right || left.val !== right.val) {
            return false
        }

        // 比较外侧是否对称
        const outside = compare(left.left, right.right);
        // 比较内侧是否对称
        const inside = compare(left.right, right.left);

        return outside && inside;
    }
    return compare(root.left, root.right);
};

翻转二叉树

层序遍历

function invertTree(root: TreeNode | null): TreeNode | null {
    let stack: TreeNode[] = [];

    if (root !== null) {
        stack.push(root);
    }

    while(stack.length) {
        let len = stack.length;
        for (let i = 0; i < len; i++) {
            let node = stack.shift()!;

            // 每层都反转
            let temp = node.left;
            node.left = node.right;
            node.right = temp;
            node.left && stack.push(node.left);
            node.right && stack.push(node.right);
        }
    }
    return root;
};

递归

// 递归遍历
function invertTree(root: TreeNode | null): TreeNode | null {
    if (root === null) {
        return root;
    }

    let temp = root.left;
    root.left = root.right;
    root.right = temp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

// 直接简化
function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) {
        return root
    }

    let left = root.left
    root.left = invertTree(root.right)
    root.right = invertTree(left)
    return root
};

迭代

function invertTree(root: TreeNode | null): TreeNode | null {
    if (root === null) {
        return root;
    }

    let stack: TreeNode[] = [root];

    while(stack.length) {
        let node = stack.pop();
        let temp = node.left;
        node.left = node.right;
        node.right = temp;
        node.left && stack.push(node.left);
        node.right && stack.push(node.right);
    }
    return root;
};

填充每个节点的下一个右侧节点指针 II

地址(opens new window)

代码与1一致

填充每个节点的下一个右侧节点指针

地址(opens new window)

function connect(root: Node1 | null): Node1 | null {
    let stack: Node1[] = [];

    if (root !== null) {
        stack.push(root);
    }

    while (stack.length) {
        let len = stack.length;
        let curNode = null;
        for (let i = 0; i < len; i++) {
            let node = stack.shift();
            curNode && (curNode.next = node);
            curNode = node;
            node.left && stack.push(node.left);
            node.right && stack.push(node.right);
        }
        curNode.next = null;
    }

    return root;
};

在每个树行中找最大值

地址(opens new window)

function largestValues(root: TreeNode | null): number[] {
    let result: number[] = [];
    let stack: TreeNode[] = [];

    if (root !== null) {
        stack.push(root);
    }

    while (stack.length) {
        let len = stack.length;
        let max = -Infinity;
        for (let i = 0; i < len; i++) {
            let node = stack.shift();
            max = Math.max(max, node.val);
            node.left && stack.push(node.left);
            node.right && stack.push(node.right);
        }
        result.push(max);
    }
    return result;
};

N 叉树的层序遍历

地址(opens new window)

function levelOrder(root: Node | null): number[][] {
    let result: number[][] = [];
    let stack: Node[] = [];

    if (root !== null) {
        stack.push(root);
    }

    while (stack.length) {
        let len = stack.length;
        let curStack = [];
        for (let i = 0; i < len; i++) {
            let node = stack.shift();
            curStack.push(node.val);
            node.children && stack.push(...node.children);
        }
        result.push(curStack);
    }
    return result;
};

二叉树的层平均值

地址(opens new window)

function averageOfLevels(root: TreeNode | null): number[] {
    let result: number[] = [];
    let stack: TreeNode[] = [];

    if (root !== null) {
        stack.push(root);
    }

    while (stack.length) {
        let len = stack.length;
        let sum = 0;
        for (let i = 0; i < len; i++) {
            let node = stack.shift();
            sum += node.val;
            node.left && stack.push(node.left);
            node.right && stack.push(node.right);
        }
        result.push(sum / len);
    }
    return result;
};

二叉树的右视图

地址(opens new window)

// 层序遍历
function rightSideView(root: TreeNode | null): number[] {
    let result: number[] = [];
    let queue: TreeNode[] = [];
    if (root !== null) {
        queue.push(root);
    }

    while (queue.length) {
        let len = queue.length;
        let curLevel: number[] = [];
        for (let i = 0; i < len; i++) {
            let node = queue.shift();
            curLevel.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        result.push(curLevel.pop()); // 取最后一个
    }
    return result;
}

// 优化
function rightSideView(root: TreeNode | null): number[] {
    let result: number[] = [];
    let queue: TreeNode[] = [];
    if (root !== null) {
        queue.push(root);
    }

    while (queue.length) {
        let len = queue.length;
        for (let i = 0; i < len; i++) {
            let node = queue.shift();
            if (i === len - 1) {
                result.push(node.val);
            }
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return result;
}

二叉树的层序遍历2

地址(opens new window)

function levelOrderBottom(root: TreeNode | null): number[][] {
    let result: number[][] = [];
    let queue: TreeNode[] = [];
    if (root !== null) {
        queue.push(root);
    }

    while (queue.length) {
        let len = queue.length;
        let curLevel: number[] = [];
        for (let i = 0; i < len; i++) {
            let node = queue.shift();
            curLevel.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        result.unshift(curLevel);
    }
    return result;
}

二叉树的层序遍历

地址(opens new window)

function levelOrder(root: TreeNode | null): number[][] {
    let result: number[][] = [];
    let queue: TreeNode[] = [];
    if (root !== null) {
        queue.push(root);
    }

    while (queue.length) {
        let len = queue.length;
        let curLevel: number[] = [];
        for (let i = 0; i < len; i++) {
            let node = queue.shift();
            curLevel.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        result.push(curLevel);
    }
    return result;
}

二叉树的后序遍历

地址(opens new window)

// 递归
function postorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = []
    const cascader = (root: TreeNode | null) => {
        if (!root) {
            return
        }

        cascader(root.left) // 左
        cascader(root.right) // 右
        result.push(root.val) // 中
    }

    cascader(root)

    return result
};

// 通过反转的方式实现后序遍历
function postorderTraversal(root: TreeNode | null): number[] {
    if (root === null) {
        return [];
    }
    let arr: number[] = [];
    let stack: TreeNode[] = [root];
    let cur = null;

    // 顺序中右左
    while (stack.length) {
        cur = stack.pop();
        arr.push(cur.val);
        cur.left && (stack.push(cur.left)); // 左子树后出栈
        cur.right && (stack.push(cur.right)); // 右子树先出栈
    }

    return arr.reverse();
};

标记法

function postorderTraversal(root: TreeNode | null): number[] {
    let result: number[] = [];
    let stack: TreeNode[] = [];
    if (root !== null) {
        stack.push(root);
    }

    while (stack.length) {
        let node = stack.pop();
        if (node !== null) {
            stack.push(node);
            stack.push(null); // 为了确保else的时候取到中间节点的值
            node.right && stack.push(node.right);
            node.left && stack.push(node.left);
            continue;
        }
        node = stack.pop(); // 这里都是取中间节点的值
        result.push(node.val);
    }
    return result;
};

二叉树的中序遍历

地址(opens new window)

// 递归
function inorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = []
    const cascader = (root: TreeNode | null) => {
        if (!root) {
            return
        }

        cascader(root.left) // 左
        result.push(root.val) // 中
        cascader(root.right) // 右
    }

    cascader(root)

    return result
};

迭代法

function inorderTraversal(root: TreeNode | null): number[] {
    if (root === null) {
        return [];
    }
    let arr: number[] = [];
    let stack: TreeNode[] = [];
    let cur = root;
    while (cur || stack.length) {
        // 先一直到左边
        if (cur) {
            // 先往左树查找
            stack.push(cur);
            cur = cur.left;
            continue;
        }

        // 左树查找完取值
        cur = stack.pop(); // 出栈
        arr.push(cur.val);

        // 然后往右树查找
        cur = cur.right; // 出栈的元素是否有右子树
    }

    return arr;
};

标记法

function inorderTraversal(root: TreeNode | null): number[] {
    let result: number[] = [];
    let stack: TreeNode[] = [];
    if (root !== null) {
        stack.push(root);
    }

    while (stack.length) {
        let node = stack.pop();
        if (node !== null) {
            node.right && stack.push(node.right);
            stack.push(node);
            stack.push(null); // 为了确保else的时候取到中间节点的值
            node.left && stack.push(node.left);
            continue;
        }
        node = stack.pop(); // 这里都是取中间节点的值
        result.push(node.val);
    }
    return result;
};

// 优化
// 思路其实就是为了标记中间节点，让中间节点后面跟一个null，当取到null的时候就直接取值就可以了
function inorderTraversal(root: TreeNode | null): number[] {
    if (!root) {
        return []
    }

    const stack: (TreeNode | null)[] = [root]
    const result: number[] = []

    while (stack.length) {
        const node = stack.pop()
        if (!node) {
            result.push(stack.pop().val)
            continue
        }

        node.right && stack.push(node.right) // 右
        stack.push(node, null) // 中
        node.left && stack.push(node.left) // 左
    }

    return result
};

二叉树的前序遍历

地址(opens new window)

递归

function preorderTraversal(root: TreeNode | null): number[] {
    let arr: number[] = [];
    let cascader = (tree: TreeNode) => {
        if (tree === null) {
            return;
        }
        arr.push(tree.val); // 中
        cascader(tree.left); // 左
        cascader(tree.right); // 右
    }
    cascader(root);
    return arr;
};

迭代法

function preorderTraversal(root: TreeNode | null): number[] {
    if (root === null) {
        return [];
    }
    let arr: number[] = [];
    let stack: TreeNode[] = [root];
    let cur = null;
    while (stack.length) {
        cur = stack.pop(); // 中间最先出栈，之后左子树，之后右子树
        arr.push(cur.val);
        cur.right && (stack.push(cur.right)); // 右子树后出栈
        cur.left && (stack.push(cur.left)); // 左子树先出栈
    }

    return arr;
};

标记法

function preorderTraversal(root: TreeNode | null): number[] {
    let result: number[] = [];
    let stack: TreeNode[] = [];
    if (root !== null) {
        stack.push(root);
    }

    while (stack.length) {
        let node = stack.pop();
        if (node !== null) {
            node.right && stack.push(node.right);
            node.left && stack.push(node.left);
            stack.push(node);
            stack.push(null); // 为了确保else的时候取到中间节点的值
            continue;
        }
        node = stack.pop(); // 这里都是取中间节点的值
        result.push(node.val);
    }
    return result;
};

前 K 个高频元素

地址(opens new window)

解法一

function topKFrequent(nums: number[], k: number): number[] {
    let map = new Map();

    // 计算出现的频率
    for (const num of nums) {
        map.set(num, (map.get(num) || 0) + 1);
    }

    const arr: number[] = [];

    for (const [key, value] of map.entries()) {
        if (arr.length === k) {
            if (value > map.get(arr[k - 1])) {
                arr.pop();
                arr.push(key);
            }
        } else {
            arr.push(key);
        }
        arr.sort((prev, next) => map.get(next) - map.get(prev));
    }
    return arr;
};

解法二

function topKFrequent(nums: number[], k: number): number[] {
    // 也可以为对象形式
    let map = new Map();

    // 计算出现的频率
    for (const num of nums) {
        map.set(num, (map.get(num) || 0) + 1);
    }

    let arr: [number, number][] = Array.from(map.entries()).sort((prev, next) => next[1] - prev[1]);
    let newArr: number[] = [];
    for (let i = 0; i < k; i++) {
        newArr.push(arr[i][0]);
    }

    return newArr;
};

滑动窗口最大值

地址(opens new window)

思路：维护一个单调堆栈，最大的排在前面

// 采用序号的方式
function maxSlidingWindow(nums: number[], k: number): number[] {
    let newArr: number[] = [];
    let stak: number[] = []; // 单调队列

    // 获取前k项单调序列
    for (let i = 0; i < k; i++) {
        while (stak.length > 0 && nums[i] >= nums[stak[stak.length - 1]]) {
            stak.pop();
        }
        stak.push(i);
    }
    newArr.push(nums[stak[0]]);

    // 获取从k项起的单调序列
    for (let i = k, len = nums.length; i < len; i++) {
        if (i - k === stak[0]) {
            stak.shift();
        }
        while (stak.length > 0 && nums[i] > nums[stak[stak.length - 1]]) {
            stak.pop(); // 弹出队尾
        }
        stak.push(i);
        newArr.push(nums[stak[0]]);
    }
    return newArr;
};

优化后：

function maxSlidingWindow(nums: number[], k: number): number[] {
    let newArr: number[] = [];
    let stak: number[] = []; // 单调队列
    for (let i = 0, len = nums.length; i < len; i++) {
        while (stak.length > 0 && nums[i] > nums[stak[stak.length - 1]]) {
            stak.pop(); // 弹出队尾
        }
        stak.push(i);
        if (i - k >= -1) {
            if (i - k === stak[0]) {
                stak.shift();
            }
            newArr.push(nums[stak[0]]);
        }
    }
    return newArr;
};

// 采用值的方式
function maxSlidingWindow(nums: number[], k: number): number[] {
    const len = nums.length

    // 记录单调递减栈
    let stack: number[] = []

    // 先找到从0到k的最大值
    for (let i = 0; i < k; i++) {
        while (stack.length && stack[stack.length - 1] < nums[i]) {
            stack.pop()
        }

        stack.push(nums[i])
    }

    // 记录结果的栈
    const result: number[] = [stack[0]]

    for (let i = k; i < len; i++) {

        // 判断是否移除首个
        if (nums[i-k] === stack[0]) {
            stack.shift()
        }

        while (stack.length && stack[stack.length - 1] < nums[i]) {
            stack.pop()
        }

        stack.push(nums[i])
        result.push(stack[0])
    }

    return result
};

逆波兰表达式求值

地址(opens new window)

function evalRPN(tokens: string[]): number {
    const stack: number[] = []

    for (const s of tokens) {
        if (s === '+') {
            stack.push(stack.pop() + stack.pop())
        } else if (s === '-') {
            stack.push(-(stack.pop() - stack.pop()))
        } else if (s === '*') {
            stack.push(stack.pop() * stack.pop())
        } else if (s === '/') {
            stack.push(Math.trunc(1 / (stack.pop() / stack.pop())))
            // stack.push(Number.parseInt((1 / (stack.pop() / stack.pop())).toString()))
        } else {
            stack.push(+s)
        }
    }

    return stack[0]
};

删除字符串中的所有相邻重复项

地址(opens new window)

function removeDuplicates(s: string): string {
    const stack: string[] = []
    for (const word of s) {
        if (stack[stack.length - 1] !== word) {
            stack.push(word)
            continue
        }

        stack.pop()
    }
    return stack.join('')
};

有效的括号

地址(opens new window)

function isValid(s: string): boolean {
    const stack: string[] = []
    const map = new Map([
        [')', '('],
        [']', '['],
        ['}', '{']
    ])

    for (const word of s) {
        if (map.has(word)) {
            if (map.get(word) !== stack.pop()) {
                return false
            }
            continue
        }

        stack.push(word)
    }

    return stack.length === 0
};

// 使用if-else判断
function isValid(s: string): boolean {
    const stack: string[] = []

    for (const word of s) {
        if (word === '{') {
            stack.push('}')
        } else if (word === '(') {
            stack.push(')')
        } else if (word === '[') {
            stack.push(']')
        } else if (stack.length === 0 || stack.pop() !== word) {
            return false
        }
    }

    return stack.length === 0
};

用队列实现栈

地址(opens new window)

class MyStack {
    stack: number[]
    constructor() {
        this.stack = []
    }

    push(x: number): void {
        this.stack.unshift(x)
    }

    pop(): number {
        return this.stack.shift()
    }

    top(): number {
        return this.stack[0]
    }

    empty(): boolean {
        return this.stack.length === 0
    }
}

用栈实现队列

地址(opens new window)

class MyQueue {
    queue: number[]
    constructor() {
        this.queue = []
    }

    push(x: number): void {
        this.queue.push(x)
    }

    pop(): number {
        return this.queue.shift()
    }

    peek(): number {
        return this.queue[0]
    }

    empty(): boolean {
        return this.queue.length === 0
    }
}

重复的子字符串

地址(opens new window)

// 暴力破解
function repeatedSubstringPattern(s: string): boolean {
    const len = s.length

    if (len === 1) {
        return false
    }

    const half = Math.floor(len / 2)
    let i = 1

    while (i <= half) {
        if (Math.ceil(len / i) === len / i && s.slice(0, i).repeat(len / i) === s) {
            return true
        }

        i++
    }

    return false
}

// KMP
function repeatedSubstringPattern(s: string): boolean {
    if (s === '') {
        return true;
    }
    let j = 0;
    let next = [0];
    let len = s.length;

    // 获取next参数
    for (let i = 1; i < len; i++) {

        // 前缀与后缀不相等时
        while (j > 0 && s[j] !== s[i]) {
            j = next[j-1];
        }

        // 前缀和后缀相等时
        if (s[j] === s[i]) {
            j++;
        }
        next[i] = j;
    }

    // 最后不应为0，同时最后一个的最长相等公共前缀应该是长度的倍数
    return next[len - 1] !== 0 && len % (len - (next[len - 1])) === 0;
};

实现strStr

地址(opens new window)

// KMP写法
// 1. 判断模式串(needle)中的最长公共相等前后缀
function strStr(haystack: string, needle: string): number {
    if (needle === '') {
        return 0;
    }

    let j = 0;
    let next = [0];
    let jLen = needle.length;

    // 判断该字符在前面出现的坐标
    // 例如ississ
    // 0 0 0 1 2 3
    for (let i = 1, len = jLen; i < len; i++) {

        // 前缀与后缀不相等时
        while (j > 0 && needle[j] !== needle[i]) {
            j = next[j-1];
        }

        // 前缀和后缀相等时
        if (needle[j] === needle[i]) {
            j++;
        }
        next[i] = j;
    }

    j = 0

    // 这里相同的道理 例如 aa b aa f
    // 而needle 为 aa b aa b，当f碰到b的时候，回退到 b看看是否一致，不一致只能回退到0
    for (let i = 0, len = haystack.length; i < len; i++) {

        // 查找next表的位置获取坐标
        while (j > 0 && haystack[i] !== needle[j]) {
            j = next[j-1];
        }
        if (haystack[i] === needle[j]) {
            j++;
        }

        if (j === jLen) {
            return i - jLen + 1;
        }
    }
    return -1;
};

// 不减1情况
function strStr(haystack: string, needle: string): number {
    if (!needle) {
        return 0
    }

    const hLen = haystack.length
    const nLen = needle.length
    let next: number[] = [-1]
    let j = -1

    for (let i = 1; i < nLen; i++) {
        while(j >= 0 && needle[j+1] !== needle[i]) {
            j = next[j]
        }

        if (needle[j+1] === needle[i]) {
            j++
        }

        next[i] = j
    }

    j = -1
    for (let i = 0; i < hLen; i++) {
        while (j >= 0 && needle[j+1] !== haystack[i]) {
            j = next[j]
        }

        if (needle[j+1] === haystack[i]) {
            j++
        }

        if (j >= nLen - 1) {
            return i - nLen + 1
        }
    }
    return -1
};

// 库语法
function strStr(haystack: string, needle: string): number {
    return haystack.indexOf(needle);
};

左旋字符串

地址(opens new window)

function reverseLeftWords(s: string, n: number): string {
    return s.slice(n, s.length) + s.slice(0, n);
};

翻转字符串里的单词

地址(opens new window)

function reverseWords(s: string): string {
    return s.split(' ').reverse().filter(Boolean).join(' ');
};

// 遍历的方式
function reverseWords(s: string): string {
    const len = s.length
    let str = ''
    let i = 0
    while (i < len) {
        if (s[i] !== ' ') {
            let newStr = ''

            // 当不存在空格时
            while(s[i] && s[i] !== ' ') {
                newStr += s[i++]
            }

            str = newStr + ' ' + str
        }

        i++
    }

    return str.slice(0, -1)
};

替换空格

地址(opens new window)

function replaceSpace(s: string): string {
    return s.replace(/\s/g, '%20')
};

反转字符串 II

地址(opens new window)

// 使用数组切割的方式
function reverseStr(s: string, k: number): string {
    if (k === 1) {
        return s;
    }
    let sArr: string[] = s.split('');
    let prev = 0;
    let next = 0;
    let cur = '';
    for (let i = 0, len = s.length; i < len; i += 2 * k) {
        prev = i;
        next = i + k - 1 > len ? len - 1 : i + k - 1;
        while (prev <= next) {
            cur = sArr[prev];
            sArr[prev++] = sArr[next];
            sArr[next--] = cur;
        }
    }

    return sArr.join('');
};

function reverseStr(s: string, k: number): string {
    if (k === 1) {
        return s;
    }
    let sArr = s.split('');
    let prev = 0;
    let next = k - 1;
    let len = s.length;
    let cur;
    while (prev <= next) {
        cur = sArr[prev];
        sArr[prev++] = sArr[next];
        sArr[next--] = cur;

        if (next < prev) {
            prev =  Math.ceil(prev / k) * k + k;
            next = prev + k - 1;

            // 如果剩余字符少于k，那么剩余字符全部反转
            if (len - prev < k) {
                next = len - 1;
            }
        }
    }
    return sArr.join('');
};

// 使用字符串取值
function reverseStr(s: string, k: number): string {
    const len = s.length
    let str = ''
    let i = 0

    while (i < len) {
        let j = Math.min(i + k - 1, len - 1)

        // 先反转k个字符
        while(j >= i) {
            str += s[j--]
        }

        // 把剩余字段加上
        j = i + k
        while(j < (i + 2 * k) && j < len) {
            str += s[j++]
        }

        i += 2 * k
    }

    return str
}

反转字符串

地址(opens new window)

function reverseString(s: string[]): void {
    s.reverse();
};

function reverseString(s: string[]): void {
    let prev = 0;
    let next = s.length - 1;
    while (prev < next) {
        let cur = s[prev];
        s[prev++] = s[next];
        s[next--] = cur;
    }
};

四数之和

地址(opens new window)

function fourSum(nums: number[], target: number): number[][] {
    let len = nums.length;
    if (len < 4) {
        return [];
    }
    const arr = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < len - 3; i++) {
        if (nums[i] === nums[i - 1]) {
            continue;
        }
        for (let j = i + 1; j < len - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue;
            }
            let l = j + 1;
            let r = len - 1;
            while (l < r) {
                let sum = nums[l] + nums[r] + nums[i] + nums[j];
                if (sum < target) {
                    l++;
                    continue;
                }

                if (sum > target) {
                    r--;
                    continue;
                }

                arr.push([nums[i], nums[j], nums[l], nums[r]]);
                while (r > l && nums[r] === nums[--r]);
                while (r > l && nums[l] === nums[++l]);
            }
        }
    }
    return arr;
};

三数之和

地址(opens new window)

// 排序，然后通过双指针的方式获取三数之和
function threeSum(nums: number[]): number[][] {
    let len = nums.length;
    if (len < 3) {
        return [];
    }
    const arr = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < len - 2; i++) {
        if (nums[i] > 0) {
            break;
        }

        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        let l = i + 1;
        let r = len - 1;
        while (l < r) {
            let sum = nums[l] + nums[r] + nums[i];
            if (sum < 0) {
                l++;
                continue;
            }

            if (sum > 0) {
                r--;
                continue;
            }

            arr.push([nums[i], nums[l], nums[r]]);

            while (r > l && nums[r] === nums[--r]);

            while (r > l && nums[l] === nums[++l]);
        }
    }
    return arr;
};

// 采用哈希表的方式存数据
function threeSum(nums: number[]): number[][] {
    let len = nums.length;
    if (len < 3) {
        return [];
    }
    let set = new Set();
    nums.sort();
    for (let i = 0; i < len - 2; i++) {
        if (nums[i] > 0) {
            break;
        }
        let l = i + 1;
        let r = len - 1;
        while (l < r) {
            let sum = nums[l] + nums[r] + nums[i];
            if (sum < 0) {
                l++;
                continue;
            }

            if (sum > 0) {
                r--;
                continue;
            }

            set.add(`${nums[i]},${nums[l]},${nums[r]}`);
            l++;
            r--;
        }
    }
    return [...set].map(item => item.split(','));
};

赎金信

地址(opens new window)

function canConstruct(ransomNote: string, magazine: string): boolean {
    // 先判断进行优化处理
    const rLen = ransomNote.length
    const mLenn = magazine.length

    if (rLen > mLenn) {
        return false
    }

    let map1 = new Map();
    for (const str of magazine) {
        map1.set(str, (map1.get(str) || 0) + 1);
    }

    for (const str of ransomNote) {
        if (!map1.get(str)) {
            return false;
        }
        map1.set(str, map1.get(str) - 1);
    }
    return true;
};

四数之和

地址(opens new window)

减少map

function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    // 两两合并
    let map1 = new Map();
    let n = 0;
    let sum = 0;
    for (const val of nums1) {
        for (const val2 of nums2) {
            sum = val + val2;
            map1.set(sum, (map1.get(sum) || 0) + 1);
        }
    }
    for (const val of nums3) {
        for (const val2 of nums4) {
            sum = val + val2;
            n += map1.get(-sum) || 0;
        }
    }
    return n;
};

map优化循环

function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    // 两两合并
    let map1 = new Map();
    let map2 = new Map();
    let len = nums1.length;
    let n = 0;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            let sum = nums1[i] + nums2[j];
            map1.set(sum, (map1.get(sum || 0) + 1);
            sum = nums3[i] + nums4[j];
            map2.set(sum, (map2.get(sum) || 0) + 1);
        }
    }
    for (const [key, value] of map1.entries()) {
        n += value * (map2.get(-key) || 0)
    }
    return n;
};

遍历（超时）

function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    // 两两合并
    let arr1 = [];
    let arr2 = [];
    let len = nums1.length;
    let n = 0;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            arr1.push(nums1[i] + nums2[j]);
            arr2.push(nums3[i] + nums4[j]);
        }
    }

    len = arr1.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (arr1[i] === -arr2[j]) {
                n++;
            }
        }
    }
    return n;
};

快乐数

地址(opens new window)

function isHappy(n: number): boolean {
    let set = new Set([n]);

    while (n !== 1) {
        n = sum(n);
        if (set.has(n)) {
            return false;
        }
        set.add(n);
    }

    return true;
};

function sum(n: number) {
    let sum = 0;

    while (n) {
        sum += (n % 10) ** 2;
        n = Math.floor(n / 10);
    }
    return sum;
}

function isHappy(n: number): boolean {
    const set = new Set([n])
    let num = n

    while(num !== 1) {
        let result = 0
        for (const val of num.toString()) {
            result += (+val) ** 2
        }

        if (set.has(result)) {
            return false
        }

        set.add(result)
        num = result
    }

    return true
};

两个数组的交集

地址(opens new window)

function intersection(nums1: number[], nums2: number[]): number[] {
    let set = new Set(nums1);
    nums2 = [...new Set(nums2)];
    let arr: number[] = [];
    for (let i = 0, len = nums2.length; i < len; i++) {
        if (set.has(nums2[i])) {
            arr.push(nums2[i]);
        }
    }
    return arr;
};

function intersection(nums1: number[], nums2: number[]): number[] {
    const set = new Set()
    for (const num of nums1) {
        set.add(num)
    }

    // 去重后再筛选数据
    return [...new Set(nums2)].filter(num => set.has(num))
};

查找共用字符

地址(opens new window)

// 整体思想就是先找到第一个字符串每一个字符对应的数量
// 然后逐个遍历剩余字符，拿到相同的字符个数
function commonChars(words: string[]): string[] {
    if (words.length === 1) {
        return words[0].split('')
    }

    let map = new Map<string, number>()

    // 获取第一个字符串的键值
    for (const word of words[0]) {
        map.set(word, (map.get(word) || 0) + 1)
    }

    for (let i = 1; i < words.length; i++) {
        let map1 = new Map()

        for (const word of words[i]) {
            // 如果存在并且
            let value = map.get(word)
            if (value && (map1.get(word) || 0) < value) {
                map1.set(word, (map1.get(word) || 0) + 1)
            }
        }

        map = map1
    }

    const arr: string[] = []
    for (const [key, value] of map) {
        arr.push(...Array(value).fill(key))
    }
    return arr
}

有效的字母异位词

地址(opens new window)

思想都是借助哈希表存数据

function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) {
        return false;
    }
    let mapS = new Map();
    for (let i = 0, len = s.length; i < len; i++) {
        mapS.has(s[i]) ? mapS.set(s[i], mapS.get(s[i]) + 1) : mapS.set(s[i], 1);
        mapS.has(t[i]) ? mapS.set(t[i], mapS.get(t[i]) - 1) : mapS.set(t[i], -1);
    }

    for (const [key, value] of mapS) {
        if (value !== 0) {
            return false;
        }
    }

    return true;
};

function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) {
        return false;
    }
    let arr = Array.from({ length: 26 }, () => 0);

    for (let i = 0, len = s.length; i < len; i++) {
        arr[s[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
        arr[t[i].charCodeAt(0) - 'a'.charCodeAt(0)] -= 1;
    }

    return arr.every(val => val === 0);
};

function isAnagram(s: string, t: string): boolean {
    const sLen = s.length
    const tLen = t.length
    if (sLen !== tLen) {
        return false
    }

    const map = {};
    let charCodeAt = 0
    for (let i = 0; i < sLen; i++) {
        charCodeAt = s[i].charCodeAt(0) - 'a'.charCodeAt(0)
        map[charCodeAt] = (map[charCodeAt] || 0) + 1
    }

    for (let i = 0; i < tLen; i++) {
        charCodeAt = t[i].charCodeAt(0) - 'a'.charCodeAt(0)
        if (!map[charCodeAt]) {
            return false
        }

        map[charCodeAt] -= 1
    }

    return true
};

环形链表 II

地址(opens new window)

// 这里也可以使用set，其实就是存一个变量，然后判断存在该变量
function detectCycle(head: ListNode | null): ListNode | null {
    let map = new Map();
    while (head) {
        if (map.has(head)) {
            return head;
        }
        map.set(head, true);
        head = head.next;
    }
    return null;
};

快慢指针：

1. slow走一步，fast走两步
2. slow与fast相遇的点开始，head与slow开始走，那么一定会在环相遇
3. 环相遇后fast又指向head，然后和slow一起走，再次相遇时就是环的入口了

function detectCycle(head: ListNode | null): ListNode | null {
    let fast = head;
    let slow = head;
    while (slow && fast?.next) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) {
            slow = head;
            while (fast !== slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }

    return null;
};

链表相交

地址(opens new window)

// 思想就是先计算两者的长度
// 计算后的差值先把长点的链表遍历到与短点的链表的相同位置
// 然后一起循环对比
var getIntersectionNode = function(headA, headB) {
    let aLen = 0;
    let bLen = 0;
    let a = headA;
    let b = headB;

    // 获取A的长度
    while (a) {
        a = a.next;
        aLen++;
    }

    // 获取B的长度
    while (b) {
        b = b.next;
        bLen++;
    }

    // 判断A长度和B的长度，然后移动
    if (aLen > bLen) {
        let cur = aLen - bLen;
        while (cur--) {
            headA = headA.next;
        }
    } else {
        let cur = bLen - aLen;
        while (cur--) {
            headB = headB.next;
        }
    }

    // 同时移动，判断是否相等
    while (headA) {
        if (headA === headB) {
            return headA;
        }
        headA = headA.next;
        headB = headB.next;
    }
    return null;
};

// 时间复杂度O(m + n)
// 空间复杂度O(m)
function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    const set = new WeakSet()
    let cur = headA
    while(cur) {
        set.add(cur)
        cur = cur.next
    }

    cur = headB

    while (cur) {
        if (set.has(cur)) {
            return cur
        }
        cur = cur.next
    }
    return cur
};

// 时间复杂度O(m + n)
// 空间复杂度O(1)
function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    let pA = headA
    let pB = headB
    while (pA !== pB) {
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }

    return pA
};

删除链表的倒数第 N 个结点

地址(opens new window)

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    // head为空的情况
    if (!head) {
        return head;
    }

    let fast: ListNode | null = new ListNode(0, head); // 快指针
    let slow: ListNode | null = fast; // 慢指针

    while (n-- && fast) {
        fast = fast.next;
    }

    fast = fast?.next || null; // 还需要再移动一格
    if (!fast) {
        return head.next;
    }

    while (fast) {
        fast = fast.next;
        slow = slow!.next;
    }

    slow!.next = slow!.next?.next || null;

    return head;
};

// 思路就是双指针
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    const newHead = new ListNode(0, head)
    let node = newHead
    let prevNode: ListNode | null = node
    let nextNode: ListNode | null = node
    for(let i = 0; i <= n; i++) {
        // 条件中写明了不会超出n，因此不用担心链表越界问题
        nextNode = nextNode.next
    }

    while(nextNode) {
        prevNode = prevNode.next
        nextNode = nextNode.next
    }

    prevNode.next = prevNode.next.next
    return newHead.next
}

// 不需要加头结点
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    if (!head || !head.next) {
        return null
    }

    let node = head
    let cur: ListNode | null = node
    let next: ListNode | null = node

    while (n > 0 && next) {
        next = next.next
        n--
    }

    if (!next) {
        return node.next
    }

    while (next?.next) {
        next = next.next
        cur = cur!.next
    }

    cur!.next = cur!.next?.next || null
    return node
};

// 栈方法
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    if (!head || !head.next) {
        return null
    }

    const listNode: ListNode[] = []
    let cur: ListNode | null = head
    while(cur) {
        listNode.push(cur)
        cur = cur.next
    }

    if (n === listNode.length) {
        return head.next
    }

    cur = listNode[listNode.length - n - 1]
    cur.next = cur.next?.next || null
    return head
};

两两交换链表中的节点

地址(opens new window)

// 画图，这里注意不能返回原先的head
// 需要加一个空白节点
function swapPairs(head: ListNode | null): ListNode | null {
    // 例如 1 -> 2 -> 3 -> 4 -> 5
    let node = new ListNode(0, head); // 0 ~ 5
    let cur = node;
    let temp = null;
    while (head?.next) {
        temp = head.next.next; // 保存临时变量到 temp = 3 -> 4 -> 5 || temp = 5
        cur.next = head.next; // cur = 0 -> 2 -> 3 -> 4 -> 5 || cur = 1 -> 4 -> 5
        head.next = temp; // head = 1 -> 3 -> 4 -> 5 || head = 3 -> 5
        cur.next.next = head; // cur = 0 -> 2 -> 1 -> 3 -> 4 -> 5 || cur = 1 -> 4 -> 3 -> 5
        cur = cur.next.next; // cur = 1 -> 3 -> 4 -> 5 || cur = 3 -> 5
        head = temp; // head = 3 -> 4 -> 5 || head = 5
    }
    return node.next;
};

反转链表

地址(opens new window)

// 直接遍历，每遍历一次就取值
function reverseList(head: ListNode | null): ListNode | null {
    let cur = null;
    while (head) {
        cur = new ListNode(val, cur);
        head = head.next;
    }
    return cur;
};

// 例如 1->2->3->4->5
// 1. 保存temp 2->3->4->5
// 2. 修改指向 1->prev 即 1-> null prev = null
// 3. prev = cur prev = 1 -> null
// 4. cur = temp，一直循环，直至遍历结束
function reverseList(head: ListNode | null): ListNode | null {
    if (!head?.next) {
        return head;
    }
    let prev = null;
    let cur = head;
    let temp;
    while (cur) {
        temp = cur.next; //  临时存储cur.next
        cur.next = prev;  // 改变cur.next位置
        prev = cur; // 改变prev指向
        cur = temp; // 继续循环
    }
    return prev;
};

// 递归，时间复杂度为O(n)、空间复杂度为O(n)
function reverseList(head: ListNode | null): ListNode | null {
    if (!head || !head.next) {
        return head
    }

    const node = reverseList(head.next)
    head.next.next = head
    head.next = null
    return node
};

设计链表

地址(opens new window)

直接取，相互不关联：

class MyLinkedList {
    head: ListNode | null;
    constructor() {
        this.head = null;
    }

    get(index: number): number {
        let head = this.head;
        while (index && head) {
            head = head.next;
            index--;
        }
        return head ? head.val : -1;
    }

    addAtHead(val: number): void {
        if (!this.head) {
            this.head = {
                val,
                next: null
            }
            return;
        }
        this.head = {
            val,
            next: this.head
        }
    }

    addAtTail(val: number): void {
        if (!this.head) {
            this.head = {
                val,
                next: null
            }
            return;
        }
        let head = this.head;
        while (head.next) {
            head = head.next;
        }
        head.next = {
            val,
            next: null
        }
    }

    addAtIndex(index: number, val: number): void {
        if (index <= 0) {
            this.head = {
                val,
                next: this.head
            }
            return;
        }
        let head = this.head;
        while (index - 1 && head) {
            head = head.next;
            index--;
        }
        head && (head.next = {
            val,
            next: head.next
        });
    }

    deleteAtIndex(index: number): void {
        if (index < 0) {
            return;
        }
        if (index === 0) {
            this.head = this.head?.next || null;
            return;
        }
        let head = this.head;
        while (index - 1 && head) {
            head = head.next;
            index--;
        }
        head?.next && (head.next = head.next.next);
    }
}

相互关联：

class MyLinkedList {
    head: ListNode | null; // 首节点
    size: number;

    constructor() {
        this.head = null; // 链表
        this.size = 0;
    }

    get(index: number): number {
        if (index < 0 || index >= this.size) {
            return -1;
        }
        return this.getNode(index)!.val;
    }

    getNode(index: number) {
        if (index < 0 || index >= this.size) {
            return null;
        }
        let cur = new ListNode(0, this.head); // 加一个虚拟节点
        while (index-- >= 0) {
            cur = cur.next!;
        }
        return cur;
    }

    addAtHead(val: number): void {
        this.head = new ListNode(val, this.head);
        this.size++;
    }

    addAtTail(val: number): void {
        let cur = this.getNode(this.size - 1);
        this.size++;
        if (!cur) {
            this.head = new ListNode(val, null);
            return;
        }
        cur.next = new ListNode(val, null);
    }

    addAtIndex(index: number, val: number): void {
        if (index === 0) {
            this.addAtHead(val);
            return;
        }
        let node = this.getNode(index - 1);
        if (node) {
            node.next = new ListNode(val, node.next);
            this.size++;
        }
    }

    deleteAtIndex(index: number): void {
        if (index === 0 && this.head) {
            this.head = this.head.next;
            this.size--;
            return;
        }

        let node = this.getNode(index - 1);
        if (node && node.next) {
            node.next = node.next.next;
            this.size--;
        }
    }
}

// 使用数组的形式更快
class MyLinkedList {
    arr: number[];

    constructor() {
        // 通过一个数组来控制
        this.arr = []
    }

    get(index: number): number {

        if (index < 0 || index >= this.arr.length) {
            return -1
        }

        return this.arr[index]
    }

    addAtHead(val: number): void {
        this.arr.unshift(val)
    }

    addAtTail(val: number): void {
        this.arr.push(val)
    }

    addAtIndex(index: number, val: number): void {
        if (index > this.arr.length) {
            return
        }

        if (index <= 0) {
            this.arr.unshift(val)
            return
        }

        this.arr.splice(index, 0, val)
    }

    deleteAtIndex(index: number): void {
        if (index < 0 || index > this.arr.length) {
            return
        }

        this.arr.splice(index, 1)
    }
}

移除链表元素

地址(opens new window)

function removeElements(head: ListNode | null, val: number): ListNode | null {
    // 设置一个虚拟节点
    let newHeader = new ListNode(0, head);
    let cur = newHeader;
    // 从第二个节点开始
    while (cur.next) {

        // 如果第二个节点等于要移除的元素，那么跳过第二个节点
        if (val === cur.next.val) {
            cur.next = cur.next.next;
            continue;
        }
        cur = cur.next;
    }

    return newHeader.next;
};

// 没有虚拟节点
function removeElements(head: ListNode | null, val: number): ListNode | null {
    if (head === null) {
        return head;
    }
    let cur = head;
    while (cur.next) {
        if (val === cur.next.val) {
            cur.next = cur.next.next;
            continue;
        }
        cur = cur.next;
    }

    return head.val === val ? head.next : head;
};

螺旋矩阵 II

地址(opens new window)

进一步优化：

function generateMatrix(n: number): number[][] {
    let arr: number[][] = [...Array.from({ length: n }, () => [])];
    let prev = 0;
    let val = 1; // 初始值
    let next = n - 1;
    while(prev < next) {
        let des = next - prev; // 差值
        // 从左到右，从上到下，从右到左，从下到上
        for (let j = prev; j < next; j++) {
            arr[prev][j] = val;
            arr[j][next] = val + des;
            arr[next][next+prev-j] = val + 2 * des
            arr[next+prev-j][prev] = val + 3 * des;
            val++;
        }
        val += 3 * des;
        prev++;
        next--;
    }

    // 如果prev和next相等了
    if (prev === next) {
        arr[prev][next] = val;
    }
    return arr;
};

最开始写法，可能比较好理解：

function generateMatrix(n: number): number[][] {
    let arr: number[][] = [...Array.from({ length: n }, () => [])];
    let prev = 0;
    let val = 1; // 初始值
    let next = n - 1;
    while(prev < next) {

        // 从左到右
        for (let j = prev; j < next; j++) {
            arr[prev][j] = val++;
        }

        // 从上到下
        for (let j = prev; j < next; j++) {
            arr[j][next] = val++;
        }

        // 从右到左
        for (let j = next; j > prev; j--) {
            arr[next][j] = val++;
        }

        // 从下到上
        for (let j = next; j > prev; j--) {
            arr[j][prev] = val++;
        }

        prev++;
        next--;
    }

    // 如果prev和next相等了
    if (prev === next) {
        arr[prev][next] = val;
    }
    return arr;
};

长度最小的子数组

采用了滑动窗口的思想，sum为加和的值，一旦sum超过了target，那么prev就需要移动了，移动的值为sum一直减后小于target的值

function minSubArrayLen(target: number, nums: number[]): number {
    let sum = 0;
    let minIndexLen = Number.MAX_SAFE_INTEGER; // 先设置了极大值
    let prev = 0; // 前面的位置
    for (let i = 0, len = nums.length; i < len; i++) {
        sum += nums[i];
        while (sum >= target) {
            // 判断哪一个最小
            minIndexLen = Math.min(minIndexLen, i - prev + 1);
            sum -= nums[prev++];
        }
    }
    return minIndexLen === Number.MAX_SAFE_INTEGER ? 0 : minIndexLen;
};

// 查看加上该值后是否大于target
function minSubArrayLen(target: number, nums: number[]): number {
    const len = nums.length
    let minLen = Infinity
    let sum = 0
    let index = 0 // 序号
    for (let i = 1; i <= len; i++) {
        if (minLen === 1) {
            return 1
        }

        sum += nums[i-1]

        if (sum >= target) {
            // 减到小于该target时
            while(index < i && sum >= target) {
                sum -= nums[index++]
            }

            // index + 1的原因是加上后才能大于或等于target
            minLen = Math.min(minLen, i - index + 1)
        }
    }

    return minLen === Infinity ? 0 : minLen
};

有序数组的平方

地址(opens new window)

// 使用双指针法
// left为左边
// right为右边
// 然后比较判断Math.abs(left)与Math.abs(right)的差异
function sortedSquares(nums: number[]): number[] {
    const len = nums.length
    const result: number[] = []
    let left = 0
    let right = len - 1
    while (right >= left) {
        if (Math.abs(nums[right]) > Math.abs(nums[left])) {
            result.unshift(nums[right] ** 2)
            right--
        } else {
            result.unshift(nums[left] ** 2)
            left++
        }
    }

    return result
};

// 暴力破解
function sortedSquares(nums: number[]): number[] {
    return nums.map(i => i**2).sort((a, b) => a - b)
}

移除元素

地址(opens new window)

function removeElement(nums: number[], val: number): number {
    let index = 0;
    while (index < nums.length) {
        if (nums[index] === val) {
            nums.splice(index, 1);
        } else {
            index++;
        }
    }
    return nums.length;
};

// 双指针
function removeElement(nums: number[], val: number): number {
    let fast = 0
    let slow = 0
    const len = nums.length
    while(fast < len) {
        if (nums[fast] !== val) {
            nums[slow++] = nums[fast]
        }
        fast++
    }
    return slow
};

二分查找

function search(nums: number[], target: number): number {
  // 二分查找，左闭右闭
  let prev = 0;
  let next = nums.length - 1;
  while (prev <= next) {
    let half = Math.floor((prev + next) / 2);
    if (nums[half] > target) {
      next = half - 1;
    } else if (nums[half] < target) {
      prev = half + 1;
    } else {
      return half;
    }
  }
  return -1;
};

左闭右闭

// 先取中间，然后与target对比，采用[start, end]的方式
// 1. 如果nums[mid] = target mid
// 2. nums[mid] > target，那么end = mid - 1
// 3. nums[mid] < target，那么start = mid + 1
function search(nums: number[], target: number): number {
  const len = nums.length
  let end = len - 1
  let start = 0

  while (end >= start) {
    let mid = Math.floor((end + start) / 2)
    if (nums[mid] === target) {
      return mid
    }

    if (nums[mid] > target) {
      end = mid - 1
    } else {
      start = mid + 1
    }
  }
  return -1
}

左闭右开

// 先取中间，然后与target对比，采用[start, end)的方式
// 1. 如果nums[mid] = target mid
// 2. nums[mid] > target，那么end = mid
// 3. nums[mid] < target，那么start = mid + 1
function search(nums: number[], target: number): number {
  const len = nums.length
  let end = len
  let start = 0

  while (end > start) {
    let mid = Math.floor((end + start) / 2)
    if (nums[mid] === target) {
      return mid
    }

    if (nums[mid] > target) {
      end = mid
    } else {
      start = mid + 1
    }
  }
  return -1
}

两数之和

通过hash表得到对应的值

function twoSum(nums: number[], target: number): number[] {
  let map = new Map();
  for (let i = 0, len = nums.length; i < len; i++) {
     if (map.has(nums[i])) {
         return [map.get(nums[i]), i];
     }
     map.set(target - nums[i], i);
  }
};

无重复字符的最长子串

地址(opens new window)

function lengthOfLongestSubstring(s: string): number {
  let max = 0;
  let map = new Map();
  let prevIndex = 0;
  // 循环该字符
  for (let i = 0, len = s.length; i < len; i++) {

      // 判断是否存在该元素，存在的话则向右滑动
      if (map.has(s[i]) && map.get(s[i]) >= prevIndex) {
          prevIndex = map.get(s[i]) + 1;
      }
      max = Math.max(max, i - prevIndex + 1);
      map.set(s[i], i);
  }
  return max;
};

字符串相加

function addStrings(num1: string, num2: string): string {
  // 判断哪一个最长，较短的使用0补足
  let len1 = num1.length;
  let len2 = num2.length;
  if (len1 < len2) {
    num1 = num1.padStart(len2, '0');
  } else {
    num2 = num2.padStart(len1, '0');
  }

  // 对数字进行循环，从最后一项开始相加
  let str = '';
  let n = 0; // 过程中如果大于10需要
  for (let i = num1.length - 1; i >= 0; i--) {
      let m = Number(num1[i]) + Number(num2[i]) + n;
      str = m % 10 + str;
      n = Math.floor(m / 10);
  }

  // 如果n还有保留，则需要整体加1
  if (n === 1) {
    str = n + str;
  }
  return str;
};

思路参考

代码随想录(opens new window)