数据结构

1.数据结构简介

1.1 总体学习内容

1. 将要学到的数据结构：
   • 栈、队列、链表
   • 集合、字典
   • 树、堆、图
2. 将要学习的算法：
   • 链表：遍历链表、删除链表节点
   • 数、图：深度 / 广度优先遍历
   • 数组：冒泡 / 选择 / 插入 / 归并 / 快速排序、顺序 / 二分搜索

1.2 时间复杂度计算

一个函数，用大 O 表示，比如 O(1)、O(n)、O(logN)...

时间复杂度是用来定性描述该算法的运行时间

1. O(1):

let i = 0
i += 1

1. O(n)：

for (let i = 0; i < n; i += 1) {
  console.log(i)
}

1. O(n) * O(n) = O(n^2)：

for (let i = 0; i < n; i += 1) {
  for (let j = 0; j < n; j += 1) {
    console.log(i, j)
  }
}

1. O(logN)：

let i = 1
while (i < n) {
  console.log(i)
  i *= 2
}

1.3 空间复杂度计算

一个函数，用大 O 表示，比如 O(1)、O(n)、O(n^2)...

算法在运行过程中临时占用存储空间大小的量度

1. O(1)：

let i = 0
i += 1

1. O(n)：

const list = []
for (let i = 0; i < n; i += 1) {
  list.push(i)
}

1. O(n^2)：矩阵

const matrix = []
for (let i = 0; i < n; i += 1) {
  matrix.push([])
  for (let j = 0; j < n; j += 1) {
    matrix[i].push(j)
  }
}

2.栈

2.1 栈简介

栈是一个后进先出的数据结构

push：向数组后面添加一个元素

pop：弹出数组后面的一个元素

典型结构：

const stack = []
// push：向数组末尾添加一个元素
stack.push(1)
stack.push(2)
// pop：删除数组末尾的元素，并返回该元素
const item1 = stack.pop()
const item2 = stack.pop()

2.2 调试技巧

1. 打断点后，输入 F5，即可运行 VSCode 自带的 nodejs 环境进行调试
2. 第一个按钮（continue 继续）：运行到下一个断点。如果没有下一个断点，则结束
3. 第二个按钮（step over 单步跳过）：用来一行一行执行代码
4. 第三、四个按钮（step into 单步调试、step out 单步跳出）：进入到函数内部 / 跳出函数
5. 第五个按钮（restart 重启）：重新调试一遍
6. 第六个按钮（stop 停止）：停止当前调试

2.3 有效的括号(20)

20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)open in new window

我的踩坑：

在 forEach 函数里使用 return、break。

官方解释：

除了抛出异常以外，没有办法中止或跳出 forEach() 循环。如果你需要中止或跳出循环，forEach() 方法不是应当使用的工具。若你需要提前终止循环，可以使用：

• 一个简单的 foropen in new window 循环
• for...ofopen in new window / for...inopen in new window 循环
• Array.prototype.every()open in new window
• Array.prototype.some()open in new window
• Array.prototype.find()open in new window
• Array.prototype.findIndex()open in new window

踩坑代码：

var isValid = function (s) {
  if (s.length % 2 === 1) return false
  const arr = s.split('')
  const res = []
  let popVal = ''
  // forEach 不支持提前终止循环
  arr?.forEach(item => {
    res.push(item)
    if (item != '(' && item != '[' && item != '{') {
      popVal = res.pop()
      if (
        (popVal === ')' && res[res.length - 1] === '(') ||
        (popVal === ']' && res[res.length - 1] === '[') ||
        (popVal === '}' && res[res.length - 1] === '{')
      ) {
        res.pop()
      } else {
        return false
      }
    }
  })
  if (!res.length) {
    return true
  } else {
    return false
  }
}
console.log(isValid('([}}])'))

正确代码：

var isValid = function (s) {
  // 如果字符串长度为奇数，返回 false
  if (s.length % 2 === 1) return false
  const arr = s.split('')
  const res = []
  let popVal = ''
  for (item of arr) {
    res.push(item)
    if (item != '(' && item != '[' && item != '{') {
      popVal = res.pop()
      if (
        (popVal === ')' && res[res.length - 1] === '(') ||
        (popVal === ']' && res[res.length - 1] === '[') ||
        (popVal === '}' && res[res.length - 1] === '{')
      ) {
        res.pop()
      } else {
        return false
      }
    }
  }
  if (!res.length) {
    return true
  } else {
    return false
  }
}
console.log(isValid('([}}])'))

---

解题思路：

• 新建一个栈
• 扫描字符串，遇左括号入栈，遇和栈顶括号类型匹配的右括号就出栈，类型不匹配就直接判定为不合法
• 栈空了就合法，否则不合法

老师代码：

var isValid = function (s) {
  if (s.length % 2 === 1) return false
  const stack = []
  for (let i = 0; i < s.length; i += 1) {
    const c = s[i]
    if (c === '(' || c === '{' || c === '[') {
      stack.push(c)
    } else {
      const t = stack[stack.length - 1]
      if (
        (t === '(' && c === ')') ||
        (t === '{' && c === '}') ||
        (t === '[' && c === ']')
      ) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  return stack.length === 0
}

时间复杂度和空间复杂度：

时间：O(n)（一个 for 循环）

空间：O(n)（stack 可能会占用全部的 s，故空间复杂度也是 O(n)）

2.4 JS 中的函数调用堆栈

1. 在 fun1() 出打一个断点，按 F5 调试
2. step into 进入函数内部，左边有 VARIABLES 变量、WATCH 监视、CALL STACK 调用堆栈 三个选项，选择调用堆栈
3. 一直点击 step into，发现 fun3 最后才调用，但是最先执行，可见是符合栈结构的

const fun1 = () => {
  fun2()
}
const fun2 = () => {
  fun3()
}
const fun3 = () => {}

fun1()

2.5 二叉树的前序遍历(144)

144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)open in new window

思路分析：

下面前三点需要重复（重复条件：stack.length 大于 0）

1. 先弹出节点：const n = stack.pop()
2. 再获取弹出节点的值：res.push(n.val)
3. 将弹出节点的右、左节点分别压入 stack：stack.push(n.right)、stack.push(n.left)

正确代码：

var preorderTraversal = function (root) {
  const res = []
  const stack = []
  if (root) stack.push(root)
  while (stack.length) {
    const n = stack.pop()
    res.push(n.val)
    if (n.right) stack.push(n.right)
    if (n.left) stack.push(n.left)
  }
  return res
}

---

时间复杂度和空间复杂度：

时间：O(n)（树的节点数量，每个节点都访问了一遍）

空间：O(n)（stack 最大是所有节点都压进去）

typescript 写法 - 1：

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val
    this.left = left === undefined ? null : left
    this.right = right === undefined ? null : right
  }
}

function preorderTraversal(root: TreeNode | null): number[] {
  const arr: Array<number> = []
  const stack: TreeNode[] = []
  if (root) stack.push(root)
  while (stack.length) {
    const n = stack.pop()
    if (n) arr.push(n.val)
    if (n?.right) stack.push(n.right)
    if (n?.left) stack.push(n.left)
  }
  return arr
}

typescript 写法 - 2：

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val
    this.left = left === undefined ? null : left
    this.right = right === undefined ? null : right
  }
}

function preorderTraversal(root: TreeNode | null): number[] {
  const arr: Array<number> = []
  function preorder(root: TreeNode | null) {
    if (!root) return
    arr.push(root.val)
    preorder(root.left)
    preorder(root.right)
  }
  preorder(root)
  return arr
}

2.6 定义一个类，实现 Stack 功能

// 使用 ES6 的 class，封装一个 Stack 类，包括 push、pop、peek 方法
class Stack {
  constructor() {
    this.stack = []
  }
  push(val) {
    this.stack.push(val)
  }
  pop() {
    return this.stack.pop()
  }
  peek() {
    return this.stack[this.stack.length - 1]
  }
}
let stack = new Stack()
stack.push(6)
console.log(stack)

2.7 实现十进制转二进制

// 将 100 这个十进制数字转化为二进制
const result = []
let target = 100
while (Math.floor(target / 2) !== 0) {
  result.push(target % 2)
  target = Math.floor(target / 2)
}
result.push(Math.floor(target % 2))
result.reverse()
console.log(result)

3.队列

3.1 队列简介

队列是一个先进先出的数据结构（不同于栈的后进先出）

push：向数组后面添加一个元素

shift：弹出数组前面的一个元素

典型结构：

const queue = []
queue.push(1)
queue.push(2)
const item1 = queue.shift()
const item2 = queue.shift()

3.2 最近的请求次数(933)

解题思路：

1. 有新请求就入队，3000ms 前发出的请求出队
2. 队列的长度就是最近的请求次数

代码：

var RecentCounter = function () {
  this.q = []
}
RecentCounter.prototype.ping = function (t) {
  this.q.push(t)
  while (this.q[0] < t - 3000) {
    this.q.shift()
  }
  return this.q.length
}

时间：O(n)（while 循环）

空间：O(n)（队列的长度）

3.3 定义一个类，实现 Queue 功能

// // ES5
// function Queue() {
//   this.queue = []
// }
// Queue.prototype.push = function(item) {
//   this.queue.push(item)
// }
// Queue.prototype.shift = function() {
//   return this.queue.shift()
// }
// Queue.prototype.peek = function() {
//   return this.queue[this.queue.length - 1]
// }
// var que = new Queue()
// que.push(2)
// que.push(3)
// que.push(4)
// que.shift()
// console.log(que.peek())
// console.log(que.queue)

// ES6
class Queue {
  constructor() {
    this.queue = []
  }
  push(item) {
    this.queue.push(item)
  }
  shift() {
    return this.queue.shift()
  }
  peek() {
    return this.queue[this.queue.length - 1]
  }
}
let que = new Queue()
que.push(2)
que.push(3)
que.push(4)
que.shift()
console.log(que.peek())
console.log(que.queue)

3.4 亲密字符串(859)

function buddyStrings(s: string, goal: string): boolean {
  if (s.length <= 1 || goal.length <= 1) return false
  if (s.length !== goal.length) return false
  const sList = s.split('')
  const goalList = goal.split('')
  const tempList: Array<string> = []
  let flag = 0
  for (let i = 0; i < sList.length; i += 1) {
    if (sList[i] !== goalList[i]) {
      if (tempList.length) {
        const popS = tempList.shift()
        const popGoal = tempList.shift()
        if (popS && popGoal && popS === goalList[i] && popGoal === sList[i]) {
          flag += 1
          if (flag > 1) return false
          continue
        }
        return false
      }
      tempList.push(sList[i])
      tempList.push(goalList[i])
    }
  }
  if (flag && !tempList.length) return true
  if (sList.length !== [...new Set(sList)].length && !tempList.length) {
    return true
  }
  return false
}

4.链表

4.1 链表简介

特点：

• 多个元素组成的列表
• 元素存储不连续，用 next 指针连在一起
• 增删非首尾元素，不需要移动元素，只需要更改 next 的指向即可

基本代码：

const a = { val: 'a' }
const b = { val: 'b' }
const c = { val: 'c' }
const d = { val: 'd' }
a.next = b
b.next = c
c.next = d

// 遍历链表
let p = a
while (p) {
  console.log(p.val)
  p = p.next
}

// 在 c、d 间插入 e
const e = { val: 'e' }
c.next = e
e.next = d

// 删除 e
c.next = d

如何生成链表？

// 1.创建链表的节点
function Node(value) {
  this.value = value
  this.next = null
}

// 2.新建链表的方法
function createList(arr) {
  // 创建头，为数组中的第一个值
  let head = new Node(arr[0])
  // 创建尾，令其初始值为头的值
  let tail = head
  for (let i = 1; i <= arr.length - 1; i++) {
    // 将尾的 next 指向下一个数组成员
    tail.next = new Node(arr[i])
    // 将尾节点指向下一个数组成员
    tail = tail.next
  }
  return head
}

// 3.生成链表
let linkedList = createList([1, 2, 3, 4, 5])

ts 生成链表：

// 链表,用以排序
class ListNode<T> {
  next: ListNode<T> | undefined
  constructor(public value: T) {
    this.value = value
    this.next = undefined
  }
}

// 创建链表
const createNodeList = <T>(arr: T[]) => {
  let head = new ListNode(arr[0])
  let tail = head
  for (let i = 1; i < arr.length; i += 1) {
    tail.next = new ListNode(arr[i])
    tail = tail.next
  }
  return head
}

// 创建循环链表
const createLoopNodeList = <T>(arr: T[]) => {
  const length = arr.length
  let i = 0
  let head = new ListNode(arr[i])
  let tail = head
  while (i < length - 1) {
    i += 1
    tail.next = new ListNode(arr[i])
    tail = tail.next
    continue
  }
  tail.next = head
  return head
}

export { createLoopNodeList, createNodeList }

4.2 删除链表中的节点(237)

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function (node) {
  node.val = node.next.val
  node.next = node.next.next
}

时间：O(1)

空间：O(1)

4.3 反转链表(206)

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

代码：

/**
 * 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}
 */
var reverseList = function (head) {
  let p1 = head
  let p2 = null
  let temp
  while (p1) {
    // 临时保存 p1 的下一个节点
    temp = p1.next
    // 将 p2 作为 p1 的下一个节点，达到反转效果
    // 如果是 p2 = p1.next，就是将 p2 指向 p1 的下一个节点，而不是使 p1 指向 p2
    p1.next = p2
    // 移动 p2，使之向后移了一位
    p2 = p1
    // 移动 p1，使之向后移了一位
    p1 = temp
  }
  return p2
}

ts 版本：

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

function reverseList(head: ListNode | null): ListNode | null {
  let p1 = head
  let p2: ListNode | null = null
  let tmp: ListNode | null
  while (p1?.next) {
    tmp = p1.next
    p1.next = p2
    p2 = p1
    p1 = tmp
  }
  if (p1) p1.next = p2
  return p1
}

完美解说：

LeetCode 力扣刷题 | 剑指 Offer 24. 反转链表_哔哩哔哩_bilibiliopen in new window

时间复杂度：while => O(n)

空间复杂度：O(1)

4.4 两数相加(2)

代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *   this.val = (val===undefined ? 0 : val)
 *   this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  // 新建一个新链表
  const l3 = new ListNode(0)
  let p1 = l1
  let p2 = l2
  let p3 = l3
  let carry = 0
  while (p1 || p2) {
    const v1 = p1 ? p1.val : 0
    const v2 = p2 ? p2.val : 0
    const val = v1 + v2 + carry
    carry = Math.floor(val / 10) // 十位
    // 由于新建的链表 new ListNode(0) 是一个空链表
    p3.next = new ListNode(val % 10) // 个位
    p1 = p1?.next
    p2 = p2?.next
    p3 = p3.next
  }
  // 如果是 [2, 2, 7]、[5, 6, 4] => [7, 8, 1] 是错误的，因为最后一个 carry 没有处理
  if (carry) {
    p3.next = new ListNode(carry)
  }
  // 返回的是 head 的下一个(主要是因为 head 是 val 为 0，next 为 null 的节点)
  return l3.next
}

力扣官方：

var addTwoNumbers = function (l1, l2) {
  let head = null,
    tail = null
  let carry = 0
  while (l1 || l2) {
    const n1 = l1 ? l1.val : 0
    const n2 = l2 ? l2.val : 0
    const sum = n1 + n2 + carry
    if (!head) {
      head = tail = new ListNode(sum % 10)
    } else {
      tail.next = new ListNode(sum % 10)
      tail = tail.next
    }
    carry = Math.floor(sum / 10)
    if (l1) {
      l1 = l1.next
    }
    if (l2) {
      l2 = l2.next
    }
  }
  if (carry > 0) {
    tail.next = new ListNode(carry)
  }
  return head
}

时间复杂度：while => O(n)

空间复杂度：创建了一个链表 => O(n)

---

TS 版本：

使用闭包与递归实现

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  let flag = 0
  function addTwoNode(l1: ListNode | null, l2: ListNode | null): null | ListNode {
    // 如果当前节点为 null 且前一个节点运算的 flag 有值，则返回 flag 作为 val
    if (!l1 && !l2 && flag) return new ListNode(flag, null)
    // 若 flag 没值且两节点都为 null，则返回 null
    if (!l1 && !l2) return null
    const left = l1?.val ?? 0
    const right = l2?.val ?? 0
    const val = (left + right + flag) % 10
    flag = Math.floor((left + right + flag) / 10)
    return new ListNode(val, addTwoNode(l1?.next ?? null, l2?.next ?? null))
  }
  return addTwoNode(l1, l2)
}

const l1 = new ListNode(
  9,
  new ListNode(
    9,
    new ListNode(
      9,
      new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, null))))
    )
  )
)
const l2 = new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, null))))
const result = addTwoNumbers(l1, l2)
console.log(result) // [8, 9, 9, 9, 0, 0, 0, 1]

4.5 删除排序链表中的重复元素(83)

代码：

/**
 * 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}
 */
var deleteDuplicates = function (head) {
  let p = head
  while (p && p.next) {
    if (p.val === p.next.val) {
      p.next = p.next.next
    } else {
      p = p.next
    }
  }
  return head
}

时间复杂度：O(n)

空间复杂度：O(1)

4.6 环形链表(141)

我的回答：

var hasCycle = function (head) {
  let p = head
  let pos
  const arr = []
  while (p) {
    // 返回目标的索引，若未找到返回 -1
    let target = arr.indexOf(p.next)
    if (target >= 0) {
      pos = target
      return true
    } else {
      pos = -1
    }
    arr.push(p)
    p = p.next
  }
  return false
}

答案：

使用两个速度不同的指针，因为是环形链表，所以它们迟早要相遇。如果没有相遇就不是环形链表

var hasCycle = function (head) {
  let p1 = head
  let p2 = head
  while (p1 && p2) {
    p1 = p1?.next
    p2 = p2?.next?.next
    if (p1 === p2) {
      return true
    }
  }
  return false
}

TS 实现：

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

function hasCycle(head: ListNode | null): boolean {
  let p1 = head
  let p2 = head
  while (p1 && p2) {
    p1 = p1.next
    p2 = p2.next?.next ?? null
    if (p1 && p2 && p1 === p2) {
      return true
    }
  }
  return false
}

4.7 链表拓展 --- 原型链

1. obj => Object.prototype => null
2. func => Function.prototype => Object.prototype => null
3. arr => Array.prototype => Object.prototype => null

代码示例

const obj = {}
const func = () => {}
const arr = []

---

下面结果均为 true

1. obj.__proto__ === Object.prototype、obj.__proto__.__proto__ === null
2. func.__proto__ === Function.prototype、func.__proto__.__proto__ === Object.prototype、func.__proto__.__proto__.__proto__ === null

拿 1 举例，obj 的隐式原型对象即为 Object 的原型对象，也可以说，obj 的原型链上可以找到 Object 的原型对象

下面结果均为 true

1. obj instanceOf Object
2. func instanceOf Function、func instanceOf Object

---

总结

• 如果 A 沿着原型链能找到 B.prototype，那么 A instanceOf B 为 true
• 如果在 A 对象没有找到 x 属性，那么会沿着原型链找 x 属性。举例：

var obj = {}
Object.prototype.x = 'x'
console.log(x) // 可以打印出来

const func = () => {}
Function.prototype.y = 'y'
console.log(y) // 可以打印出来

4.8 面试题一

题目

简述 instanceof 原理，并用代码实现

思路

遍历 A 的原型链，如果找到 B.prototype，返回 true，否则返回 false

代码

const instanceOf = (A, B) => {
  let p = A
  while(p) {
    if(p === B.prototype) {
      return true
    }
    p = p.__proto__
  }
  return false
}

4.9 面试题二

var foo = {}
var F = function () {}
Object.prototype.a = 'value a'
Function.prototype.b = 'value b'

console.log(foo.a) // value a，obj => Object.prototype => null
console.log(foo.b) // undefined

console.log(F.a) // value a，func => Function.prototype => Object.prototype => null
console.log(F.b) // value b

4.10 JSON 路径遍历

const json = {
  a: {
    b: {
      c: 1
    }
  },
  d: {
    e: 2
  }
}

const path = ['a', 'b', 'c']

let p = json
path.forEach(k => {
  p = p[k]
})
// 最终会得到 1（即 a.b.c 的值）

4.11 删除链表的倒数第 n 个节点(19)

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  let slow = head
  let fast = head
  // fast 比 slow 指针领先 n 个元素
  while (n-- > 0) {
    fast = fast?.next ?? null
  }
  // 删除的是第一个元素
  if (fast === null) return head?.next ?? null
  // 这里使用 fast.next 是为了将 slow 指针指向要删除元素的上一个元素，以便接下来使用 slow.next = slow.next.next
  while (fast?.next !== null) {
    fast = fast.next
    slow = slow?.next ?? null
  }
  if (slow) {
    slow.next = slow.next?.next ?? null
  }
  return head
}

const head = removeNthFromEnd(
  new ListNode(1, new ListNode(2, new ListNode(3, null))),
  1
)

4.12 相交链表(160)

使用 Set 方法进行求出相交链表：

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

function getIntersectionNode(
  headA: ListNode | null,
  headB: ListNode | null
): ListNode | null {
  const set = new Set<ListNode>([])
  let p = headA
  while (p) {
    set.add(p)
    p = p.next
  }
  p = headB
  while (p) {
    if (set.has(p)) return p
    p = p.next
  }
  return null
}

使用双指针交替遍历实现：

function getIntersectionNode(
  headA: ListNode | null,
  headB: ListNode | null
): ListNode | null {
  let p1 = headA
  let p2 = headB
  const toggleObj = {
    p1: false,
    p2: false
  }
  while (p1 || p2) {
    if (p1 === p2) return p1
    p1 = p1?.next ?? null
    p2 = p2?.next ?? null
    if (p1 == null) {
      if (toggleObj.p1) return null
      p1 = headB
      toggleObj.p1 = true
    }
    if (p2 == null) {
      if (toggleObj.p2) return null
      p2 = headA
      toggleObj.p2 = true
    }
  }
  return null
}

5.集合

5.1 集合简介

集合是一种无序且唯一的数据结构

作用：

1. 去重
2. 判断某元素是否在集合中
3. 求交集

基本操作：

// 去重
const arr = [1, 1, 2, 2]
const arr2 = [...new Set(arr)]

// 判断元素是否在集合中
const set = new Set(arr)
const has = set.has(2) // true

// 求交集
const set2 = new Set([2, 3])
const set3 = new Set([...set].filter(item => set2.has(item)))

5.2 两个数组的交集(349)

关键词：交集、唯一、数组

我的答案：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  const s1 = new Set(nums1)
  return [...new Set(nums2.filter(item => s1.has(item)))]
}
const result = intersection([4, 9, 5], [9, 4, 9, 8, 4])
console.log(result) // [9, 4]

老师的答案：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  return [...new Set(nums1)].filter(n => nums2.includes(n))
}

时间复杂度：filter + includes => O(m * n)

空间复杂度：...new Set(nums1) => O(m)

5.3 前端与集合

1. 使用 Set 对象：new、add、delete、has、size
2. 迭代 Set：多种迭代方法、Set 和 Array 互转、求交集 / 差集

---

示例代码：

// add
let mySet = new Set()
mySet.add(5)
mySet.add(5)
mySet.add(2)

// has
const has = mySet.has(5) // true

// delete
// mySet.delete(5)

// 迭代 set，set 的 keys 和 values 都是一样的
for (let item of mySet) console.log(item)
for (let item of mySet.values()) console.log(item)
for (let item of mySet.entries) console.log(item)

// set => array
const myArr = [...mySet]
const myArr2 = Array.from(mySet)

// array => set
const mySet2 = new Set([1, 2, 3, 4])

// 交集
const intersection = new Set([...mySet].filter(x => mySet2.has(x)))

// 差集
const difference = new Set([...mySet].filter(x => !mySet2.has(x)))

6.字典

6.1 简介

与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储

字典的增删改查：

const m = new Map()

// 增
m.set('a', 'aa')
m.set('b', 'bb')

// 删
m.delete('b')
// 删除所有的键值对
// m.clear()

// 改(覆盖就行)
m.set('a', 'aaa')

// 查
console.log(m.get('a')) // aaa

6.2 两个数组的交集(349)

由于字典也具有键的唯一性，所以设置 map.set() 的时候就自动去了重

代码：

var intersection = function (nums1, nums2) {
  const map = new Map()
  nums1.forEach(n => {
    map.set(n, true)
  })
  const res = []
  nums2.forEach(n => {
    if (map.get(n)) {
      res.push(n)
      map.delete(n)
    }
  })
  return res
}

时间复杂度：O(m + n)

空间复杂度：O(m)

6.3 有效的括号(20)

修改前：

var isValid = function (s) {
  if (s.length % 2 === 1) return false
  const stack = []
  const map = new Map()
  for (let i = 0; i < s.length; i += 1) {
    const c = s[i]
    if (c === '(' || c === '{' || c === '[') {
      stack.push(c)
    } else {
      const t = stack[stack.length - 1]
      if (
        (t === '(' && c === ')') ||
        (t === '{' && c === '}') ||
        (t === '[' && c === ']')
      ) {
        stack.pop()
      } else {
        return false
      }
    }
  }
}

时间复杂度：O(n)

空间复杂度：O(n)

修改后：

function isValid(s: string): boolean {
  const map = new Map([
    ['(', ')'],
    ['[', ']'],
    ['{', '}']
  ])
  const stack: string[] = []
  let top: string | undefined
  for (let char of s) {
    const value = map.get(char)
    if (value) {
      stack.push(value)
    } else {
      top = stack.pop()
      if (top !== char) return false
    }
  }
  return stack.length === 0
}

6.4 两数之和(1)

var twoSum = function (nums, target) {
  const map = new Map()
  for (let i = 0; i < nums.length; i += 1) {
    const n = nums[i]
    const n2 = target - n
    if (map.has(n2)) {
      return [map.get(n2), i]
    } else {
      map.set(n, i)
    }
  }
}

时间复杂度：O(n)

空间复杂度：O(n)

6.5 无重复字符的最长子串(3)

我的答案：

var lengthOfLongestSubstring = function (s) {
  if (s === '') return 0
  const tg = s.split('')
  const map = new Map()
  // 指针，当有重复时向右移一位
  let p = 0
  // 存放长度大小的数组
  const arr = []
  for (let i = 0; i < tg.length; i += 1) {
    const n = tg[i]
    if (map.has(n)) {
      arr.push(i - p)
      // 清空字典
      map.clear()
      p += 1
      // 使指针向右移一位
      i = p
      i = i - 1
    } else {
      map.set(n, i)
    }
  }
  if (arr.length === 0) {
    return map.size
  }

  const maxLength = arr.reduce((prev, cur) => {
    return Math.max(prev, cur)
  })

  return Math.max(map.size, maxLength)
}

const ml = lengthOfLongestSubstring('aau')
console.log(ml)

老师思路：

1. 用双指针维护一个滑动窗口，用来剪切子串
2. 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位
3. 过程中，记录所有窗口的长度，并返回最大值

代码：

var lengthOfLongestSubstring = function (s) {
  let l = 0
  let res = 0
  const map = new Map()
  for (let r = 0; r < s.length; r += 1) {
    // 以 abbcdea 举例，输出为 6，但是预期结果应该为 5，原因就是滑动窗口的左指针向左滑动了
    // 原本左指针指向的应该是第二个 b，但是 map.has(s[r]) 得到的是 0，显然在窗口外边了
    if (map.has(s[r]) && map.get(s[r]) >= l) {
      l = map.get(s[r]) + 1
    }
    res = Math.max(res, r - l + 1)
    map.set(s[r], r)
  }
  return res
}

---

时间复杂度：O(n)

空间复杂度：O(m)，m 是字符串中不重复字符的个数

6.6 最小覆盖子串(76)

解题思路：

• 先找出所有包含 T 的子串
• 找出长度最小的那个子串，返回即可

解题步骤：

• 用双指针维护一个滑动窗口
• 移动右指针，找到包含 T 的子串，移动左指针，尽量减少包含 T 的子串的长度
• 循环上述过程，找出包含 T 的最小子串

代码：

var minWindow = function (s, t) {
  let l = 0
  let r = 0
  const need = new Map()
  for (let c of t) {
    need.set(c, need.has(c) ? need.get(c) + 1 : 1)
  }
  let needType = need.size
  let res = ''
  while (r < s.length) {
    const c = s[r]
    if (need.has(c)) {
      need.set(c, need.get(c) - 1)
      if (need.get(c) === 0) needType -= 1
    }
    while (needType === 0) {
      const newRes = s.substring(l, r + 1)
      if (!res || newRes.length < res.length) res = newRes
      // // 左闭右开
      // console.log(s.substring(l, r + 1))
      const c2 = s[l]
      if (need.has(c2)) {
        need.set(c2, need.get(c2) + 1)
        if (need.get(c2) === 1) needType += 1
      }
      l += 1
    }
    r += 1
  }
  return res
}

时间复杂度：O(m + n) => m 是 t 的长度，n 是 s 的长度

空间复杂度：O(m)

7.树

7.1 简介

树是一种分层数据的抽象模型。前端的树包括 DOM 树、级联选择、树形控件。javascript 没有树，可以用 Object 和 Array 构建树

数的常用操作：

• 深度优先遍历
• 广度优先遍历
• 先中后序遍历

7.2 深度 / 广度优先遍历

基本介绍：

• 深度优先遍历（dfs）：尽可能深的搜索树的分支（如果有俩分支，就是一个分支走到底后再进入另一个分支）
• 广度优先遍历（bfs）：先访问离根节点最近的节点

深度优先遍历口诀：

• 访问根节点
• 对根节点的 children 挨个进行深度优先遍历

const tree = {
  val: 'a',
  children: [
    {
      val: 'b',
      children: [
        {
          val: 'd',
          children: []
        },
        {
          val: 'e',
          children: []
        }
      ]
    },
    {
      val: 'c',
      children: [
        {
          val: 'f',
          children: []
        },
        {
          val: 'g',
          children: []
        }
      ]
    }
  ]
}

const dfs = root => {
  // 访问根节点
  console.log(root.val) // a b d e c f g
  // 对根节点的 children 挨个进行深度优先遍历
  root.children.forEach(dfs)
}

dfs(tree)

广度优先遍历口诀：

• 新建一个队列，把根节点入队
• 把队头出队并访问
• 把队头的 children 挨个入队
• 重复第二、三步，直到队列为空

const tree = {
  val: 'a',
  children: [
    {
      val: 'b',
      children: [
        {
          val: 'd',
          children: []
        },
        {
          val: 'e',
          children: []
        }
      ]
    },
    {
      val: 'c',
      children: [
        {
          val: 'f',
          children: []
        },
        {
          val: 'g',
          children: []
        }
      ]
    }
  ]
}

const bfs = root => {
  // 新建一个队列，把根节点入队
  const q = [root]
  // 重复下面两步，直到队列为空
  while (q.length > 0) {
    // 把队头出队并访问
    const n = q.shift()
    console.log(n.val) // a b c d e f g
    n.children.forEach(child => {
      // 把队头的 children 挨个入队
      q.push(child)
    })
  }
}
bfs(tree)

7.3 二叉树的先中后序遍历 - 递归版

二叉树特点：

• 树中的每个节点最多只有两个子节点
• 在 JS 中通常用 Object 来模拟二叉树

先序遍历口诀：根 - 左 - 右

• 访问根节点
• 对根节点的左子树进行先序遍历
• 对根节点的右子树进行先序遍历

bt.js：

const bt = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
      left: null,
      right: null
    },
    right: {
      val: 5,
      left: null,
      right: null
    }
  },
  right: {
    val: 3,
    left: {
      val: 6,
      left: null,
      right: null
    },
    right: {
      val: 7,
      left: null,
      right: null
    }
  }
}

module.exports = bt

preorder.js：

const bt = require('./bt')

const preorder = root => {
  if (!root) return
  // 访问根节点
  console.log(root.val) // 1 2 4 5 3 6 7
  // 访问左子树
  preorder(root.left)
  // 访问右子树
  preorder(root.right)
}

preorder(bt)

---

中序遍历口诀：左 - 根 - 右

• 对根节点的左子树进行中序遍历
• 访问根节点
• 对根节点的右子树进行中序遍历

inorder.js：

const bt = require('./bt')

const inorder = root => {
  if (!root) return
  inorder(root.left)
  console.log(root.val) // 4 2 5 1 6 3 7
  inorder(root.right)
}

inorder(bt)

---

后序遍历口诀：左 - 右 - 根

• 对根节点的左子树进行后序遍历
• 对根节点的右子树进行后序遍历
• 访问根节点

const bt = require('./bt')

const postorder = root => {
  if (!root) return
  postorder(root.left)
  postorder(root.right)
  console.log(root.val) // 4 5 2 6 7 3 1
}

postorder(bt)

7.4 二叉树的先中后序遍历 - 非递归版

先序遍历：根-左-右

const bt = require('./bt')

// const preorder = (root) => {
//   if (!root) return
//   // 访问根节点
//   console.log(root.val) // 1 2 4 5 3 6 7
//   // 访问左子树
//   preorder(root.left)
//   // 访问右子树
//   preorder(root.right)
// }

const preorder = root => {
  if (!root) return
  const stack = [root]
  while (stack.length) {
    const n = stack.pop()
    console.log(n.val)
    if (n.right) stack.push(n.right)
    if (n.left) stack.push(n.left)
  }
}

preorder(bt)

中序遍历：左-根-右

const bt = require('./bt')

// const inorder = (root) => {
//   if (!root) return
//   inorder(root.left)
//   console.log(root.val) // 4 2 5 1 6 3 7
//   inorder(root.right)
// }

const inorder = root => {
  if (!root) return
  const stack = []
  let p = root
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    console.log(n.val)
    p = n.right
  }
}

inorder(bt)

typescript 版本：

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val
    this.left = left === undefined ? null : left
    this.right = right === undefined ? null : right
  }
}

// 左 -> 中 -> 右
function inorderTraversal(root: TreeNode | null): number[] {
  if (!root) return []
  const arr: Array<number> = []
  const stack: Array<TreeNode> = []
  // 这里的 undefined 类型相当重要，因为下面 p = p.left 不声明 undefined 是不会执行的
  let p: TreeNode | null | undefined = root
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    if (n) arr.push(n.val)
    if (n?.right) p = n.right
  }
  return arr
}

后序遍历：左-右-根

const bt = require('./bt')

// const postorder = (root) => {
//   if (!root) return
//   postorder(root.left)
//   postorder(root.right)
//   console.log(root.val) // 4 5 2 6 7 3 1
// }

// 后序遍历：左右根 => 根左右
const postorder = root => {
  if (!root) return
  const stack = [root]
  const outputStack = []
  while (stack.length) {
    const n = stack.pop()
    outputStack.push(n)
    // 下面两个操作与先序遍历相反
    if (n.left) stack.push(n.left)
    if (n.right) stack.push(n.right)
  }
  // 倒序输出
  while (outputStack.length) {
    const n = outputStack.pop()
    console.log(n.val)
  }
}

postorder(bt)

7.5 二叉树的最大深度(104)

这里为什么用先序遍历？答：因为二叉树的先序遍历类似深度优先遍历，都是在一个分支下遍历完节点再进行下一个分支

var maxDepth = function (root) {
  let res = 0
  const dfs = (n, l) => {
    if (!n) return
    // 如果是叶子结点
    if (!n.left && !n.right) res = Math.max(res, l)
    dfs(n.left, l + 1)
    dfs(n.right, l + 1) // 这时 n.right 相当于放入了栈中
  }
  dfs(root, 1)
  return res
}

时间复杂度：O(N)，节点数 N

空间复杂度：O(logN)

7.6 二叉树的最小深度(111)

使用广度优先遍历最好

var minDepth = function (root) {
  if (!root) return 0
  const q = [[root, 1]]
  while (q.length) {
    const [n, l] = q.shift()
    if (!n.left && !n.right) return l
    if (n.left) q.push([n.left, l + 1])
    if (n.right) q.push([n.right, l + 1])
  }
}

7.7 二叉树的层序遍历(102)

广度优先遍历

方法一：

const levelOrder = root => {
  if (!root) return []
  const q = [[root, 0]]
  const res = []
  while (q.length) {
    const [n, level] = q.shift()
    if (!res[level]) {
      res.push([n.val])
    } else {
      res[level].push(n.val)
    }
    if (n.left) q.push([n.left, level + 1])
    if (n.right) q.push([n.right, level + 1])
  }
  return res
}

方法二：

const levelOrder = root => {
  if (!root) return []
  const q = [root]
  const res = []
  while (q.length) {
    res.push([])
    let len = q.length
    // 保证 q 数组的成员都是当前层级的成员
    while (len--) {
      const n = q.shift()
      res[res.length - 1].push(n.val)
      if (n.left) q.push(n.left)
      if (n.right) q.push(n.right)
    }
  }
  return res
}

7.8 二叉树的中序遍历(94)

非递归版：

思路：1.先找到左叶子结点 -> 2.若无左节点，弹出并输出 -> 3.将指针指向弹出节点的右节点

const inorderTraversal = root => {
  const res = []
  const stack = []
  let p = root
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    res.push(n.val)
    p = n.right
  }
  return res
}

递归版：

只不过是把 log 部分变成推入数组

const inorderTraversal = root => {
  const res = []
  const rec = n => {
    if (!n) return
    rec(n.left)
    res.push(n.val)
    rec(n.right)
  }
  rec(root)
  return res
}

7.9 路径总和(112)

深度优先遍历

const hasPathSum = (root, sum) => {
  if (!root) return false
  let res = false
  const dfs = (n, s) => {
    if (!n.left && !n.right && s === sum) {
      res = true
    }
    if (n.left) dfs(n.left, s + n.left.val)
    if (n.right) dfs(n.right, s + n.right.val)
  }
  dfs(root, root.val)
  return res
}

7.10 遍历 JSON 的所有节点值

const json = {
  a: {
    b: {
      c: 1
    }
  },
  d: [1, 2]
}

const dfs = (n, path) => {
  console.log(n, path)
  Object.keys(n).forEach(k => {
    dfs(n[k], path.concat(k))
  })
}

dfs(json, [])

8.图

8.1 简介

图是什么？

• 图是网络结构的抽象模型，是一组由边连接的节点
• 图可以表示任何二元关系，比如道路、航班...

JS 中的图：

• 可以使用 Object 和 Array 构建图
• 图的表示法：邻接矩阵、邻接表、关联矩阵...

8.2 深度优先遍历

算法口诀：

• 访问根节点
• 对根节点的没访问过的相邻节点挨个进行深度优先遍历

---

graph.js：

const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3]
}

module.exports = graph

dfs.js：

const graph = require('./graph')

const visited = new Set()

const dfs = n => {
  console.log(n)
  visited.add(n)
  graph[n].forEach(c => {
    if (!visited.has(c)) {
      dfs(c)
    }
  })
}

// 起始节点是 2(根节点)
dfs(2) // 2 0 1 3

8.3 广度优先遍历

算法口诀：

• 新建一个队列，将根节点入队
• 把队头出队并访问
• 把队头的没访问过的相邻节点入队
• 重复第二三步，直到队列为空

---

bfs.js：

const graph = require('./graph')

const visited = new Set()
visited.add(2)
const q = [2]
while (q.length) {
  const n = q.shift()
  console.log(n)
  graph[n].forEach(c => {
    if (!visited.has(c)) {
      q.push(c)
      // 放在这个位置，是为了防止放在 const n = q.shift() 后面导致的重复元素的问题
      visited.add(n)
    }
  })
}

8.4 有效数字(65)

解题步骤：

• 构建一个表示状态的图
• 遍历字符串，并沿着图走，如果到了某个节点无路可走就返回 false
• 比那里结束，如果走到 3/5/6，就返回 true，否则返回 false

---

const isNumber = s => {
  const graph = {
    0: { blank: 0, sign: 1, '.': 2, digit: 6 },
    1: { digit: 6, '.': 2 },
    2: { digit: 3 },
    3: { digit: 3, e: 4, E: 4 },
    4: { digit: 5, sign: 7 },
    5: { digit: 5 },
    6: { digit: 6, '.': 3, e: 4, E: 4 },
    7: { digit: 5 }
  }
  let state = 0
  for (c of s.trim()) {
    if (c >= '0' && c <= '9') {
      c = 'digit'
    } else if (c === ' ') {
      c = 'blank'
    } else if (c === '+' || c === '-') {
      c = 'sign'
    }
    state = graph[state][c]
    if (state === undefined) return false
  }
  if (state === 3 || state === 5 || state === 6) {
    return true
  }
  return false
}

8.5 太平洋大西洋水流问题(417)

解题步骤：

• 新建两个矩阵，分别记录能流到两个大洋的坐标
• 从海岸线，多管齐下，同时深度优先遍历图，过程中填充上述矩阵
• 遍历两个矩阵，找到能流到两个大洋的坐标

---

const pacificAtlantic = matrix => {
  if (!matrix || !matrix[0]) return []
  // m 为行数
  const m = matrix.length
  // n 为列数
  const n = matrix[0].length
  // Array.from(参数一, 参数二)
  // 第一个参数为可迭代对象或者包含 length 属性的伪数组对象(也可以是 length 本身)
  // 第二个参数为数组中每一个成员的内容(这里就是一个大小为 n 的填充满 false 的数组)
  const flow1 = Array.from({ length: m }, () => new Array(n).fill(false))
  const flow2 = Array.from({ length: m }, () => new Array(n).fill(false))

  const dfs = (r, c, flow) => {
    flow[r][c] = true[([r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1])]?.forEach(
      ([nr, nc]) => {
        if (
          // 保证下一个节点在矩阵中
          nr >= 0 &&
          nr < m &&
          nc >= 0 &&
          nc < n &&
          // 防止死循环
          !flow[nr][nc] &&
          // 保证逆流而上
          matrix[nr][nc] >= matrix[r][c]
        ) {
          dfs(nr, nc, flow)
        }
      }
    )
  }

  // 沿着海岸线逆流而上
  for (let r = 0; r < m; r += 1) {
    // 第一列
    dfs(r, 0, flow1)
    // 最后一列
    dfs(r, n - 1, flow2)
  }
  for (let c = 0; c < n; c += 1) {
    // 第一行
    dfs(0, c, flow1)
    // 最后一行
    dfs(m - 1, c, flow2)
  }

  // 收集能流到两个大洋里的坐标
  const res = []
  for (let r = 0; r < m; r += 1) {
    for (let c = 0; c < n; c += 1) {
      if (flow1[r][c] && flow2[r][c]) {
        res.push([r, c])
      }
    }
  }
  return res
}

8.6 克隆图(133)

解题思路：

• 拷贝所有节点
• 拷贝所有的边

解体步骤：

• 深度或广度优先遍历所有节点
• 拷贝所有的节点，存储起来
• 将拷贝的节点，按照原图的连接方式进行连接

---

深度优先遍历：

const cloneGraph = node => {
  if (!node) return
  // 记录原来节点和拷贝节点的映射关系
  const visited = new Map()
  const dfs = n => {
    const nCopy = new Node(n.val)
    visited.set(n, nCopy)
    ;(n.neighbors || []).forEach(ne => {
      if (!visited.has(ne)) {
        dfs(ne)
      }
      nCopy.neighbors.push(visited.get(ne))
    })
  }
  dfs(node)
  return visited.get(node)
}

广度优先遍历：

const cloneGraph = node => {
  if (!node) return
  const visited = new Map()
  const q = [node]
  visited.set(node, new Node(node.val))
  while (q.length) {
    const n = q.shift()
    console.log(n.val)
    ;(n.neighbors || []).forEach(ne => {
      if (!visited.has(ne)) {
        q.push(ne)
        visited.set(ne, new Node(ne.val))
      }
      visited.get(n).neighbors.push(visited.get(ne))
    })
  }
  return visited.get(node)
}

9.堆

9.1 简介

上浮（shiftUp）（以构建最小堆为例）：

上浮操作就是，如果一个节点比它父节点小，则将它与父节点交换位置。这个节点在数组中的位置上升。

下沉（shiftDown）：

下沉操作就是，如果一个节点比它子节点大，那么它需要向下移动。称之为“下沉”。

堆是什么？

• 堆是一种特殊的完全二叉树（最下层靠右的可以不是满的，其余地方是满的）
• 所有的节点都大于等于（最大堆）或小于等于（最小堆）它的子节点

JS 中的堆：

• JS 通常用数组表示堆
• 左侧子节点位置为 2 * index + 1
• 右侧子节点位置为 2 * index + 2
• 父节点位置为 (index - 1) / 2

堆的应用：

• 能够高效快速地找出最大值最小值，时间复杂度：O(1)
• 找出第 K 个最大（小）元素

9.2 JavaScript 实现：最小堆类

插入：

• 将值插入堆的底部，即数组的尾部
• 然后上移：将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值
• 大小为 k 的堆中插入元素的时间复杂度为 O(logk)

class MinHeap {
  constructor() {
    this.heap = []
  }
  swap(i1, i2) {
    const temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }
  getParentIndex(i) {
    return (i - 1) >> 1 // 等同于 Math.floor((i - 1) / 2) 除二并向下取整
  }
  shiftUp(index) {
    if (index === 0) return
    const ParentIndex = this.getParentIndex(index)
    if (this.heap[ParentIndex] > this.heap[index]) {
      this.swap(ParentIndex, index)
      this.shiftUp(ParentIndex)
    }
  }
  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }
}

const h = new MinHeap()
h.insert(3)
h.insert(2)
h.insert(1)

删除堆顶：

• 用数组尾部元素替换堆顶（直接删除堆顶会破坏堆结构）
• 然后下移：将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶
• 大小为 k 的堆中删除堆顶的时间复杂度为 O(logk) - 主要花在堆高度上

class MinHeap {
  constructor() {
    this.heap = []
  }
  swap(i1, i2) {
    const temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }
  getParentIndex(i) {
    return (i - 1) >> 1 // 等同于 Math.floor((i - 1) / 2) 除二并向下取整
  }
  getLeftIndex(i) {
    return i * 2 + 1
  }
  getRightIndex(i) {
    return i * 2 + 2
  }
  shiftUp(index) {
    if (index === 0) return
    const ParentIndex = this.getParentIndex(index)
    if (this.heap[ParentIndex] > this.heap[index]) {
      this.swap(ParentIndex, index)
      this.shiftUp(ParentIndex)
    }
  }
  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    if (this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }
  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }
  pop() {
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
  }
}

const h = new MinHeap()
h.insert(3)
h.insert(2)
h.insert(1)
h.pop()

获取堆顶和堆的大小：

• 获取堆顶：返回数组的头部
• 获取堆的大小：返回数组的长度

class MinHeap {
  constructor() {
    this.heap = []
  }
  swap(i1, i2) {
    const temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }
  getParentIndex(i) {
    return (i - 1) >> 1 // 等同于 Math.floor((i - 1) / 2) 除二并向下取整
  }
  getLeftIndex(i) {
    return i * 2 + 1
  }
  getRightIndex(i) {
    return i * 2 + 2
  }
  shiftUp(index) {
    if (index === 0) return
    const ParentIndex = this.getParentIndex(index)
    if (this.heap[ParentIndex] > this.heap[index]) {
      this.swap(ParentIndex, index)
      this.shiftUp(ParentIndex)
    }
  }
  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    if (this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }
  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }
  pop() {
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
  }
  peak() {
    return this.heap[0]
  }
  size() {
    return this.heap.length
  }
}

const h = new MinHeap()
h.insert(3)
h.insert(2)
h.insert(1)
h.pop()

9.3 数组中的第 K 个最大元素(215)

解题步骤：

• 构建一个最小堆，并以此把数组的值插入堆中
• 当堆的容量超过 K，就删除堆顶
• 插入结束后，堆顶就是第 K 个最大元素

---

const findKthLargest = (nums, k) => {
  const h = new MinHeap()
  nums.forEach(n => {
    h.insert(n)
    if (h.size() > k) {
      h.pop()
    }
  })
  return h.peek()
}

时间复杂度：O(n) * 0(logk)（insert 和 pop 时间复杂度都为 logk，即堆的高度，而 forEach 时间复杂度为 n，故此）

空间复杂度：O(k)，k 即为参数 k

9.4 前 K 个高频元素(347)

下意识方法：

const topKFrequent = (nums, k) => {
  const map = new Map()
  // 统计每个元素出现的频率
  nums.forEach(n => {
    map.set(n, map.has(n) ? map.get(n) + 1 : 1)
  })
  // 将 map 映射转换为 [[-1, 1], [1, 1], [2, 2]] 的形式，并进行降序排序
  const list = Array.from(map).sort((a, b) => b[1] - a[1])
  // 由于返回的是一个二维数组，故通过 map 方法返回一个处理过后的一维数组
  return list.slice(0, k).map(n => n[0])
}

时间复杂度：由于 forEach 时间复杂度为 O(n)；sort 是原生的排序算法，也是最快的排序算法，时间复杂度为 O(n * logn)，但是不符合题目要求，因为时间复杂度必须要优于 O(n * logn)，而其不满足

---

使用堆：

class MinHeap {
  constructor() {
    this.heap = []
  }
  swap(i1, i2) {
    const temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }
  getParentIndex(i) {
    return (i - 1) >> 1
  }
  getLeftIndex(i) {
    return i * 2 + 1
  }
  getRightIndex(i) {
    return i * 2 + 2
  }
  shiftUp(index) {
    if (index === 0) return
    const ParentIndex = this.getParentIndex(index)
    // 这里加上了 ?.value 以适应这题
    if (this.heap[ParentIndex]?.value > this.heap[index]?.value) {
      this.swap(ParentIndex, index)
      this.shiftUp(ParentIndex)
    }
  }
  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    // 这里加上了 ?.value 以适应这题
    if (this.heap[leftIndex]?.value < this.heap[index]?.value) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    // 这里加上了 ?.value 以适应这题
    if (this.heap[rightIndex]?.value < this.heap[index]?.value) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }
  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }
  pop() {
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
  }
  peak() {
    return this.heap[0]
  }
  size() {
    return this.heap.length
  }
}

const topKFrequent = (nums, k) => {
  const map = new Map()
  nums.forEach(n => {
    map.set(n, map.has(n) ? map.get(n) + 1 : 1)
  })
  const h = new MinHeap()
  map.forEach((value, key) => {
    h.insert({ value, key })
    if (h.size() > k) {
      h.pop()
    }
  })
  return h.heap.map(a => a.key)
}

时间复杂度：O(n * logk)，优于 O(n * logn)

空间复杂度：O(n)

9.5 合并 K 个排序链表(23)

我的做法：

const mergeKLists = lists => {
  const newList = []
  lists?.forEach(a => {
    newList.push(...a)
  })
  newList.sort((a, b) => a - b)
  console.log(newList)
  return newList
}

const list = mergeKLists([
  [1, 4, 5],
  [1, 3, 4],
  [2, 6]
])
console.log(list)

---

解题步骤：

• 构建一个最小堆，并依次把链表头插入堆中
• 弹出堆顶接到输出链表，并将堆顶所在链表的新链表头插入堆中
• 等堆元素全部弹出，合并工作就完成了

class MinHeap {
  constructor() {
    this.heap = []
  }
  swap(i1, i2) {
    const temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }
  getParentIndex(i) {
    return (i - 1) >> 1 // 等同于 Math.floor((i - 1) / 2) 除二并向下取整
  }
  getLeftIndex(i) {
    return i * 2 + 1
  }
  getRightIndex(i) {
    return i * 2 + 2
  }
  shiftUp(index) {
    if (index === 0) return
    const ParentIndex = this.getParentIndex(index)
    if (this.heap[ParentIndex] && this.heap[ParentIndex].val > this.heap[index].val) {
      this.swap(ParentIndex, index)
      this.shiftUp(ParentIndex)
    }
  }
  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    if (this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }
  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }
  pop() {
    if (this.size() === 1) return this.heap.shift()
    const top = this.heap[0]
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
    return top
  }
  peak() {
    return this.heap[0]
  }
  size() {
    return this.heap.length
  }
}

const mergeKLists = lists => {
  const res = new ListNode(0)
  let p = res
  const h = new MinHeap()
  lists.forEach(l => {
    if (l) h.insert(l)
  })
  while (h.size()) {
    const n = h.pop()
    p.next = n
    p = p.next
    if (n.next) h.insert(n.next)
  }
  return res.next
}

时间复杂度：O(n * logk)

空间复杂度：O(k)

9.6 TS 实现：最小堆类

class MinHeap<T> {
  heap: T[]
  constructor() {
    this.heap = []
  }
  swap(i1: number, i2: number) {
    const temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }
  getParentIndex(i: number) {
    return (i - 1) >> 1
  }
  getLeftIndex(i: number) {
    return i * 2 + 1
  }
  getRightIndex(i: number) {
    return i * 2 + 2
  }
  shiftUp(index: number) {
    if (index === 0) return
    const parentIndex = this.getParentIndex(index)
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
    }
  }
  shiftDown(index: number) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    if (this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }
  insert(value: T) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }
  pop() {
    if (this.heap.length) {
      this.heap[0] = this.heap.pop() as T
      this.shiftDown(0)
    }
  }
  peek() {
    return this.heap[0]
  }
  size() {
    return this.heap.length
  }
}

10.排序和搜索

10.1 冒泡排序

思路：

• 比较所有相邻元素，如果第一个比第二个大，则交换它们
• 一轮下来，可以保证最后一个数是最大的
• 执行 n - 1 轮，就可以完成排序

---

Array.prototype.bubbleSort = function () {
  for (let i = 0; i < this.length - 1; i += 1) {
    for (let j = 0; j < this.length - 1 - i; j += 1) {
      if (this[j] > this[j + 1]) {
        const temp = this[j]
        this[j] = this[j + 1]
        this[j + 1] = temp
      }
    }
  }
  return this
}
const arr = [5, 4, 3, 2, 1]
arr.bubbleSort()

时间复杂度：两个嵌套循环 -> O(n^2)

10.2 选择排序

思路：

• 找到数组中的最小值，选中它并将其放置在第一位
• 找到数组中第二小的值，选中它并将其放置在第二位
• 以此类推，执行 n - 1 轮

---

Array.prototype.selectionSort = function () {
  for (let i = 0; i < this.length - 1; i += 1) {
    let indexMin = i
    for (let j = i; j < this.length; j += 1) {
      if (this[j] < this[indexMin]) {
        indexMin = j
      }
    }
    // 第三轮时已经是 [1, 2, 3, 4, 5]，此时 indexMin 为 2，且 i 也为 2，这是不应该交换
    if (indexMin !== i) {
      const temp = this[i]
      this[i] = this[indexMin]
      this[indexMin] = temp
    }
  }
}
const arr = [5, 4, 3, 2, 1]
arr.selectionSort()

时间复杂度：两个嵌套循环 -> O(n^2)

10.3 插入排序

插入排序的时间复杂度为 O(n^2)，但是在小型数组中插入排序比冒泡排序和选择排序的性能都要好

思路：

• 从第二个数开始往前比
• 比它大的往后排
• 以此类推进行到最后一个数

---

Array.prototype.insertionSort = function () {
  for (let i = 1; i < this.length; i += 1) {
    const temp = this[i]
    let j = i
    while (j > 0) {
      if (this[j - 1] > temp) {
        this[j] = this[j - 1]
      } else {
        break
      }
      j -= 1
    }
    this[j] = temp
  }
}
const arr = [5, 4, 3, 2, 1]
arr.insertionSort()

10.4 归并排序

事件复杂度为 O(n * logn)，火狐浏览器用的排序方法就是归并排序

思路：

• 分：把数组劈成两半，再递归地对子数组进行“分”操作，知道分成一个个单独的数
• 合：把两个数进行合并为有序数组，再对有序数组进行合并，知道全部子数组合并成为一个完整数组

合并两个有序数组：

• 新建一个空数组 res，用于存放最终排序后的数组
• 比较两个有序数组的头部，较小者出队并推入 res 中
• 如果两个数组还有值，就重复第二步

---

Array.prototype.mergeSort = function () {
  const rec = arr => {
    if (arr.length === 1) return arr
    const mid = Math.floor(arr.length / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid, arr.length)
    const orderLeft = rec(left)
    const orderRight = rec(right)
    const res = []
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
      } else if (orderLeft.length) {
        res.push(orderLeft.shift())
      } else if (orderRight.length) {
        res.push(orderRight.shift())
      }
    }
    return res
  }
  const res = rec(this)
  res.forEach((n, i) => {
    this[i] = n
  })
}
const arr = [5, 4, 3, 2, 1]
arr.mergeSort()

---

时间复杂度：

• 分的时间复杂度是 O(logN) -> 因为二分的事件复杂度就是这个
• 合的时间复杂度是 O(n) -> 因为有一个 while 循环体
• 时间复杂度：O(n * logN)

10.5 快速排序

chrome 曾经就用快速排序作为 sort 的算法。比前面的排序速度都要快

思路：

• 分区：从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面
• 递归：递归地对基准前后的子数组进行分区

---

Array.prototype.quickSort = function () {
  const rec = arr => {
    if (arr.length <= 1) return arr
    let left = []
    let right = []
    const base = arr[0]
    // 因为基准线是 arr[0]，所以从下标是 1 也就是第二个开始
    for (let i = 1; i < arr.length; i += 1) {
      if (arr[i] < base) {
        left.push(arr[i])
      } else {
        right.push(arr[i])
      }
    }
    return [...rec(left), base, ...rec(right)]
  }
  const res = rec(this)
  res.forEach((item, key) => {
    this[key] = item
  })
}

const arr = [1, 5, 9, 3, 18, 6, 2, 7]
arr.quickSort()
console.log(arr)

---

时间复杂度：

• 递归的时间复杂度是 O(logN)
• 分区操作的时间复杂度是 O(n)

10.6 顺序搜索

• 遍历数组
• 找到跟目标值相等的元素，就返回它的下标
• 遍历结束后，如果没有搜索到目标值，就返回 -1

---

Array.prototype.sequentialSearch = function (item) {
  for (let i = 0; i < this.length; i += 1) {
    if (this[i] === item) {
      return i
    }
  }
  return -1
}

const res = [1, 2, 3, 4, 5].sequentialSearch(3)

---

时间复杂度：

• 遍历数组是一个循环操作
• 时间复杂度：O(n)

10.7 二分搜索

思路：

• 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束
• 如果目标值大于或者小于中间元素，则在大于或小于中间元素的那一半数组中搜索

---

Array.prototype.binarySearch = function (item) {
  let low = 0
  let high = this.length - 1
  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    const element = this[mid]
    if (element < item) {
      low = mid + 1
    } else if (element > item) {
      high = mid - 1
    } else {
      return mid
    }
  }
  return -1
}

const res = [1, 2, 3, 4, 5].binarySearch(1)

时间复杂度：

• 每一次比较都使得搜索范围缩小一半
• 时间复杂度：O(logN)

TS 版本：

function search(nums: Array<number>, target: number): number {
  let mid: number,
    left = 0,
    right = nums.length - 1
  while (left <= right) {
    mid = left + ((right - left) >> 1)
    if (nums[mid] > target) right = mid - 1
    else if (nums[mid] < target) left = mid + 1
    else return mid
  }
  return -1
}

---

在排序数组中查找元素的第一个和最后一个位置(34)：

function searchRange(nums: number[], target: number): number[] {
  let leftFlag = false,
    rightFlag = false
  let left = 0,
    right = nums.length - 1
  const res = [-1, -1]
  while (left <= right) {
    if (res[0] >= 0 && res[1] >= 0) break
    if (!leftFlag) {
      if (nums[left] === target) {
        res[0] = left
        leftFlag = true
      } else {
        left++
      }
    }
    if (!rightFlag) {
      if (nums[right] === target) {
        res[1] = right
        rightFlag = true
      } else {
        right--
      }
    }
  }
  return res
}

console.log(searchRange([5, 7, 7, 8, 8, 10], 8))

10.8 合并两个有序链表(21)

类似并归排序算法

解题步骤：

• 新建一个新链表，作为返回结果
• 用指针遍历两个有序链表，并比较两个链表的当前节点，较小者先接入新链表，并将指针后移一步
• 链表遍历结束，返回新链表

---

const mergeTwoLists = function (l1, l2) {
  const res = new ListNode(0)
  let p = res
  let p1 = l1
  let p2 = l2
  while (p1 && p2) {
    if (p1.val < p2.val) {
      p.next = p1
      p1 = p1.next
    } else {
      p.next = p2
      p2 = p2.next
    }
    p = p.next
  }
  if (p1) {
    p.next = p1
  }
  if (p2) {
    p.next = p2
  }
  return res.next
}

10.9 猜数字大小(374)

解题步骤：

• 从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束
• 如果目标值大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找

---

const guessNumber = function (n) {
  let low = 1
  let high = n
  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    const res = guess(mid)
    if (res === 0) {
      return mid
    } else if (res === 1) {
      low = mid + 1
    } else {
      high = mid - 1
    }
  }
}

---

时间复杂度：O(logN)

空间复杂度：O(1)

10.10 总结

排序和搜索是什么？

• 排序：把某个乱序的数组变成升序或者降序的数组
• 搜索：找出数组中某个元素的下标

11.分而治之

11.1 简介

分而治之是什么？

• 分而治之是算法设计中的一种方法
• 它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题

场景一：归并排序

• 分：把数组从中间一分为二
• 解：递归地对两个子数组进行归并排序
• 合：合并有序子数组

场景二：快速排序

• 分：选基准，按基准把数组生成两个子数组
• 解：递归地把两个子数组进行快速排序
• 合：对两个子数组进行合并

11.2 猜数字大小(374)

时间复杂度：o(logN)，空间复杂度：logN，递归版（即这个）的空间复杂度反而不大好

const guessNumber = function (n) {
  const rec = (low, high) => {
    if (low > high) return
    const mid = Math.floor((low + high) / 2)
    const res = guess(mid)
    if (res === 0) {
      return mid
    } else if (res === 1) {
      return rec(mid + 1, high)
    } else {
      return rec(1, mid - 1)
    }
  }
  return rec(1, n)
}

11.3 反转二叉树(226)

解题步骤：

• 分：获取左右子树
• 解：递归地反转左右子树
• 合：将反转后的左右子树换个位置放到根节点上

---

const invertTree = function (root) {
  if (!root) {
    return null
  }
  return {
    val: root.val,
    left: invertTree(root.right),
    right: invertTree(root.left)
  }
}

---

时间复杂度：o(N)

空间复杂度：o(H)，H 为树的高度

11.4 相同的树(100)

解题思路：

• 两个树：根节点的值相同，左子树相同，右子树相同
• 符合"分、解、合"特性
• 考虑分而治之

---

const isSameTree = function (p, q) {
  if (!p && !q) return true
  if (
    p &&
    q &&
    p.val === q.val &&
    isSameTree(p.left, q.left) &&
    isSameTree(p.right, q.right)
  ) {
    return true
  } else {
    return false
  }
}

---

时间复杂度：o(N) => 遍历了所有节点

空间复杂度：o(N)

11.5 对称二叉树(101)

解题思路：

• 转化为：左右子树是否镜像
• 分解为：树 1 的左子树和树 2 的右子树是否镜像，树 1 的右子树和树 2 的左子树是否镜像

---

const isSymmetric = function (root) {
  if (!root) return true
  const isMirror = (l, r) => {
    if (!l && !r) return true
    if (
      l &&
      r &&
      l.val === r.val &&
      isMirror(l.left, r.right) &&
      isMirror(l.right, r.left)
    ) {
      return true
    } else {
      return false
    }
  }
  return isMirror(root.left, root.right)
}

时间复杂度：o(n) -> 访问了所有的节点

空间复杂度：o(n) -> 树的高度，最坏为 o(n)，二叉树均匀分布为 o(logn)

12.动态规划

12.1 简介

动态规划是什么？

• 动态规划是算法设计中的一种方法
• 它将一个问题分解为 相互重叠 的子问题，通过反复求解子问题，来解决原来的问题

斐波那契数列：

• 定义子问题：F(n) = F(n - 1) + F(n - 2)
• 反复执行：从 2 循环到 n，执行上述公式

动态规划 & 分而治之：

如果子问题是独立的，是分而治之；如果子问题是重叠的，是动态规划

12.2 爬楼梯(70)

解题思路：

• 爬到第 n 阶可以在第 n - 1 阶爬 1 个台阶，或者在第 n - 2 阶楼梯爬 2 个台阶
• F(n) = F(n - 1) + F(n - 2)
• 使用动态规划

---

const climbStairs = function (n) {
  if (n < 2) return 1
  const dp = [1, 1]
  for (let i = 2; i <= n; i += 1) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  console.log(dp)
  return dp[n]
}

时间复杂度：o(n) -> 有个 for 循环

空间复杂度：o(n) -> 有个线性数组

---

优化空间复杂度为 o(1)

const climbStairs = function (n) {
  if (n < 2) return 1
  let dp0 = 1
  let dp1 = 1
  for (let i = 2; i <= n; i += 1) {
    const temp = dp0
    dp0 = dp1
    dp1 = dp1 + temp
  }
  return dp1
}

12.3 打家劫舍(198)

解题思路：

这思路太牛了！

• f(k) = 从前 k 个房屋中能偷窃到的最大数额
• Ak = 第 k 个房屋的钱数
• f(k = max(f(k - 2) + Ak, f(k - 1)))

---

方法一：

const rob = function (nums) {
  if (nums.length === 0) return 0
  const dp = [0, nums[0]]
  for (let i = 2; i <= nums.length; i += 1) {
    dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1])
  }
  return dp[nums.length]
}

方法二：

减少空间复杂度为 o(1)

const rob = function (nums) {
  if (nums.length === 0) return 0
  // const dp = [0, nums[0]]
  let dp0 = 0
  let dp1 = nums[0]
  for (let i = 2; i <= nums.length; i += 1) {
    const dp2 = Math.max(dp0 + nums[i - 1], dp1)
    dp0 = dp1
    dp1 = dp2
  }
  return dp1
}

13.贪心算法

13.1 简介

贪心算法是什么？

• 贪心算法是算法设计中的一种方法
• 期盼通过每个阶段的局部最优选择，从而达到全局的最优
• 结果并不一定是最优

13.2 分发饼干(455)

解题思路：

• 局部最优：既能满足孩子，还消耗最少
• 先将"较小的饼干"发给"胃口最小"的孩子

解体步骤：

• 对饼干数组和胃口数组升序排序
• 遍历饼干数组，找到能满足第一个孩子的饼干
• 然后继续遍历饼干数组，找到满足第二、三、...、n 个孩子的饼干

---

const findContentChildren = function (g, s) {
  const sortFuc = function (a, b) {
    return a - b
  }
  g.sort(sortFuc)
  s.sort(sortFuc)
  let i = 0
  // 遍历饼干
  s.forEach(n => {
    if (n >= g[i]) {
      i += 1
    }
  })
  return i
}

---

时间复杂度：o(n * logn) * o(n) => o(n * logn)

空间复杂度：0(1)

13.3 买卖股票的最佳时机 ii(122)

解题思路：

• 上帝视角，知道未来的价格
• 局部最优：见好就收，见差就不动，不做任何长远打算

解题步骤：

• 新建一个变量，用来统计总利润
• 遍历价格数组，如果当前价格比昨天高，就在昨天买，今天卖，否则不交易
• 遍历结束后，返回所有利润之和

---

const maxProfit = function (prices) {
  let profit = 0
  for (let i = 1; i < prices.length; i += 1) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1]
    }
  }
  return profit
}

---

时间复杂度：o(n)

空间复杂度：o(1)

14.回溯算法

14.1 简介

回溯算法是什么？

• 回溯算法是算法设计中的一种方法
• 回溯算法是一种渐进式寻找并构建问题解决方式的策略
• 回溯算法会先从一个可能的动作开始解决问题，如果不行，就回溯并选择另一个动作，直到将问题解决

什么问题适合用回溯算法解决？

• 有很多路
• 这些路里，有死路，也有出路
• 通常需要递归来模拟所有的路

全排列：

• 用递归模拟出所有情况
• 遇到包含重复元素的情况，就回溯
• 收集所有到达递归终点的情况，并返回

14.2 全排列(46)

解题思路：

• 要求：1、所有排列情况；2、没有重复元素
• 有出路、有死路
• 考虑使用回溯算法

解题步骤：

• 用递归模拟出所有情况
• 遇到包含重复元素的情况，就回溯
• 收集所有到达递归终点的情况，并返回

---

const permute = function (nums) {
  const res = []
  const backtrack = path => {
    if (path.length === nums.length) {
      res.push(path)
      return
    }
    nums.forEach(n => {
      if (path.includes(n)) return
      backtrack(path.concat(n))
    })
  }
  backtrack([])
  return res
}

---

时间复杂度：o(n!)

空间复杂度：o(n)

14.3 子集(78)

解题步骤：

• 用递归模拟出所有情况
• 保证接的数字都是后面的数字
• 收集所有到达递归终点的情况，并返回

---

const subsets = function (nums) {
  const res = []
  const backtrack = (path, l, start) => {
    if (path.length === l) {
      res.push(path)
      return
    }
    for (let i = start; i < nums.length; i += 1) {
      backtrack(path.concat(nums[i]), l, i + 1)
    }
  }
  // 长度可以是 0 到 3(3 为数组的长度)
  for (let i = 0; i <= nums.length; i += 1) {
    backtrack([], i, 0)
  }
  return res
}

---

时间复杂度：o(2^N)，因为每个元素都存在两种可能

空间复杂度：o(N)

15.总结

15.1 总结

重点难点：

• 与前端最相关的数据结构是链表和树
• 链表 / 树 / 图的遍历、数组的排序和搜索很重要
• 设计思想重点看分而治之、动态规划，贪心、回溯次之

16.其他

16.1 字符串重复次数最多的字符

let str = 'abcabcabcbbccccc'

const obj = {}
let max = 0

for (let i = 0; i < str.length; i += 1) {
  const key = str[i]
  if (!obj[key]) {
    obj[key] = 1
  } else {
    obj[key] += 1
  }
  max = Math.max(obj[key], max)
}
const res = Object.keys(obj).find(key => obj[key] === max)

console.log(res) // c