前端常见算法

查找表问题

两个数组的交集 II-350

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/in… (opens new window) 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

为两个数组分别建立 map，用来存储 num -> count 的键值对，统计每个数字出现的数量。

找出 nums1, nums2 的公共元素，然后将公共元素按出现的次数往结果数组里 push 公共元素

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
  const res = []
  const map1 = makeMap(nums1)
  const map2 = makeMap(nums2)
  const commen = [...new Set(nums1.concat(nums2))]
  commen.forEach(v => {
    if (map1[v] && map2[v]) {
      const min = Math.min(map1[v], map2[v])
      for (let i = 0; i < min; i++) {
        res.push(v)
      }
    }
  })
  return res
}

const makeMap = nums => {
  const map = Object.create(null)
  nums.forEach(v => {
    map[v] = map[v] || 0
    map[v]++
  })
  return map
}

双指针问题

最接近的三数之和-16

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

3 <= nums.length <= 10^3` `-10^3 <= nums[i] <= 10^3` `-10^4 <= target <= 10^4

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/3s… (opens new window)

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

先按照升序排序，然后分别从左往右依次选择一个基础点 i（0 <= i <= nums.length - 3），在基础点的右侧用双指针去不断的找最小的差值。

假设基础点是 i，初始化的时候，双指针分别是：

• left：i + 1，基础点右边一位。
• right: nums.length - 1 数组最后一位。

然后求此时的和，如果和大于 target，那么可以把右指针左移一位，去试试更小一点的值，反之则把左指针右移。

在这个过程中，不断更新全局的最小差值 min，和此时记录下来的和 res。

最后返回 res 即可。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

let threeSumClosest = function(nums, target) {
  let n = nums.length
  if (n === 3) {
    return nums[0] + nums[1] + nums[2]
  }
  // 先升序排序 此为解题的前置条件
  nums.sort((a, b) => a - b)

  let min = Infinity // 和 target 的最小差
  let res

  // 从左往右依次尝试定一个基础指针 右边至少再保留两位 否则无法凑成3个
  for (let i = 0; i <= nums.length - 3; i++) {
    let basic = nums[i]
    let left = i + 1 // 左指针先从 i 右侧的第一位开始尝试
    let right = n - 1 // 右指针先从数组最后一项开始尝试

    while (left < right) {
      let sum = basic + nums[left] + nums[right] // 三数求和
      // 更新最小差
      let diff = Math.abs(sum - target)
      if (diff < min) {
        min = diff
        res = sum
      }
      if (sum < target) {
        // 求出的和如果小于目标值的话 可以尝试把左指针右移 扩大值
        left++
      } else if (sum > target) {
        // 反之则右指针左移
        right--
      } else {
        // 相等的话 差就为0 一定是答案
        return sum
      }
    }
  }

  return res
}

滑动窗口问题

无重复字符的最长子串-3

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/lo… (opens new window) 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

这题是比较典型的滑动窗口问题，定义一个左边界 left 和一个右边界 right，形成一个窗口，并且在这个窗口中保证不出现重复的字符串。

/**
 * @param {string} str
 * @return {number}
 */

let lengthOfLongestSubstring = function(str) {
  const len = str.length
  let max = 0
  let i = 0 // 左指针
  for (let j = 0; j < len; j++) {
    const v = str[j]
    let subStr = str.slice(i, j)
    // 确保 subStr 是无重复子串
    while (subStr.includes(v)) {
      i++
      subStr = str.slice(i, j)
    }
    max = Math.max(max, j - i + 1)
  }
  return max
}

let test = 'abcabcbcabbc'
console.log(lengthOfLongestSubstring(test))

链表问题

两两交换链表中的节点-24

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/sw… (opens new window)

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

这题本意比较简单，1 -> 2 -> 3 -> 4 的情况下可以定义一个递归的辅助函数 helper，这个辅助函数对于节点和它的下一个节点进行交换，比如 helper(1) 处理 1 -> 2，并且把交换变成 2 -> 1 的尾节点 1的next继续指向 helper(3)也就是交换后的 4 -> 3。

边界情况在于，1.第 1 第 2 一对节点与之后的节点对(3 与 4 对，5 与 6 对...)的处理不同，所以增加一个 dummy node 使 1,2 节点对与之后的处理保持一致；2.current 或者 current.next 都可能为尾结点，需要特殊处理。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
let swapPairs = function(head) {
  let dummy = new ListNode(undefined, head)
  let current = dummy
  let n1 = current.next
  let n2 = (n1 || {}).next
  while (n1 && n2) {
    current.next = n2
    n1.next = n2.next
    n2.next = n1
    current = n1
    n1 = current.next
    n2 = (n1 || {}).next
  }
  return dummy.next
}

栈问题

有效的括号-20

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

leetcode-cn.com/problems/va… (opens new window)

---

提前记录好左括号类型 (, {, [和右括号类型), }, ]的映射表，当遍历中遇到左括号的时候，就放入栈 stack 中（其实就是数组），当遇到右括号时，就把 stack 顶的元素 pop 出来，看一下是否是这个右括号所匹配的左括号（比如 ( 和 ) 是一对匹配的括号）。

当遍历结束后，栈中不应该剩下任何元素，返回成功，否则就是失败。

/**
 * @param {string} s
 * @return {boolean}
 */
const map = {
  ')': '(',
  ']': '[',
  '}': '{'
}
let isValid = function(str) {
  const arr = []
  if (str.length % 2) return false
  return (
    str.split('').every(s => {
      if (['(', '[', '{'].includes(s)) {
        arr.push(s)
        return true
      } else {
        if (arr.pop() === map[s]) return true
        return false
      }
    }) && arr.length === 0
  )
}

递归与回溯

直接看我写的这两篇文章即可，递归与回溯甚至是平常业务开发中最常见的算法场景之一了，所以我重点总结了两篇文章。

《前端电商 sku 的全排列算法很难吗？学会这个套路，彻底掌握排列组合。》 (opens new window)

前端「N 皇后」递归回溯经典问题图解 (opens new window)

动态规划

打家劫舍 - 198

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
  偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
  偷窃到的最高金额 = 2 + 9 + 1 = 12 。

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/ho… (opens new window) 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

动态规划的一个很重要的过程就是找到「状态」和「状态转移方程」，

在这个问题里，设 i 是当前屋子的下标，dp[i] 是偷前 i 个房子能获取的最大价值。

在某一个房子 i 面前，盗贼只有两种选择：偷或者不偷。

1. 偷的话，价值就是「当前房子的价值」+ dp[i - 2]
2. 不偷的话，价值就是 dp[i - 1]

在这两个值中，选择最大值记录在 dp[i]中。

动态规划的起手式，找基础状态，在这题中，以 dp[0] 为起点的最大价值一定是最好找的，就是 nums[0]。

那么就找到了动态规划的状态转移方程：

dp[0] = nums[0]
dp[1] = Math.max(nums[1], dp[0])
dp[2] = Math.max(nums[2] + dp[0], dp[1])
dp[3] = Math.max(nums[3] + dp[1], dp[2])
...
dp[n] = Math.max(nums[n] + dp[n - 2], dp[n - 1])

并且从后往前求解。

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  const n = nums.length
  if (!n) {
    return 0
  }
  let dp = new Array(nums.length).fill(0)
  nums.forEach((v, i) => {
    if (i === 0) {
      dp[0] = v
    } else if (i === 1) {
      dp[1] = Math.max(v, dp[0])
    } else {
      dp[i] = Math.max(v + dp[i - 2], dp[i - 1])
    }
  })
  return dp[n - 1]
}

最后返回 dp 数组最后一个元素即可。

贪心算法问题

分发饼干-455

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：

你可以假设胃口值为正。 一个小朋友最多只能拥有一块饼干。

示例 1:

输入: [1,2,3], [1,1]

输出: 1

解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:

输入: [1,2], [1,2,3]

输出: 2

解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/as… (opens new window) 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

把饼干和孩子的需求都排序好，然后从最小的饼干分配给需求最小的孩子开始，不断的尝试新的饼干和新的孩子，这样能保证每个分给孩子的饼干都恰到好处的不浪费，又满足需求。

利用双指针不断的更新 i 孩子的需求下标和 j饼干的值，直到两者有其一达到了终点位置：

1. 如果当前的饼干不满足孩子的胃口，那么把 j++ 寻找下一个饼干，不用担心这个饼干被浪费，因为这个饼干更不可能满足下一个孩子（胃口更大）。
2. 如果满足，那么 i++; j++; count++ 记录当前的成功数量，继续寻找下一个孩子和下一个饼干。

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
  g = g.sort((a, b) => a - b)
  s = s.sort((a, b) => a - b)
  let child,
    cookie,
    n1 = g.length,
    n2 = s.length,
    i = 0,
    j = 0,
    count = 0
  while (i < n1 && j < n2) {
    child = g[i]
    cookie = s[j]
    if (cookie >= child) {
      j++
      i++
      count++
    } else {
      j++
    }
  }
  return count
}

排列组合

77. 组合 (opens new window)

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

---

思路：递归求解， [1, n] 中所有可能的 k 个数的组合，等于 [1, n] 中先选一个数出来，再在剩下的 n - 1 个数中选 k - 1 个数出来。

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var helper = function(arr, k) {
  const result = []
  const n = arr.length
  if (k > 0) {
    for (let i = 0; i < n; i++) {
      const left = arr[i]
      if (k === 1) {
        result.push([left])
      } else {
        const rest = arr.slice(i + 1, n)
        let temp = helper(rest, k - 1)
        temp.forEach(arr1 => {
          arr1.unshift(left)
          result.push(arr1)
        })
      }
    }
  }
  return result
}

const combine = function(n, k) {
  const arr = Array.from({ length: n }, (v, k) => k + 1)
  return helper(arr, k)
}
console.log(combine(4, 2))

JS 实现全排列

给定一个字符串，输出该字符串所有排列的可能。如输入“abc”，输出“abc,acb,bca,bac,cab,cba”。

实现过程

输入字符串，输出所有的组合，对 js 来说，用数组表示最恰当了 即：

function fullpermutate(str) {
  var result = []
  return result
}

然后，用递归的形式解决。基础情况应该是输入字符串为单个字符时的情况，此时返回的就是其本身，但不要忘记用数组的形式返回哦；

function fullpermutate(str) {
  var result = []
  if (str.length > 1) {
    //do something
  } else if (str.length == 1) {
    result.push(str)
  }
  return result
}

接下来，遍历字符串的每一个元素，并将字符串中除了该元素的其他元素进行全排列，如'abc',拿到 a 后，将 bc 再次进行全排列，返回的排列好的数组每一项再与 a 组合在一起得到最终的 abc、acb；

function fullpermutate(str) {
  var result = []
  if (str.length > 1) {
    //遍历每一项
    for (var m = 0; m < str.length; m++) {
      //拿到当前的元素
      var left = str[m]
      //除当前元素的其他元素组合
      var rest = str.slice(0, m) + str.slice(m + 1, str.length)
      //上一次递归返回的全排列
      var preResult = fullpermutate(rest)
      //组合在一起
      for (var i = 0; i < preResult.length; i++) {
        var tmp = left + preResult[i]
        result.push(tmp)
      }
    }
  } else if (str.length == 1) {
    result.push(str)
  }
  return result
}

深度优先遍历问题

二叉树的所有路径-257

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入: root = [1,2,3,null,5]

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/bi… (opens new window)

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

用当前节点的值去拼接左右子树递归调用当前函数获得的所有路径。

也就是根节点拼上以左子树为根节点得到的路径，加上根节点拼上以右子树为根节点得到的所有路径。

直到叶子节点，仅仅返回包含当前节点的值的数组。

let binaryTreePaths = function(root) {
  let res = []
  if (!root) {
    return res
  }

  if (!root.left && !root.right) {
    return [`${root.val}`]
  }

  let leftPaths = binaryTreePaths(root.left)
  let rightPaths = binaryTreePaths(root.right)

  leftPaths.forEach(leftPath => {
    res.push(`${root.val}->${leftPath}`)
  })
  rightPaths.forEach(rightPath => {
    res.push(`${root.val}->${rightPath}`)
  })

  return res
}

广度优先遍历（BFS）问题

在每个树行中找最大值-515

leetcode-cn.com/problems/fi… (opens new window)

您需要在二叉树的每一行中找到最大的值。

输入:

          1
         / \
        3   2
       / \   \
      5   3   9

输出: [1, 3, 9]

---

这是一道典型的 BFS 题目，BFS 的套路其实就是维护一个 queue 队列，在读取子节点的时候同时把发现的孙子节点 push 到队列中，但是先不处理，等到这一轮队列中的子节点处理完成以后，下一轮再继续处理的就是孙子节点了，这就实现了层序遍历，也就是一层层的去处理。

但是这里有一个问题卡住我了一会，就是如何知道当前处理的节点是哪个层级的，在最开始的时候我尝试写了一下二叉树求某个 index 所在层级的公式，但是发现这种公式只能处理「平衡二叉树」。

后面看题解发现他们都没有专门维护层级，再仔细一看才明白层级的思路：

其实就是在每一轮 while 循环里，再开一个 for 循环，这个 for 循环的终点是「提前缓存好的 length 快照」，也就是进入这轮 while 循环时，queue 的长度。其实这个长度就恰好代表了「一个层级的长度」。

缓存后，for 循环里可以安全的把子节点 push 到数组里而不影响缓存的当前层级长度。

另外有一个小 tips，在 for 循环处理完成后，应该要把 queue 的长度截取掉上述的缓存长度。一开始我使用的是 queue.splice(0, len)，结果速度只击败了 33%的人。后面换成 for 循环中去一个一个shift来截取，速度就击败了 77%的人。

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
let largestValues = function(root) {
  if (!root) return []
  let queue = [root]
  let maximums = []

  while (queue.length) {
    let max = -Infinity
    // 这里需要先缓存len 这个len最开始代表当前所处的层级
    // 在循环开始后 会push新的节点 len就不稳定了
    let len = queue.length
    for (let i = 0; i < len; i++) {
      let node = queue[i]
      max = Math.max(node.val, max)

      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
    }

    // 本「层级」处理完毕，截取掉。
    while (len--) {
      queue.shift()
    }

    // 这个for循环结束后 代表当前层级的节点全部处理完毕
    // 直接把计算出来的最大值push到数组里即可。
    maximums.push(max)
  }

  return maximums
}

const root = {
  val: 1,
  left: {
    val: 3,
    left: {
      val: 5
    },
    right: {
      val: 3
    }
  },
  right: {
    val: 2,
    left: null,
    right: {
      val: 9
    }
  }
}
console.log(largestValues(root))

二叉树遍历

1. 前序遍历

LeetCode 题目 (opens new window)

递归

先记录 node.val, 再递归 node.left, node.right

var preorderTraversal = function(root) {
  const res = []
  // 递归函数
  function _preorder(node) {
    if (!node) return
    res.push(node.val)
    _preorder(node.left)
    _preorder(node.right)
  }
  _preorder(root)
  return res
}

迭代

通过栈数据结构(先进后出)，在出栈时记录节点值，则出栈时记录的顺序为 父节点->左子节点->右子节点，又因为必须父节点最先进栈，所以进栈的顺序为 父节点->右子节点->左子节点，且父节点进栈后立即出栈。我们将父节点压入栈，对栈执行出栈操作，每次将出栈的节点的右孩子先压入栈，其次压入左孩子。这样就可以做到先遍历父节点，再遍历左孩子部分，后遍历右孩子部分。

var preorderTraversal = function(root) {
  if (!root) return []
  const stack = [root]
  const res = []
  while (stack.length) {
    // 出栈
    const cur = stack.pop()
    res.push(cur.val)
    // 子节点存在压入栈中，先右再左
    cur.right && stack.push(cur.right)
    cur.left && stack.push(cur.left)
  }
  return res
}

2. 中序遍历

LeetCode 题目 (opens new window)

递归

先递归 node.left, 再记录 node.val, 再递归 node.right

var inorderTraversal = function(root) {
  const res = []
  // 递归函数
  function _inorder(node) {
    if (!node) return
    _inorder(node.left)
    res.push(node.val)
    _inorder(node.right)
  }
  _inorder(root)
  return res
}

迭代

我们同样可以使用栈结构来实现中序遍历，因为中序遍历左子树是优先遍历，所以父节点要先于左子树的节点优先压入栈中，每当我们压入节点时，都要把节点的左子树的所有左节点压入栈中。

var inorderTraversal = function(root) {
  if (!root) return []
  const stack = []
  let cur = root
  const res = []
  while (stack.length || cur) {
    // 左节点都先压入栈
    while (cur) {
      stack.push(cur)
      cur = cur.left
    }
    const node = stack.pop()
    res.push(node.val)
    if (node.right != null) {
      cur = node.right
    }
  }
  return res
}

3. 后序遍历

LeetCode 题目 (opens new window)

递归

先递归 node.left, node.right, 再记录 node.val

var postorderTraversal = function(root) {
  const res = []
  // 递归函数
  function _postorder(node) {
    if (!node) return
    _postorder(node.left)
    _postorder(node.right)
    res.push(node.val)
  }
  _postorder(root)
  return res
}

迭代

后序遍历是父节点需要最后被遍历。但其实可以跟前序遍历的实现方式上差不多，只不过在插入数组中，我们总是在头部插入，这样先被插入的节点值一定是相对于左右孩子后面的。

var postorderTraversal = function(root) {
  if (!root) return null
  const res = []
  const stack = [root]
  while (stack.length) {
    const cur = stack.pop()
    // 总是头部插入，先被插入的在后面。
    res.unshift(cur.val)
    cur.left && stack.push(cur.left)
    cur.right && stack.push(cur.right)
  }

  return res
}

3. 层序遍历（广度优先遍历）

LeetCode 题目 (opens new window)

递归

var levelOrder = function(root) {
  const res = []
  function _levelOrder(node, level) {
    if (!node) return null
    // 当前层数组初始化
    res[level] = res[level] || []
    res[level].push(node.val)
    // 下一层 +1
    _levelOrder(node.left, level + 1)
    _levelOrder(node.right, level + 1)
  }
  _levelOrder(root, 0)

  return res
}

迭代

我们使用队列来保存节点，每轮循环中，我们都取一层出来，将它们的左右孩子放入队列。

var levelOrder = function(root) {
  if (root == null) return []
  const ans = []
  let level = 0
  const queue = [root]
  while (queue.length) {
    ans.push([])
    // len 是一整层元素的个数
    const len = queue.length
    // 通过遍历，提前执行完一层的所有元素，层级level就可以+1
    for (let i = 0; i < len; i++) {
      const node = queue.shift()
      ans[level].push(node.val)
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
    }
    level++
  }
  return ans
}

总结

关于二叉树的前序、中序、后续遍历，使用递归的方法不用多说，主要是迭代方法，通过对栈的应用，对节点不同顺序的压入栈中，从而实现不同顺序的遍历。二叉树的层序遍历迭代方式则是通过对队列的应用。

4. 二叉树的最近公共祖先

题目：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

解题思路

第一步： 弄清 3 种情况下返回 root；

1. root === null;
2. root === p;
3. root === q;

第二步： 分治： 让左右子树分别深度优先搜索获取返回值 left 和 right；根据返回值有 4 种情况

1. left,right 都为 null；则证明左右子树都找不到 返回 null；
2. left 为 null，则把希望寄托在 right 不管找不找得到都返回 right
3. right 为 null，则把希望寄托在 left 不管找不找得到都返回 left
4. left,right 都不为 null；则证明左右子树都找到了 返回 root；

// https://www.bilibili.com/video/BV16g4y1B7hj?spm_id_from=333.337.search-card.all.click
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  if (!root || root === p || root === q) return root
  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)
  if (!left) return right
  if (!right) return left
  return root
}

5. 二叉树的深度/平衡二叉树

二叉树的深度/平衡二叉树, 判断二叉树是否是平衡二叉树

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */

/**
思路： root 的深度 = max(root.left 的深度，root.right 的深度) + 1
然后递归
 */
function TreeDepth(pRoot) {
  if (!pRoot) return 0
  const left = TreeDepth(pRoot.left)
  const right = TreeDepth(pRoot.right)
  return Math.max(left, right) + 1
}
module.exports = {
  TreeDepth: TreeDepth
}

/**
判断是否是平衡二叉树。
如果 root 的左右子树高度差 diff <= 1，且左右子树都是平衡二叉树，
则 root 是平衡二叉树
 */
const isBalanceTree = pRoot => {
  if (!pRoot) return true
  const leftDepth = TreeDepth(root.left)
  const rightDepth = TreeDepth(root.right)
  if (Math.abs(leftDepth - rightDepth) > 1) return false
  return isBalanceTree(root.left, root.right)
}

6. 扁平数据结构转 Tree

打平的数据内容如下：

let arr = [
  { id: 1, name: '部门1', pid: 0 },
  { id: 2, name: '部门2', pid: 1 },
  { id: 3, name: '部门3', pid: 1 },
  { id: 4, name: '部门4', pid: 3 },
  { id: 5, name: '部门5', pid: 4 }
]

输出结果

[
  {
    "id": 1,
    "name": "部门1",
    "pid": 0,
    "children": [
      {
        "id": 2,
        "name": "部门2",
        "pid": 1,
        "children": []
      },
      {
        "id": 3,
        "name": "部门3",
        "pid": 1,
        "children": [
          // 结果 ,,,
        ]
      }
    ]
  }
]

let arr = [
  { id: 1, name: '部门1', pid: 0 },
  { id: 2, name: '部门2', pid: 1 },
  { id: 3, name: '部门3', pid: 1 },
  { id: 4, name: '部门4', pid: 3 },
  { id: 5, name: '部门5', pid: 4 }
]

/**
 * @param {Array} data
 * @param {number} pid
 * @return {Array}
 */
const arrayToTree = (data, pid) => {
  // 构造一个 root 节点用于开始递归
  const root = {
    id: pid,
    children: []
  }
  // helper 方法递归的将 node 的子节点放入 node.children
  const helper = node => {
    data
      .filter(child => child.pid === node.id)
      .forEach(child => {
        node.children.push(child)
        child.children = []
        helper(child)
      })
  }
  helper(root)
  console.log(JSON.stringify(root.children, null, 2))
  return root.children
}
arrayToTree(arr, 0)

7. 重建二叉树

根据前序遍历和中序遍历结果重建二叉树：

LeetCode (opens new window)

优化方向：

• 最开始用 map 映射一下 中序遍历的值和 index，避免以后 n * n 次遍历中序遍历

• 去处对数组的 slice ，改为传 前序子数组的 start,end 以及 中序子数组的 start,end。

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶
   示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：
1 <= n <= 45

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/climbing-stairs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

本质上是一个斐波那契数列，详细解释 (opens new window)

// 记忆化递归
var temp = []
var climbStairs = function(n) {
  if (n <= 0) {
    return 0
  }
  if (n <= 2) {
    return n
  }
  if (temp[n]) {
    return temp[n]
  }
  temp[n] = climbStairs(n - 2) + climbStairs(n - 1)
  return temp[n]
}

// 动态规划的解法
var climbStairs = function(n) {
  if (n <= 2) {
    return n
  }
  var res = [0, 1, 2]
  for (var i = 3; i <= n; i++) {
    res[i] = res[i - 1] + res[i - 2]
  }
  return res[n]
}

猴子吃香蕉

猴子吃香蕉, 分割数组（猴子吃香蕉可是掰成好几段来吃哦）

把一个数组arr按照指定的数组大小size分割成若干个数组块。

例如:

chunk([1,2,3,4],2)=[[1,2],[3,4]];

chunk([1,2,3,4,5],2)=[[1,2],[3,4],[5]];

function chunk(arr, size) {
  var newarr = []
  for (var i = 0; i < arr.length; i += size) {
    newarr.push(arr.slice(i, i + size))
  }
  console.log(newarr)
  return newarr
}
chunk(['a', 'b', 'c', 'd'], 2)

判断回文字符串

1. reverse()

function Palindromes(str) {
  let reg = /[\W_]/g // \w 匹配所有字母和数字以及下划线； \W与之相反； 
  // [\W_] 表示匹配下划线或者所有非字母非数字中的任意一个；g全局匹配
  let newStr = str.replace(reg, '').toLowerCase()
  let reverseStr = newStr
    .split('')
    .reverse()
    .join('')
  return reverseStr === newStr // 与 newStr 对比
}

实际上这里做了很多步对数组的操作，字符转数组 翻转数组 再转字符串，所以这里性能也不是很好。因为数组是引用类型，要改变这个数组，需要开辟新的堆地址空间。字符串没有 reverse 方法。

2. 循环

// 写法1
function Palindromes(str) {
  let reg = /[\W_]/g
  let newStr = str.replace(reg, '').toLowerCase()
  for (let i = 0, len = Math.floor(newStr.length / 2); i < len; i++) {
    if (newStr[i] !== newStr[newStr.length - 1 - i]) return false
  }
  return true
}
// 写法2
function Palindromes(str) {
  let reg = /[\W_]/g
  let newStr = str.replace(reg, '').toLowerCase()
  let len = newStr.length
  for (let i = 0, j = len - 1; i < j; i++, j--) {
    // i < j
    console.log('---')
    if (newStr[i] !== newStr[j]) return false
  }
  return true
}
// 写法3
function Palindromes(str) {
  let reg = /[\W_]/g
  let newStr = str.replace(reg, '').toLowerCase()
  let start = 0
  let end = newStr.length - 1
  while (start < end) {
    if (newStr[start] !== newStr[end]) {
      return false
    }
    start++
    end--
  }
  return true
}
const str1 = 'abcdcba'
const str2 = 'abcdcba1'
console.log(Palindromes(str1))
console.log(Palindromes(str2))

3. 递归

function Palindromes(str) {
  let reg = /[\W_]/g
  let newStr = str.replace(reg, '').toLowerCase()
  let len = newStr.length
  while (len >= 1) {
    console.log('--')
    if (newStr[0] != newStr[len - 1]) {
      // len = 0; // 为了终止 while 循环 否则会陷入死循环
      return false
    } else {
      return Palindromes(newStr.slice(1, len - 1))
      // 截掉收尾字符 再次比较收尾字符是否相等
      // 直到字符串剩下一个字符（奇数项）或者 0 个字符（偶数项）
    }
  }
  return true
}

钟表时针和分针夹角

以 12 点为界限来计算角度，首先计算时针到 12 点的角度，就等于 h % 12 * 360 + 360 / 12 * m / 60。

再计算分针到 12 点的角度，就是 m / 60 * 360。之后求这两个角度差的绝对值就是夹角，如果夹角大于 180 则再求一次补角返回即可。

/**
 * @param {number} hour
 * @param {number} minutes
 * @return {number}
 */
var angleClock = function(h, m) {
  // 分针移动的角度
  let minutesAngle = (m / 60) * 360
  // 时针移动的角度 并且防止12点 所以 hour % 12
  let hourAngle = (h % 12) * 360 + ((360 / 12) * m) / 60
  // 用时针的角度减去分针的角度，得其绝对值
  let diff = Math.abs(hourAngle - minutesAngle)
  // 返回最小值
  return Math.min(diff, 360 - diff)
}

反转链表

题目： https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

{1,2,3} -> {3,2,1}

// https://www.bilibili.com/video/BV1KZ4y157Up?spm_id_from=333.337.search-card.all.click
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function ReverseList(pHead) {
  let pre,
    current = pHead,
    temp
  while (current) {
    temp = current.next
    current.next = pre
    pre = current
    current = temp
  }
  return pre
}
module.exports = {
  ReverseList: ReverseList
}

两个链表的第一个公共节点

两个链表的第一个公共节点 (opens new window)

B站讲解 (opens new window)

链表中环的入口结点

题目： (opens new window)

思路： (opens new window)

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

/**
主要分为三步：
1.通过快慢指针判断是否有环：如果有环，快慢指针相遇的节点A一定位于环内
2.获取环的长度：从快慢指针相遇的节点A开始遍历，回到节点A时走过的长度就是环长l + 1
3.使用前后指针 p1,p2，快指针 p1 比慢指针 p2 先多走 l 步，
则 p1,p2 相遇的点就是环的入口
 */
function EntryNodeOfLoop(pHead) {
  let fast = pHead,
    slow = pHead

  if (!fast.next) return null
  while (fast && fast.next) {
    fast = fast.next.next
    slow = slow.next
    if (fast === slow) {
      break
    }
  }
  console.log(`fast1`, fast)
  console.log(`slow`, slow)
  if (!fast) return null
  fast = fast.next
  let len = 1
  while (fast !== slow) {
    len++
    fast = fast.next
  }
  console.log(`fast2`, fast)
  console.log(`len`, len)
  ;(fast = pHead), (slow = pHead)
  while (len--) {
    fast = fast.next
  }
  console.log(`fast3`, fast)
  while (fast !== slow) {
    fast = fast.next
    slow = slow.next
  }
  console.log(`fast4`, fast)
  console.log(`slow4`, slow)
  return slow
}
module.exports = {
  EntryNodeOfLoop: EntryNodeOfLoop
}

// {1,2},{3,4,5}

// var n3 = {
//   val: 5,
//   next: n2
// }

// var n2 = {
//   val: 3,
//   next: {
//     val: 4,
//     next: n3
//   }
// }

// n3.next = n2

// var n1 = {
//   val: 1,
//   next: { val: 2, next: n2 }
// }

var n1 = {
  val: 1
}

EntryNodeOfLoop(n1)

前端排序算法汇总

1. sort 排序

// 数组排序
var arr=[3,4,100,9,2,16];
arr.sort((a,b) => a-b)  //括号里不写回调函数，则默认按照字母逐位升序排列，结果为[2,3,4,9,16,100]

2. 插入排序

保证左边 n 个数始终从小到大排列，将第 n + 1 个数抽出来，插入到左边有序数列的合适的位置，使之依然保持有序。

var arr = [10, 44, 82, 50, 70, 74, 29, 1, 40, 36, 58, 21, 56, 44, 43, 61, 222, 48];
for (var i = 0; i < arr.length - 1; i++) {
  var n = i;
  // 保证左边 n + 1 个数始终从小到大
  while (arr[n + 1] < arr[n] && n >= 0) {
    var temp = arr[n];
    arr[n] = arr[n + 1];
    arr[n + 1] = temp;
    n--;
  }
}

3. 冒泡排序

//性能一般
var arr = [3, 4, 1, 2];
function bubbleSort (arr) {
  for (var j = 0; j < arr.length - 1; j++) {
    // 这里要根据外层for循环的 j，逐渐减少内层 for循环的次数
    for (var i = 0; i < arr.length - 1 - j; i++) {
      if (arr[i] > arr[i + 1]) {
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
  return arr;
}
bubbleSort(arr);

4. 选择排序

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

// 性能一般
var arr = [10, 44, 82, 50, 70, 74, 29, 1, 40, 36, 58, 21, 56, 44, 43, 61, 222, 48]
var temp
for (var i = 0; i < arr.length - 1; i++) {
  for (var j = i + 1; j < arr.length; j++) {
    if (arr[j] < arr[i]) {
      temp = arr[i]
      arr[i] = arr[j]
      arr[j] = temp
    }
  }
}

5. 桶排序

不重要 https://juejin.cn/post/6960226985926721567

var arr=[10,44,82,50,70,74,29,1,40,36,58,21,56,44,43,61,222,48];
var arr2=[];
for(var i=0;i<arr.length;i++){
    var key=arr[i];
    arr2[key]=1;
}
for(var j in arr2){
    console.log(j);
}

计数排序

//1. 定义需要排序的数组
let arr = [2, 6, 3, 8, 3]
// let arr = [9,5,8,7,2,3,5,1,7,2,3,5,7,6,8,9,2,1,3,5];
const max = Math.max(...arr)
//2. 定义需要记录元素出现次数的数组 arr1
let arr1 = new Array(max)
//3. 把arr1的值全部置零
arr1.fill(0)
//4. 循环遍历arr,记录arr中元素出现的次数
for (let i = 0; i < arr.length; i++) {
  arr1[arr[i]] = arr1[arr[i]] + 1
  // 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14    索引号
  //[0, 0, 1, 2, 0, 0, 1, 0, 1, 0, 0,  0, 0, 0, 0]
}
//5. 定义一个接受返回值的数组 arr2
let arr2 = []
//6. 遍历 arr1
for (let i = 0; i < arr1.length; i++) {
  //7. arr1[i] 就是 i 出现的次数
  for (let j = 0; j < arr1[i]; j++) {
    arr2.push(i)
  }
}
console.log(arr2) //[2, 3, 3, 6, 8]

6. 希尔排序

原理 (opens new window)

希尔排序又称缩小增量排序，是插入排序 (opens new window)的一种更高效的改进版，属于非稳定排序算法。

适用说明

希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多。

算法思想

希尔排序的基本思想是：先将整个待排序的序列分割成为若干子序列，而后将它们分别进行直接插入排序。

具体步骤：

1. 选择一个增量序列 t1，t2，…，ti，tj，tk，其中 ti > tj，tk = 1。注意，增量是不断缩小的。
2. 按增量序列的个数 n，对序列进行 n 趟排序。
3. 每趟排序，根据对应的增量，将待排序的序列分割成若干长度为 m 的子序列，并分别对各子序列进行直接插入排序。当增量为 1 时，对整个序列进行直接插入排序。

function shell(arr) {
  var interval = parseInt(arr.length / 2);  //分组间隔设置
  while (interval > 0) {
    for (var i = 0; i < arr.length; i++) {
      var n = i;
      while (arr[n] < arr[n - interval] && n > 0) {
        var temp = arr[n];
        arr[n] = arr[n - interval];
        arr[n - interval] = temp;
        n = n - interval;
      }
    }
    interval = parseInt(interval / 2);
  }
  return arr;
}
let arr1 = [10, 44, 82, 50, 70, 74, 29, 1, 40, 36, 58, 21, 56, 44, 43, 61, 222, 48]
shell(arr1);

7. 快速排序

核心思想:

1.在待排序的元素任取一个元素作为基准(通常选第一个元素，称为基准元素）

2.将待排序的元素进行分块，比基准元素大的元素移动到基准元素的右侧，比基准元素小的移动到左侧，从而一趟排序过程，就可以锁定基准元素的最终位置

3.对左右两个分块重复以上步骤直到所有元素都是有序的（递归过程）

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var left = [];
  var right = [];
  var midIndex = parseInt(arr.length / 2);
  var mid = arr[midIndex];
  for (var i = 0; i < arr.length; i++) {
    if (i == midIndex) continue;
    if (arr[i] < mid) {
      left.push(arr[i])
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([mid], quickSort(right));
}

const mm = [4,2,0,9,8,3,1,9,9,2]
console.log(mm)
console.log(quickSort(mm))