力扣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
}, [])
};贡献者
PinkDopeyBug版权所有
版权归属：
