常见算题

概述

• 哈希表：js通过Map/Set结构模拟哈希表结构
• 链表：递归+迭代 两种遍历方式
• 二叉树：广度BFS（Breadth-First-Search）（迭代）+ 深度优先DFS（Deth-First-Search）（递归） 两种遍历方式

• 斐波那契数列：迭代+递归

  // 迭代
  const fib = n => {
    if (n < 2) return n
  let [pre, cur, next] = [0, 0, 1]
  for (let i = 1; i < n; i++) {
      pre = cur
    cur = next
    next = pre + cur
  }
  return next
  }

• 动态规划：滑动窗口

  题目

• offer18：删除链表节点-> 迭代+递归

• offer22: 取链表倒数k个节点 -> 迭代（快慢指针+正常迭代获取）
• offer25：合并两个链表 -> 迭代（比较值大小合并即可）
• offer61: 扑克牌中的顺子 -> 排序: max - min < 5
• offer55: 二叉树深度 -> 递归

1. 链表：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

// 算法一：迭代
var reverseList = function(head) {
  let [pre, cur] = [null, head]
  while(cur) {
      let next = cur.next
    cur.next = pre
    pre = cur
    cur = next
  }
  return pre
}
// 算法二：递归
var reverseList = function(head) {
  if (!head || !head.next) return head
  const res = reverseList(head.next)
  head.next.next = head
  head.next = null
  return res
}

2. 二分查找：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

// 方法一
var missingNumber = function(nums) {
  for (let i = 0; i <= nums; i++) {
      if (nums[i] !== i) {
        return i
    }
  }
}
// 方法二：二分法
var missingNumber = function(nums) {
    let [l, r] = [0, nums.length-1]
    while(l <= r) {
        let m = Math.floor((l + r) / 2)
        if (nums[m] === m) {
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return l
}

3. 二叉树：遍历二叉树

// 广度优先：迭代
var levelOrder = function(root) {
    if (!root) return []
    let queue = [root]
    let res = []
    while(queue.length) {
        let n = queue.shift()
        res.push(n.val)
        n.left && queue.push(n.left)
        n.right && queue.push(n.right)
    }
    return res
}
// 深度优先：递归
var levelOrder = function(root) {
    if (!root) return null
    console.log(root.val)
    levelOrder(root.left)
    levelOrder(root.right)
}

4. 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

// 广度：迭代
// 深度：递归
var isSubStructure = function(A, B) {
    if (!A || !B) return false
    const dfs = (A, B) => {
        if (!B) return true
        if (!A) return false
        return A.val === B.val && dfs(A.left, B.left) && dfs(A.right, B.right)
    }
    return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
};

5. 动态规划：输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值

// f(i)前是正向收益则加入，否则舍弃
var maxSubArray = function(nums) {
    let [max, tempMax] = [nums[0], 0]
    nums.forEach(x => {
        tempMax = Math.max(tempMax + x, x)
        max = Math.max(max, tempMax)
    })
    return max
};

5. 动态规划-滑动窗口：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度

// 有重复则计算一次max
var lengthOfLongestSubstring = function(s) {
    let max = 0
    let arr = []
    for (const i of s) {
        if (arr.includes(i)) {
            max = Math.max(max, arr.length)
            arr = arr.slice(arr.indexOf(i) + 1)
        }
        arr.push(i)
    }
    return Math.max(max, arr.length)
};

6.判断二叉树是否为平衡二叉树

// 判断二叉树的深度
var maxDepth = function(root) {
  if (!root) return 0
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}
// 回溯，递归
var isBalanced = function(root) {
  const dfs = root => {
      if (!root) return 0
    let left = dfs(root.left)
    let right = dfs(root.right)
    if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
        return -1
    }
    return Math.max(left, right) + 1
  }
  return dfs(root) !== -1
}

7. 二叉树总和是否等于targetsum

// 递归：targetSum减去当前值val开始递归，类似的可使用同样的解法
var hasPathSum = function(root, targetSum) {
    if (!root) return false
    if (!root.left && !root.right) return root.val === targetSum
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
};

8. 删除链表节点

// 迭代
// 递归
var deleteNode = function(head, val) {
    if (!head) return null
  if (head.val === val) return head.next
  head.next = deleteNode(head.next, val)
  return head
}