力扣2
排序后只比较第一个和最后一个字符串，因为默认按字典排序，它们的差异最大只需要比较它们即可，会有额外的空间开销，也可以手动对比，但性能开销更大
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
};贡献者
PinkDopeyBug版权所有
版权归属：
