算法

[mileOfSunshine]

链表

链表节点

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val
    this.next = next
  }
}

根据一维数组生成 『链表』

function createList(arr, start = 0) {
  // 最后一项指向 null
  if(arr.length === start) {
    return null
  }
  const head = new ListNode(arr[start], createList(arr, ++start))
  return head
 }

二叉树

树节点

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

根据一维数组生成 『二叉树』

function createTree(arr, index = 1) {
  const item = arr[index - 1]
  // 递归结束条件：index超出或是叶子节点
  if(arr.length < index || item === null) {
    return null
  }
  const node = new TreeNode(item)
  node.left = createTree(arr, index * 2)
  node.right = createTree(arr, index * 2 + 1)
  return node
}

[mileOfSunshine]

时间复杂度 & 空间复杂度

时间复杂度：算法的执行时间与数据规模之间的增长关系。

公式：T(n) = O(f(n)) 其中 T(n) 表示算法执行总时间，f(n) 表示每行代码执行总次数，而 n 表示数据的规模。 大O时间复杂度表示法表示 代码执行时间随数据规模增长的变化趋势。故常量、低阶、系数 实际上对这种增长趋势不产生决定性影响项，可在做时间复杂度分析时忽略。

空间复杂度：算法的存储空间与数据规模之间的增长关系。

公式：S(n) = O(f(n)) 其中，n 为问题的规模，f(n) 为语句关于所占存储空间的函数 。

JavaScript 数据结构与算法之美 - 时间和空间复杂度 (算法入门)人人都能看懂的时间复杂度和空间复杂度

[mileOfSunshine]

? 深度优先遍历问题

二叉树的所有路径 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。

输入:

1 / \ 2 3 \ 5

输出：["1->2->5","1->3"] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

var binaryTreePaths = function(root) {
  const paths = [];
  const buildPaths = (root, path) => {
    if (root) {
      path += root.val.toString();
      if (root.left === null && root.right === null) { // 当前节点是叶子节点
        paths.push(path); // 把路径加入到答案中
      } else {
        path += "->"; // 当前节点不是叶子节点，继续递归遍历
        buildPaths(root.left, path);
        buildPaths(root.right, path);
      }
    }
  }
  buildPaths(root, "");
  return paths;
};

binaryTreePaths(createTree([1,2,3,null,5])) // => ["1->2->5", "1->3"]

作者：LeetCode-Solution 链接：https://leetcode.cn/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[mileOfSunshine]

? 有效的括号（考点：栈）

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

s = "()"  // => true
s = "()[]{}" // => true
s = "(]" // => false
s = "([)]" // => false
s = "{[]}" // => true

var isValid = function(s) {
  // 奇数不满足需求
  if (s % 2 === 1) return false
  const pairs = new Map([
    [')', '('],
    [']', '['],
    ['}', '{'],
  ])
  const stack = []
  let i = 0
  while(i < s.length) {
    const target = s[i]
    if(!pairs.has(target)) {
      stack.push(target)
    } else {
      // 当前字符和栈顶字符不匹配，直接结束  
      if (pairs.get(target) !== stack.pop()) {
        return false
      }
    }
    i++
  }
  return stack.length === 0
}

[mileOfSunshine]

? 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

head = [1,2,3,4]  // => [2,1,4,3]
head = []  // => []
head = [1]  // => [1]

var swapPairs = function(head) {
  if (head === null || head.next === null) {
    return head
  }
  const next = head.next
  head.next = swapPairs(next.next)
  next.next = head
  return next
};

[mileOfSunshine]

收集雨水问题

问题描述：给定n个非负整数，表示直方图的方柱的高度，同时，每个方柱的宽度假定都为1。若使用这样形状的容器收集雨水，可以盛多少水量？

如输入：0,1,0,2,1,0,1,3,2,1,2,1；返回6。

function GetRain(arr) {
  let sum = 0;
  for (let i = 1; i < arr.length - 1; i++) {
    let maxLeft = 0
    let maxRight = 0
    let leftArr = []
    let rightArr = []

    for (let j = 0; j < i; j++) {
      if (arr[i] < arr[j]) {
        leftArr.push(arr[j])
      }
    }

    for (let k = i + 1; k < arr.length; k++) {
      if (arr[i] < arr[k]) {
        rightArr.push(arr[k])
      }
    }

    if (leftArr.length > 0 && rightArr.length > 0) {
      maxLeft = Math.max(...leftArr)
      maxRight = Math.max(...rightArr)
      sum = sum + (Math.min(maxLeft, maxRight) - arr[i])
    }
  }
  console.log(sum)
}
const num = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
GetRain(num) // 6

GetRain([2,1,5,6,2,3]) // 2

[mileOfSunshine]

? 两个数组的交集

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

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

示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

哈希表

var intersect = (nums1, nums2) => {
  const makeMap = (nums1) => {
    const map = new Map()
    nums1.map(n => {
      map.set(n,
        map.has(n) ? map.get(n) + 1 : 1
      )
    })
    return map
  }
  const nums1Map = makeMap(nums1)
  const res = []
  nums2.map(n => {
    if (nums1Map.has(n)) {
      res.push(n)
      if (nums1Map.get(n) <= 1) {
        nums1Map.delete(n)
      } else {
        nums1Map.set(n, nums1Map.get(n) - 1)
      }
    }
  })
  return res
}

排序 + 双指针

var intersect = (nums1, nums2) => {
  const sort = (n) => n.sort((a, b) => (a - b))
  const ns1 = sort(nums1)
  const ns2 = sort(nums2)
  const res = []
  let i = 0
  let j = 0
  while(i < ns1.length && j < ns2.length) {
    if (ns1[i] < ns2[j]) {
      i++
    } else if (ns1[i] > ns2[j]) {
      j++
    } else {
      res.push(ns1[i])
      i++
      j++
    }
  }
  return res
}

[mileOfSunshine]

? 最接近的三数之和（排序 + 双指针）

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。

var threeSumClosest = function(nums, target) {
  const ns = nums.sort((a, b) => (a - b))
  const len = ns.length
  let res = ns[0] + ns[1] + ns[2]
  for(let i = 0; i < len - 1; i++) {
    let start = i + 1
    let end = len - 1
    while(start < end) {
      const sum = ns[i] + ns[start] + ns[end]
      if (Math.abs(sum - target) < Math.abs(res - target)) {
        res = sum
      }
      if (sum < target) {
        start++
      } else if (sum > target) {
        end--
      } else {
        return res
      }
    }
  }
  return res
};

[mileOfSunshine]

? 盛最多水的容器（双指针）

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]
输出：49 

var maxArea = function(height) {
  const n = height.length
  let start = 0
  let end = n - 1
  let res = 0
  while(start < end) {
    const sH = height[start]
    const eH = height[end]
    res = Math.max(Math.min(sH, eH) * (end - start), res)
    if (sH <= eH) {
      start++
    } else if (sH > eH) {
      end--
    }
  }
  return res
};

[mileOfSunshine]

排序

• 冒泡排序

function bubbleSort(arr) {
  for(var i = 0; i < arr.length - 1; i++) {
    for(var j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j+1], arr[j]] = [arr[j], arr[j+1]]
      }
    }
  }
  return arr
}

• 插入排序

（1）从第一个元素开始，该元素可以认为已经被排序。

（2）取出下一个元素，在已经排序的元素序列中从后向前扫描。

（3）如果该元素（已排序）大于新元素，则将该元素移动到下一个位置。

（4）重复上一个步骤，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置后，重复上面的步骤。

function insertSort(arr) {
  for(var i = 1; i < arr.length; i++) {
    var j = i
    var temp = arr[i]
    while(j > 0 && arr[j-1] > temp) {
      arr[j] = arr[j-1]
      j-- 
    }
    arr[j] = temp
  }
  return arr
}

• 快速排序

  （1）选择一个元素作为基数（通常是第一个元素） （2）把比基数小的元素放到它左边 （3）比基数大的元素放到它右边（相当于二分） （4）再不断递归基数左右两边的序列。

[mileOfSunshine]

区间重叠|重叠比判断算法

假设存在两个区间 A[A1, A2]，B[B1, B2]，如何判断区间 A 和 B 存在重叠，重叠的长度多少.

伪代码：

1、Begin = Max(A1 , B1) ;

2、End = Min(A2 , B2) ;

3、Len = End - Begin

如果Len >= 0，那么区间AB重叠，重叠部分为Len；否则不重叠