数据结构

这块有一些基础了解即可（可以根据下面的关键词进行回忆），不打算去大厂的话不建议去刷题。

线性结构

数组与链表（优缺点、工程使用场景）

顺序表是通用底层容器，栈、队列、堆经常拿顺序表当底层实现。

Link 链表

约瑟夫环问题

问题描述

据说著名犹太历史学家 Josephus有过以下的故事：

在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友（共41个人）躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式：

41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而 Josephus 和他的朋友并不想遵从。

首先从一个人开始，越过 k-2 个人（因为第一个人已经被越过），并杀掉第 k 个人。
接着，再越过 k-1 个人，并杀掉第 k 个人。
这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

问题是一开始要站在什么地方才能避免自杀？Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第 16 个与第 31 个位置，于是逃过了这场死亡游戏。

数组下标方案

javascript

// 初始状态各坐标都赋值为0，被选中则标记为1
const arr = new Array(41).fill(0);
const key = 3;

// 最后会剩下2人，走掉39人
const numOfPeopleToLeave = arr.length - 2;

let count = 0;
while (arr.filter((checked) => checked === 1).length < numOfPeopleToLeave) {
  for (let i = 0, len = arr.length; i < len; i++) {
    // 如果数组中该坐标已被标记，则直接跳过
    if (arr[i] === 1) {
      continue;
    }
    count++;
    // 每到第key个人
    if (count === key) {
      // 标记数组中该坐标已被占位
      arr[i] = 1;
      count = 0;
    }
  }
}
// 输出标记情况，标记为0的表示未被选中，标记为1表示被选中
console.log(arr);

// 输出被留下的人（值为0）对应的坐标
console.log(
  arr
    .map((checked, idx) => (checked === 0 ? idx : undefined))
    .filter((idx) => typeof idx === "number"),
);

链表方案（单向循环链表）

如果是单向循环链表的话，对单个链表节点，有：

javascript

function Node(next) {
  this.next = next || null;
}

每当计数计到3时，将当前node节点的上一个节点的next指向当前node节点的下一个节点，然后继续从1开始计数，代码就不写了，虽说数据结构上和数组下标方案不同，逻辑是差不多的，while循环的终止条件可以换成当当前节点next指向null时。

合并2个排序链表

问题描述

输入两个单调递增的链表，输出两个链表合成后的链表，要求合成后的链表满足单调不减规则。

递归版本

javascript

function merge(pHead1, pHead2) {
  let node = null;
  if (pHead1 === null) {
    return pHead2;
  } else if (pHead2 === null) {
    return pHead1;
  }

  if (pHead1.val >= pHead2.val) {
    node = pHead2;
    node.next = merge(pHead1, pHead2.next);
  } else {
    node = pHead1;
    node.next = merge(pHead1.next, pHead2);
  }
  return node;
}

非递归版本

javascript

function merge(pHead1, pHead2) {
  if (pHead1 === null) {
    return pHead2;
  } else if (pHead2 === null) {
    return pHead1;
  }
  let node = null;
  let startNode = null;
  if (pHead1.val <= pHead2.val) {
    node = pHead1;
    startNode = pHead1;
    pHead1 = pHead1.next;
  } else {
    node = pHead2;
    startNode = pHead2;
    pHead2 = pHead2.next;
  }
  while (pHead1 !== null && pHead2 !== null) {
    if (pHead1.val <= pHead2.val) {
      node.next = pHead1;
      node = pHead1;
      pHead1 = pHead1.next;
    } else {
      node.next = pHead2;
      node = pHead2;
      pHead2 = pHead2.next;
    }
  }
  if (pHead1 !== null) {
    node.next = pHead1;
  } else if (pHead2 !== null) {
    node.next = pHead2;
  }
  return startNode;
}

广义表（Generalized List）

栈、队列、双端队列

Stack 栈

受限线性表，LIFO。

括号闭合问题

问题描述

给定一个只包括 (，)，{，}，[，]的字符串 s，判断字符串是否有效，即满足如下条件：

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

如：

有效的字符串："()"、"()[]{}"、"{[]}"。
无效的字符串："(]"、"([)]"。

解决方案

javascript

function isStrValid(str) {
  const matches = ["()", "[]", "{}"];
  const arr = [];
  for (let i = 0, len = str.length; i < len; i++) {
    const char = str.charAt(i);
    if (arr.length === 0) {
      arr.push(char);
      continue;
    }
    const last = arr[arr.length - 1];
    if (matches.includes(last + char)) {
      arr.pop();
      continue;
    }
    arr.push(char);
  }
  return arr.length === 0;
}

字符消消乐

问题描述

给定一个字符串，消除其中所有的字符串 ac 和 b，如果消掉之后获得的新字符串中仍存在可消内容则需要继续消，直到没有可继续消的字符串为止。

比如字符串 aaaaaaaaabbbbbbbcccccbbbbbcccc 经过处理后应该得到空字符串。

解决方案

javascript

function deleteMatchStr(str) {
  const arr = str.split("");
  const tempArr = [];
  arr.forEach((item) => {
    const last = tempArr.length ? tempArr[tempArr.length - 1] : "";
    if (last + item === "ac") {
      tempArr.pop();
      return;
    }
    if (item !== "b") {
      tempArr.push(item);
    }
  });
  return tempArr.join("");
}
deleteMatchStr("aaaaaaaaabbbbbbbcccccbbbbbcccc");

去重返回最小数

单调栈（Monotone stack）

单调栈是一种特殊的栈结构，其内部元素的排序是单调朝一个方向的。在许多数组的范围查询问题上，用上单调栈可显著降低时间复杂度——毕竟其时间复杂度只有 O(N)。

问题描述

这是 LeetCode 里的一道难度级别显示为中等的题目。

题目：给定一串数字, 去除字符串中重复的数字, 而且不能改变数字之间的顺序，使得返回的数字最小 "23123" => "123" "32134323" => "1342"。

解决方案

javascript

function handleArray(strings) {
  const array = strings.split("");
  const stack = [];
  const obj = {};

  for (let i = 0, len = array.length; i < len; i++) {
    const item = array[i];
    if (stack.length === 0) {
      stack.push(item);
      continue;
    }
    const lastStackItem = stack[stack.length - 1];
    while (lastStackItem >= item && array.slice(i).includes(lastStackItem)) {
      stack.pop();
    }
    if (!stack.includes(item)) {
      stack.push(item);
    }
  }

  return stack.join("");
}
handleArray("23123");
handleArray("32134323");

队列（Queue）

受限线性表，FIFO。

哈希表、哈希冲突、解决方式

树形结构

普通二叉树、遍历（前中后层序）

二叉搜索树

二叉树的构造

构造实现

javascript

// 节点对象的构造函数
function Node(data, left, right) {
  this.data = data;
  this.left = left;
  this.right = right;
}

Node.prototype.getData = function () {
  return this.data;
};

// 二叉搜索树的构造函数
function BST() {
  this.root = null;
}

// 插入方法
BST.prototype.insert = function (data) {
  const n = new Node(data, null, null);
  if (this.root === null) {
    this.root = n;
    return;
  }
  let current = this.root;
  let parent;
  while (true) {
    parent = current;
    if (data < current.data) {
      current = current.left;
      if (current === null) {
        parent.left = n;
        break;
      }
    } else {
      current = current.right;
      if (current === null) {
        parent.right = n;
        break;
      }
    }
  }
};

const nums = new BST();
nums.insert(8);
nums.insert(3);
nums.insert(10);
nums.insert(1);
nums.insert(6);
nums.insert(14);
nums.insert(4);
nums.insert(7);
nums.insert(13);

前序遍历

前序遍历（根节点 > 左子树 > 右子树）

8 => 3 => 1 => 6 => 4 => 7 => 10 => 14 => 13

前序遍历的递归实现

javascript

// 前序遍历二叉树
BST.prototype.preOrder = function (node) {
  if (node !== null) {
    console.log(node.getData());
    this.preOrder(node.left);
    this.preOrder(node.right);
  }
};

前序遍历的非递归实现

根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；访问其左子树后，再访问它的右子树。因此其处理过程如下：

对于任一结点P：

访问结点P，并将结点P入栈;
判断结点P的左孩子是否为空，

若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1；
若不为空，则将P的左孩子置为当前的结点P;

直到P为NULL并且栈为空，则遍历结束。

javascript

function preOrder(bst) {
  let p = bst.root;
  const arr = [];
  while (p !== null || arr.length > 0) {
    while (p !== null) {
      console.log(p.getData());
      arr.push(p);
      p = p.left;
    }

    if (arr.length > 0) {
      p = arr.pop();
      p = p.right;
    }
  }
}

中序遍历

中序遍历（左子树 > 根节点 > 右子树）

1 => 3 => 4 => 6 => 7 => 8 => 10 => 13 => 14

中序遍历的递归实现

javascript

// 中序遍历二叉树
BST.prototype.inOrder = function (node) {
  if (node !== null) {
    this.inOrder(node.left);
    console.log(node.getData());
    this.inOrder(node.right);
  }
};

中序遍历的非递归实现

根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：

对于任一结点P，

若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
直到P为NULL并且栈为空则遍历结束。

javascript

function inOrder(bst) {
  let p = bst.root;
  const arr = [];
  while (p !== null || arr.length > 0) {
    while (p !== null) {
      arr.push(p);
      p = p.left;
    }

    if (arr.length > 0) {
      p = arr.pop();
      console.log(p.getData());
      p = p.right;
    }
  }
}

后序遍历

后序遍历（左子树 > 右子树 > 根节点）

1 => 4 => 7 => 6 => 3 => 13 => 14 => 10 => 8

后序遍历的递归实现

javascript

// 后序遍历二叉树
BST.prototype.postOrder = function (node) {
  if (node !== null) {
    this.postOrder(node.left);
    this.postOrder(node.right);
    console.log(node.getData());
  }
};

后序遍历的非递归实现

后续遍历比前中/序遍历是要麻烦一些的。

遍历顺序：左右根。左路的遍历和上面的思路是类似的，区别是元素出栈时不能直接打印，因为如果有没访问过右侧子树的话，需要先访问右侧子树。右侧子树访问结束后才访问根节点。

javascript

function postOrder(bst) {
  let p = bst.root;
  let last = null;
  const arr = [];
  while (p !== null || arr.length > 0) {
    while (p !== null) {
      arr.push(p);
      p = p.left;
    }

    if (arr.length > 0) {
      p = arr[arr.length - 1]; // 栈顶元素
      // 当p不存在右子树或右子树已被访问过的话，直接访问当前节点数据
      if (!p.right || p.right === last) {
        p = arr.pop();
        console.log(p.getData());
        last = p; // 记录上一次访问过的节点
        p = null; // 这个容易漏掉，避免下个循环继续访问左子树
      } else {
        p = p.right;
      }
    }
  }
}

层次遍历

层次遍历（从上往下一层层来）

8 => 3 => 10 => 1 => 6 => 14 => 4 => 7 => 13

递归方案

javascript

// 遍历到某个节点后，将该节点的值推入到指定深度对应的数组中
function level(node, idx, arr) {
  if (arr.length < idx) {
    arr.push([]);
  }

  arr[idx - 1].push(node.value);

  if (node.left !== null) {
    level(node.left, idx + 1, arr);
  }

  if (node.right !== null) {
    level(node.right, idx + 1, arr);
  }
}

function levelOrder(root) {
  if (root === null) {
    return [];
  }

  const arr = [];
  level(root, 1, arr);
  return arr;
}

非递归方案

使用队列实现。

javascript

function levelOrder(root) {
  const arr = [];
  if (root === null) {
    return arr;
  }

  const queue = [root];

  while (queue.length > 0) {
    const currentLevel = [];
    const currentLevelLength = queue.length;
    for (let i = 0; i <= currentLevelLength; i++) {
      const node = queue.pop();
      currentLevel.push(node.value);

      if (node.left !== null) {
        queue.push(node.left);
      }
      if (node.right !== null) {
        queue.push(node.right);
      }
    }
    arr.push(currentLevel);
  }

  return arr;
}

平衡树、AVL、红黑树（工程理解）

B树、B+树（MySQL索引底层重点）

堆 Heap

二叉堆，不保证全局有序，根永远是极值，用于优先队列，不要和操作系统内存的堆 (heap) 混淆

数据结构

线性结构

数组与链表（优缺点、工程使用场景）

Link 链表

约瑟夫环问题

合并2个排序链表

广义表（Generalized List）

栈、队列、双端队列

Stack 栈

括号闭合问题

字符消消乐

去重返回最小数

队列（Queue）

哈希表、哈希冲突、解决方式

树形结构

普通二叉树、遍历（前中后层序）

二叉搜索树

二叉树的构造

前序遍历

中序遍历

后序遍历

层次遍历

平衡树、AVL、红黑树（工程理解）

B树、B+树（MySQL索引底层重点）

堆 Heap

图结构

图的存储方式：邻接矩阵、邻接表

深度优先 DFS

广度优先 BFS

数据结构 ​

线性结构 ​

数组与链表（优缺点、工程使用场景） ​

Link 链表 ​

约瑟夫环问题 ​

合并2个排序链表 ​

广义表（Generalized List） ​

栈、队列、双端队列 ​

Stack 栈 ​

括号闭合问题 ​

字符消消乐 ​

去重返回最小数 ​

队列（Queue） ​

哈希表、哈希冲突、解决方式 ​

树形结构 ​

普通二叉树、遍历（前中后层序） ​

二叉搜索树 ​

二叉树的构造 ​

前序遍历 ​

中序遍历 ​

后序遍历 ​

层次遍历 ​

平衡树、AVL、红黑树（工程理解） ​

B树、B+树（MySQL索引底层重点） ​

堆 Heap ​

图结构 ​

图的存储方式：邻接矩阵、邻接表 ​

深度优先 DFS ​

广度优先 BFS ​

数据结构

线性结构

数组与链表（优缺点、工程使用场景）

Link 链表

约瑟夫环问题

合并2个排序链表

广义表（Generalized List）

栈、队列、双端队列

Stack 栈

括号闭合问题

字符消消乐

去重返回最小数

队列（Queue）

哈希表、哈希冲突、解决方式

树形结构

普通二叉树、遍历（前中后层序）

二叉搜索树

二叉树的构造

前序遍历

中序遍历

后序遍历

层次遍历

平衡树、AVL、红黑树（工程理解）

B树、B+树（MySQL索引底层重点）

堆 Heap

图结构

图的存储方式：邻接矩阵、邻接表

深度优先 DFS

广度优先 BFS