# 10.算法
# 1.两数之和 (opens new window)
var twoSum = function (nums, target) {
const obj = {}
for (let i = 0; i < nums.length; i++) {
const num = target - nums[i]
if (obj[num] !== undefined) {
return [obj[num], i]
}
obj[nums[i]] = i
}
}
# 2.全排列 (opens new window)
var permute = function (nums) {
const res = []
function backTrack(path) {
if (path.length === nums.length) {
res.push([...path])
}
for (let num of nums) {
if (!path.includes(num)) {
path.push(num)
backTrack(path)
path.pop()
}
}
}
backTrack([])
return res
}
# 3.二叉树的前序遍历 (opens new window)
var preorderTraversal = function (root) {
if (!root) return []
const stk = [root], res = []
while (stk.length) {
let node = stk.pop()
res.push(node.val)
if (node.right) stk.push(node.right)
if (node.left) stk.push(node.left)
}
return res
}
# 4.无重复字符的最长子串 (opens new window)
var lengthOfLongestSubstring = function (s) {
let left = 0, right = 0, count = 0;
const window = {}
while (right < s.length) {
const c = s[right++]
window[c] = (window[c] || 0) + 1
while (window[c] > 1) {
const d = s[left++]
window[d]--
}
count = Math.max(count, right - left)
}
return count
}
# 5.反转链表 (opens new window)
var reverseList = function (head) {
let prev = null, curr = head
while (curr) {
const next = curr.next
curr.next = prev
prev = curr
curr = next
}
return prev
}
# 6.最长连续序列 (opens new window)
var longestConsecutive = function (nums) {
const set = new Set(nums)
let count = 0
for (let num of nums) {
if (!set.has(num - 1)) {
let val = num + 1
while (set.has(val)) val++
count = Math.max(count, val - num)
}
}
return count
}
# 7.爬楼梯 (opens new window)
var climbStairs = function (n) {
if (n < 3) return n
let a = 1, b = 2
for (let i = 3; i <= n; i++) {
[a, b] = [b, a + b]
}
return b
}
# 8.数组中的第K个最大元素 (opens new window)
var findKthLargest = function (nums, k) {
return nums.sort((a, b) => b - a)[k - 1]
}
# 9.合并两个有序数组 (opens new window)
var merge = function (nums1, m, nums2, n) {
let i = m - 1
let j = n - 1
let k = m + n - 1
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k] = nums1[i]
i--
} else {
nums1[k] = nums2[j]
j--
}
k--
}
while (j >= 0) {
nums1[k] = nums2[j]
j--
k--
}
}
# 10.两个数组的交集 II (opens new window)
var intersect = function (nums1, nums2) {
const obj = {}
const res = []
nums1.forEach(item => {
if (obj[item]) {
obj[item] = obj[item] + 1
} else {
obj[item] = 1
}
})
nums2.forEach(item => {
if (obj[item]) {
res.push(item)
obj[item]--
}
})
return res
}
# 11.有效的括号 (opens new window)
var isValid = function (s) {
const stk = []
const obj = {
']': '[',
'}': '{',
')': '('
}
for (let ch of s) {
if (obj[ch]) {
const ele = stk.pop()
if (obj[ch] !== ele) {
return false
}
} else {
stk.push(ch)
}
}
return stk.length === 0
}
# 12.最长公共前缀 (opens new window)
var longestCommonPrefix = function (strs) {
let prefix = strs[0]
for (let i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) !== 0) {
prefix = prefix.substring(0, prefix.length - 1)
if (prefix === '') {
return ''
}
}
}
return prefix
}
# 13.最长回文子串 (opens new window)
var longestPalindrome = function (s) {
let res = ''
for (let i = 0; i < s.length; i++) {
const oddStr = expandCenter(s, i, i)
const evenStr = expandCenter(s, i, i + 1)
res = res.length > oddStr.length ? res : oddStr
res = res.length > evenStr.length ? res : evenStr
}
return res
}
function expandCenter(s, left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--
right++
}
return s.substring(left + 1, right)
}
# 14.二叉树的最近公共祖先 (opens new window)
var lowestCommonAncestor = function (root, p, q) {
if (!root || root === p || root === q) return root
let left = lowestCommonAncestor(root.left, p, q)
let right = lowestCommonAncestor(root.right, p, q)
if (left && right) {
return root
}
if (left) {
return left
}
if (right) {
return right
}
return null
}
# 15.二叉树中序遍历 (opens new window)
var inorderTraversal = function (root) {
if (!root) return []
const stk = [], res = []
let node = root
while (stk.length || node) {
while (node) {
stk.push(node)
node = node.left
}
node = stk.pop()
res.push(node.val)
node = node.right
}
return res
}
# 16.二叉树后序遍历 (opens new window)
var postorderTraversal = function (root) {
if (!root) return []
const stk = [root], res = []
// 左右中
// 中左右 => 中右左 => 左右中
while (stk.length) {
const node = stk.pop()
res.push(node.val)
if (node.left) stk.push(node.left)
if (node.right) stk.push(node.right)
}
return res.reverse()
}
# 17.二叉树层序遍历 (opens new window)
var levelOrder = function (root) {
if (!root) return []
const q = [root], res = []
while (q.length) {
const levelRes = [], len = q.length
for (let i = 0; i < len; i++) {
const node = q.shift()
levelRes.push(node.val)
if (node.left) q.push(node.left)
if (node.right) q.push(node.right)
}
res.push(levelRes)
}
return res
}
# 18.二叉树的直径 (opens new window)
var diameterOfBinaryTree = function (root) {
let count = 0
function getDiameter(node) {
if (!node) return 0
let left = getDiameter(node.left)
let right = getDiameter(node.right)
count = Math.max(count, left + right)
return Math.max(left, right) + 1
}
getDiameter(root)
return count
}
# 19.二叉树的最大深度 (opens new window)
var maxDepth = function (root) {
if (!root) return 0
const q = [root]
let count = 0
while (q.length) {
const levelSize = q.length
for (let i = 0; i < levelSize; i++) {
let node = q.shift()
if (node.left) q.push(node.left)
if (node.right) q.push(node.right)
}
count++
}
return count
}
# 20.接雨水 (opens new window)
var trap = function (height) {
let left = 0, right = height.length - 1, count = 0;
let leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left])
rightMax = Math.max(rightMax, height[right])
if (leftMax < rightMax) {
count += leftMax - height[left]
left++
} else {
count += rightMax - height[right]
right--
}
}
return count
}
# 21.盛最多水的容器 (opens new window)
var maxArea = function (height) {
let left = 0, right = height.length - 1;
let maxArea = 0;
while (left < right) {
let minHeight = Math.min(height[left], height[right])
maxArea = Math.max(maxArea, minHeight * (right - left))
if (height[left] < height[right]) {
left++
} else {
right--
}
}
return maxArea
}
# 22.冒泡排序 (opens new window)
var bubbleSort = function (arr) {
const len = arr.length - 1
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
return arr
}
# 23.插入排序 (opens new window)
function insertionSort(nums) {
for (let i = 1; i < nums.length; i++) {
for (j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
[nums[j - 1], nums[j]] = [nums[j], nums[j - 1]]
}
}
}
# 24.三数之和 (opens new window)
var threeSum = function (nums) {
// 1.对数组进行排序
nums.sort((a, b) => a - b)
const res = []
// 2.遍历数组
for (let i = 0; i < nums.length - 2; i++) {
// 数字相同的话跳过循环
if (i > 0 && nums[i] === nums[i - 1]) continue
// 设置双指针
let left = i + 1
let right = nums.length - 1
// 双指针内部循环
while (left < right) {
let sum = nums[i] + nums[left] + nums[right]
if (sum === 0) {
res.push([nums[i], nums[left], nums[right]])
// 跳过重复数字
while (nums[left] === nums[++left]);
while (nums[right] === nums[--right]);
} else if (sum < 0) {
left++
} else {
right--
}
}
}
return res
};
# 25.删除链表的倒数第 N 个结点 (opens new window)
// 双指针
function listNode(head, n) {
const dummy = new ListNode(0, head)
let first = dummy
let second = dummy
for (let i = 0; i < n + 1; i++) {
first = first.next
}
while (first !== null) {
first = first.next
second = second.next
}
second.next = second.next.next
return dummy.next
}
# 26.删除排序链表中的重复元素 (opens new window)
function listNode(head) {
let current = head
while (current && current.next) {
if (current.val === current.next.val) {
current.next = current.next.next
} else {
current = current.next
}
}
return head
}
# 27.删除排序链表中的重复元素 II (opens new window)
function deleteDuplicates(head) {
const dummy = new ListNode(0, head)
let prev = dummy
let current = head
while (current) {
let flag = false
while (current.next && current.val === current.next.val) {
flag = true
current = current.next
}
if (flag) {
prev.next = current.next
} else {
prev = current
}
current = current.next
}
return dummy.next
}
# 28.旋转链表 (opens new window)
function rotateRight(head, k) {
if (!head || !head.next || k === 0) return head
// 计算链表长度
let oldTail = head
let n = 1
while (oldTail.next) {
oldTail = oldTail.next
n++
}
// 计算链表需要移动的真实步数
let steps = n - k % n
// 将链表变成循环链表
oldTail.next = head
// 找到新的头部和尾部并断开
let newTail = head
for (let i = 1; i < steps; i++) {
newTail = newTail.next
}
let newHead = newTail.next
newTail.next = null
return newHead
}
# 29.翻转二叉树 (opens new window)
function invertTree(root) {
if (!root) return null
[root.left, root.right] = [root.right, root.left]
invertTree(root.left)
invertTree(root.right)
return root
}
# 30.对称二叉树 (opens new window)
function isSymmetric(root) {
if (!root) return true
const queue = [root.left, root.right]
while (queue.length) {
const node1 = queue.shift()
const node2 = queue.shift()
if (!node1 && !node2) continue;
if (!node1 || !node2) return false
if (node1.val !== node2.val) return false
queue.push(node1.left, node2.right, node1.right, node2.left)
}
return true
}
# 31.二叉树的右视图 (opens new window)
function rightSideView(root) {
if (!root) return [];
// 层序
const queue = [root]
const res = []
while (queue.length) {
const levelSize = queue.length
for (let i = 0; i < levelSize; i++) {
const node = queue.shift()
if (i === levelSize - 1) {
res.push(node.val)
}
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
}
}
return res
}
# 32.二叉树展开为链表 (opens new window)
function flatten(root) {
if (!root) return;
const stack = [root]
let prev = null
while (stack.length) {
const node = stack.pop()
if (prev) {
prev.right = node
prev.left = null
}
if (node.right) stack.push(node.right)
if (node.left) stack.push(node.left)
prev = node
}
}
# 33.从前序与中序遍历序列构造二叉树 (opens new window)
function buildTree(preorder, inorder) {
let preIndex = 0;
const map = new Map()
for (let i = 0; i < inorder.length; i++) {
map.set(inorder[i], i)
}
function constructTree(left, right) {
if (left > right) return null;
const rootVal = preorder[preIndex++]
const root = new TreeNode(rootVal)
const index = map.get(rootVal)
root.left = constructTree(left, index - 1)
root.right = constructTree(index + 1, right)
return root
}
return constructTree(0, inorder.length - 1)
}
# 34.二叉树中的最大路径和 (opens new window)
function maxPathSum(root) {
let maxSum = Number.MIN_SAFE_INTEGER;
function dfs(node) {
if (!node) return 0;
const leftPath = Math.max(dfs(node.left), 0)
const rightPath = Math.max(dfs(node.right), 0)
const newPathSum = node.val + leftPath + rightPath
maxSum = Math.max(maxSum, newPathSum)
return node.val + Math.max(leftPath, rightPath)
}
dfs(root)
return maxSum
}
# 35.字母异位词分组 (opens new window)
var groupAnagrams = function (strs) {
const map = {}
for (let str of strs) {
let sorted = str.split('').sort().join()
if (!map[sorted]) {
map[sorted] = []
}
map[sorted].push(str)
}
return Object.values(map)
}
# 36.快速排序 (opens new window)
解题思路：
1.将序列分为较大和较小的两个子序列
2.选取一个基准值对序列进行拆分
3.通过与基准值比大小递归排序子序列
function quickSort(arr) {
if (arr.length <= 1) return arr
const len = arr.length - 1
const pivot = arr[len]
const left = []
const right = []
for (let i = 0; i < len; i++) {
if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...quickSort(left), pivot, ...quickSort(right)]
}
const array = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSort(array));
# 37.比较版本号 (opens new window)
var compareVersion = function (version1, version2) {
const v1 = version1.split('.').map(item => Number(item))
const v2 = version2.split('.').map(item => Number(item))
for (let i = 0; i < Math.max(v1.length, v2.length); i++) {
const num1 = v1[i] || 0
const num2 = v2[i] || 0
if (num1 > num2) return 1
if (num1 < num2) return -1
}
return 0
};