力扣2

约 2398 字大约 8 分钟

2026-02-25

排序后只比较第一个和最后一个字符串，因为默认按字典排序，它们的差异最大只需要比较它们即可，会有额外的空间开销，也可以手动对比，但性能开销更大

function longestCommonPrefix(strs: string[]): string {
  if (strs.length == 0) return ''
  if (strs.length == 1) return strs[0]

  let i = 0
  strs.sort()
  const start = strs[0]
  const end = strs[strs.length - 1]

  for (; i < start.length && start[i] == end[i]; i++) { }
  return strs[0].slice(0, i)
};

226. 翻转二叉树 - 力扣（LeetCode）

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null
  invertTree(root.left)
  invertTree(root.right)
  const temp = root.left
  root.left = root.right
  root.right = temp

  return root
};

1556. 千位分隔数 - 力扣（LeetCode）

function thousandSeparator(n: number): string {
  const temp = String(n)
  let res = ''
  for (let i = temp.length; i > 0; i -= 3) {
    const str = temp.slice(i - 3 < 0 ? 0 : i - 3, i)
    res = str + '.' + res
  }
  return res.slice(0, res.length - 1)
};

62. 不同路径 - 力扣（LeetCode）

直接深搜时间过长会超时需要使用二维动态规划，每一格的路径个数等于它左边一格和上边一个路径个数之和

function uniquePaths(m: number, n: number): number {
  const dp = []
  for (let i = 0; i < m; ++i) {
    dp.push(new Array(n).fill(1))
  }
  for (let i = 1; i < m; ++i) {
    for (let j = 1; j < n; ++j) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    }
  }
  return dp[m - 1][n - 1]
};

283. 移动零 - 力扣（LeetCode）

function moveZeroes(nums: number[]): void {
  for (let i = 0; i < nums.length; ++i) {
    if (nums[i] === 0) {
      for (let j = i + 1; j < nums.length; ++j) {
        if (nums[j] !== 0) {
          nums[i] = nums[j]
          nums[j] = 0
          break
        }
      }
    }
  }
};

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

先利用深搜遍历节点，存储下根节点到p和q的路径，接着遍历两个数组，相同就记录，不同就跳出

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
  let pathP: TreeNode[] = [] // 根节点到节点p的路径
  let pathQ: TreeNode[] = [] // 根节点到节点q的路径
  const temp: TreeNode[] = [] // 暂存路径
  function dfs(node: TreeNode | null) {
    if (!node) return
    temp.push(node)
    if (node === p) {
      pathP = Array.from(temp)
    } else if (node === q) {
      pathQ = Array.from(temp)
    }
    dfs(node.left)
    dfs(node.right)

    temp.pop()
  }
  dfs(root)

  let res: TreeNode | null = null
  for (let i = 0; i < Math.min(pathP.length, pathQ.length); ++i) {
    if (pathP[i] === pathQ[i]) {
      res = pathP[i]
    } else break
  }
  return res
};

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

层序遍历，适时反转

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  const res: number[][] = []
  if (!root) return res

  const queue: TreeNode[] = []
  queue.push(root)

  while (queue.length > 0) {
    const temp: number[] = []
    const size = queue.length
    for (let i = 0; i < size; ++i) {
      const node = queue.shift()
      if (node) {
        temp.push(node?.val)
        if(node.left) queue.push(node.left)
        if(node.right) queue.push(node.right)
      }
    }
    if (res.length % 2 === 0) {
      res.push(temp)
    } else {
      res.push(temp.reverse())
    }
  }
  return res
};

2. 两数相加 - 力扣（LeetCode）

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const head = new ListNode()
  let cur = head
  let carry = 0
  while (l1 || l2 || carry) {
    const res = (l1?.val || 0) + (l2?.val || 0) + carry
    carry = Math.floor(res / 10)
    const node = new ListNode(res % 10)

    // 移动指针
    cur.next = node
    cur = node

    if (l1) l1 = l1.next
    if (l2) l2 = l2.next
  }
  return head.next
};

209. 长度最小的子数组 - 力扣（LeetCode）

滑动窗口

function minSubArrayLen(target: number, nums: number[]): number {
  let res = nums.length + 1, sum = 0, left = 0, right = 0
  for (; right < nums.length; ++right) {
    sum += nums[right]
    while (sum >= target) {
      res = Math.min(res, right - left + 1)
      sum -= nums[left]
      ++left
    }
  }
  return res === nums.length + 1 ? 0 : res
};

394. 字符串解码 - 力扣（LeetCode）

单调栈

function decodeString(s: string): string {
  const stack = []
  for (let i = 0; i < s.length; ++i) {
    if (s[i] !== ']') {
      stack.push(s[i])
    } else {
      let str = ''
      let temp = ''
      while (stack[stack.length - 1] !== '[') {
        temp = stack.pop()!
        str = temp + str
      }
      stack.pop()
      let num = ''
      while (!Number.isNaN(Number(stack[stack.length - 1]))) {
        temp = stack.pop()!
        num = temp + num
      }
      let el = ''
      for (let i = 0; i < parseInt(num); ++i) {
        el += str
      }
      stack.push(el)
    }
  }
  return stack.join('')
};

101. 对称二叉树 - 力扣（LeetCode）

层序遍历判断

function isSymmetric(root) {
  if (!root) return true

  const queue = []
  queue.push([root.left, root.right])
  while (queue.length > 0) {
    const [left, right] = queue.shift()

    if (!left && !right) continue
    if (!left && right || left && !right) return false
    if (left.val === right.val) {
      queue.push([left.left, right.right])
      queue.push([left.right, right.left])
    } else {
      return false
    }
  }
  return true
};

155. 最小栈 - 力扣（LeetCode）

两个栈，第一个栈正常存储元素，第二个栈存储第一个栈每一位对应最小的元素，如：stack1=[-3,0,-2] stack2=[-3,-2,-2]

199. 二叉树的右视图 - 力扣（LeetCode）

将二叉树层序遍历后取每一层（数组）最右（后）的值

function rightSideView(root: TreeNode | null): number[] {
  const ans: number[][] = []
  function travel(node: TreeNode | null, level: number) {
    if (!node) return
    if (ans[level]) {
      ans[level].push(node.val)
    } else {
      ans[level] = [node.val]
    }

    travel(node.left, level + 1)
    travel(node.right, level + 1)
  }
  travel(root, 0)
  return ans.reduce((acc, cur) => {
    acc.push(cur[cur.length - 1])
    return acc
  }, [])
};

198. 打家劫舍 - 力扣（LeetCode）

动态规划到每间房子可以选择偷当前房子的收益加上前第二间房的收益，也可以选择不偷当前房子偷前一间房子从第二间可以就可以比较偷当前房子收益大还是偷前一间房子收益大状态转移方程：Math.max(dp[i - 1], dp[i - 2] + dp[i])

function rob(nums: number[]): number {
  if (nums.length == 1) return nums[0]
  const dp = Array.from(nums)
  dp[1] = Math.max(dp[0], dp[1])
  for (let i = 2; i < nums.length; ++i) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + dp[i])
  }
  return dp[dp.length - 1]
};

160. 相交链表 - 力扣（LeetCode）

可以遍历两个链表并将它们的节点记录到两个数组中，再将数组从后往前遍历直到遇到不相等的节点，但时间复杂度和空间复杂度都是O(m+n) 另一个思路是设置两个指针从前往后遍历，第一个链表的指针走到末尾时将指针指向第二个链表的头，第二个链表的指针走到末尾时将指针指向第一个链表的头。这样遍历两次后它们的走过的路径就相等了，判断它们是否相等即可

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  let h1 = headA
  let h2 = headB
  while (h1 !== h2) {
    if (h1) {
      h1 = h1.next
    } else {
      h1 = headB
    }
    if (h2) {
      h2 = h2.next
    } else {
      h2 = headA
    }
  }
  return h1
};

718. 最长重复子数组 - 力扣（LeetCode）

二维动态规划设置一个二维数组，双层循环，如果nums1[i] === nums2[j]则表示两个数组中找到了公共数，再判断公共数的dp[i - 1][j - 1]公共数长度，在当前+1，对角线相连即为连续的数组。记录dp中的最大值就是最长重复子数组长度状态转移方程：dp[i][j] = (dp[i - 1]?.[j - 1] || 0) + 1

function findLength(nums1: number[], nums2: number[]): number {
  const dp: number[][] = []
  for (const key in nums1) {
    dp.push(new Array(nums2.length).fill(0))
  }

  let res = 0
  for (let i = 0; i < nums1.length; ++i) {
    for (let j = 0; j < nums2.length; ++j) {
      if (nums1[i] === nums2[j]) {
        dp[i][j] = (dp[i - 1]?.[j - 1] || 0) + 1
        res = Math.max(res, dp[i][j])
      }
    }
  }
  return res
};

125. 验证回文串 - 力扣（LeetCode）

前后双指针，遇到特殊字符跳过也可以将字符串特殊字符去除获得一个数组再判断，但时间和空间复杂度都是on

function isPalindrome(s: string): boolean {
  let left = 0, right = s.length - 1
  const reg = /[a-z0-9A-Z]/
  while (left < right) {
    while (left < right && !reg.test(s[left])) {
      ++left
    }
    while (left < right && !reg.test(s[right])) {
      --right
    }
    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false
    }
    ++left
    --right
  }
  return true
};

49. 字母异位词分组 - 力扣（LeetCode）

可以遍历数组将每个字符串排序，排序默认按字典排这里使用哈希表的思想，设置一个长度为26（26个单词），遍历字符串，将里面的每个字符转成unicode编码和z的unicode编码相减就是在哈希表的上偏移量，并对上面的值+1，字母异位词得到的哈希表都是相同的，将哈希表转成字符串当作键，键相同就是字母异位词

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>()
  strs.forEach((str, index) => {
    const key = new Array(26).fill(0)
    for (const char of str) {
      ++key['z'.codePointAt(0)! - char.codePointAt(0)!]
    }
    if (map.has(key.toString())) {
      map.get(key.toString())?.push(str)
    } else {
      map.set(key.toString(), [str])
    }
  })

  const res: string[][] = []
  map.forEach((item, index) => {
    res.push(item)
  })
  return res
};

128. 最长连续序列 - 力扣（LeetCode）

先排序再判断时间复杂度nlogn 将数组转换成集合，再遍历判断当前值-1是否在集合中，如果在就表示当前值是连续序列的起始位置，那么就再判断当前值一直+1记录长度，直到不在集合中。如果当前值-1在集合中，那么就表示当前值不是连续序列的起始位置就跳过（因为从起始位置开始计算已经计算过了非起始位置的数据）

function longestConsecutive(nums: number[]): number {
  let res = 0
  const set = new Set(nums)
  set.forEach((item, index) => {
    if (!set.has(item - 1)) {
      let len = 1
      while (set.has(item + len)) {
        ++len
      }
      res = Math.max(res, len)
    }
  })
  return res
};

11. 盛最多水的容器 - 力扣（LeetCode）

暴力枚举会超时设置左右双指针，每次计算完成之后移动容器的短板（移动长板容积一定变小，移动短板容积可能变大）

function maxArea(height: number[]): number {
  let res = 0
  let left = 0, right = height.length - 1

  while (left < right) {
    let area = (right - left) * Math.min(height[left], height[right])
    res = Math.max(res, area)
    if (height[left] < height[right]) {
      ++left
    } else {
      --right
    }
  }
  return res
};

双指针滑动窗口实现，将p的26个英文字母做哈希映射，右指针往后移动直到超出p的长度在将左指针往后移动，移动时判断对应位置的哈希值是否相同

function findAnagrams(s: string, p: string): number[] {
  const need = new Array(26).fill(0)
  for (const char of p) {
    ++need[char.codePointAt(0)! - 'a'.codePointAt(0)!]
  }
  const count = need.filter(value => value > 0).length

  const window = new Array(26).fill(0)
  let left = 0, len = 0
  const res: number[] = []

  for (let right = 0; right < s.length; ++right) {
    const index = s[right].codePointAt(0)! - 'a'.codePointAt(0)!
    ++window[index]

    if (window[index] === need[index]) ++len
    if (right - left + 1 > p.length) {
      const lIndex = s[left].codePointAt(0)! - 'a'.codePointAt(0)!
      if (window[lIndex] === need[lIndex]) --len
      --window[lIndex]
      ++left
    }
    if ((right - left + 1 === p.length) && len === count) res.push(left)
  }
  return res
};

贡献者

PinkDopeyBug

版权所有

版权归属：wynnsimon

许可证：署名 4.0 国际 (CC-BY-4.0)

力扣2

公告