数据结构

基础数据结构¶

数组、字符串 Array & String
链表 Linked List
栈 Stack
队列 / 双端队列 Queue & Deque
树 Tree

数组、字符串¶

优点
- 构建简单
- 可在 O(1) 时间内通过下标访问元素
缺点
- 构建时必须分配连续空间
- 查询元素是否存在，需要 O(n) 时间

242. 有效的字母异位词¶

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
  let count = {};

  for(let i = 0; i < s.length; i++) {
    count[s[i]] = count[s[i]] ? count[s[i]] + 1 : 1;
  }

  for(let i = 0; i < t.length; i++) {
    if (!count[t[i]]) {
      return false;
    }
    count[t[i]]--;
  }

  for(let p in count) {
    if (count[p] !==0) {
      return false;
    }
  }

  return true;
};

链表¶

优点
- 灵活分配内存空间
- 可在 O(1) 时间添加或删除元素
缺点
- 查询元素是否存在，需要 O(n) 时间
解题技巧
- 块慢指针，多则三个
- 创建虚假链表头

25. K 个一组翻转链表¶

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
  let length = 0;
  let dumpy = head;
  while (head) {
    length++;
    head = head.next
  }
  head = dumpy;

  let prev = null;
  let curr = head;
  let next;

  let fast;
  let slow;

  for(let i = 0; i < Math.floor(length / k); i++) {
    fast = curr;

    for(let j = 0; j < k; j++) {
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    if (slow) {
      slow.next = prev;
    }
    slow = fast;

    if (i === 0) { head = prev; }
  }

  if (slow) {
    slow.next = curr;
  }

  return head;
};

递归解法

var reverseKGroup = function(head, k) {
  let length = 0;
  let dumpy = head;
  while (head) {
    length++;
    head = head.next
  }
  head = dumpy;

  if (length < k) {
    return head;
  }

  let prev = null;
  let curr = head;
  let next;
  for(let j = 0; j < k; j++) {
    next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  dumpy.next = reverseKGroup(curr, k)

  head = prev;
  return head;
};

栈¶

先进后出
只关心栈顶的操作

739. 每日温度¶

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
  const result = [];

  const stack = []; // 存放下标
  for(let i = 0; i < T.length; i++) {
    let top = stack[stack.length - 1];
    while(T[top] < T[i]) {
      stack.pop();
      result[top] = i - top;
      top = stack[stack.length - 1];
    }

    stack.push(i);
  }

  while(stack.length > 0) {
    let top = stack.pop()
    result[top] = 0;
  }

  return result;
};

队列 / 双端队列¶

先进先出
可以双联表实现

239. 滑动窗口最大值¶

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
  const result = [];

  const deque = []; // 存放下标
  for(let i = 0; i < nums.length; i++) {
    while(deque[0]  <= i - k) {
      deque.shift();
    }
    while(nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }
    deque.push(i);

    if (i >= k-1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
};

树¶

树你的共性
- 结构直观
- 天生的递归
树的形状
- 普通二叉树
- 平衡二叉树
- 完全二叉树
- 二叉搜索树
- 四叉树
- 多叉树
- 红黑树
- 自平衡二叉搜索树
遍历
- 前序遍历
- 中序遍历
- 后序遍历

230. 二叉搜索树中第K小的元素¶

算法思想：中序遍历到第 K 个元素。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
  let result = -1;

  let count = 0;
  InOrderTraverse(root, node => {
    count++;
    if (count === k) {
      result = node.val;
      return true;
    }
  });

  return result;
};

function InOrderTraverse(root, found) {
  if (!root) { return; }

  InOrderTraverse(root.left, found);
  if (found(root)) { return; }
  InOrderTraverse(root.right, found);
}

高级数据结构¶

优先队列 Priority Queue
图 Graph
前缀树 Trie
线段树 Segment Tree
树状数组 Fenwick Tree

优先队列¶

每次取出的元素是队列中优先级最高的
本质上是一个 二叉堆（Binary Heap）
可利用一个数组来实现完全二叉树
数组特性
1. array[0] 拥有最高优先级
2. 元素 array[i] 的 父节点 下标是 (i - 1) / 2
3. 元素 array[i] 的 左子节点 下标是 2 * i + 1
4. 元素 array[i] 的 右子节点 下标是 2 * i + 2
5. 数组中每个元素优先级高于它的两个子节点
基本操作
- 向上筛选（sift up）
- 向下筛选（sift down）
- 添加元素时，向上筛选；取出堆顶元素时，向下筛选
优先队列的初始化，时间复杂度实际上是 O(n)

代码¶

class PriorityQueue {
  constructor(comparator) {
    this.comparator = typeof comparator === 'function'
      ? comparator
      : ((a, b) => a <= b ? -1 : 1);
    this.list = [];
  }

  size() {
    return this.list.length;
  }

  top() {
    return this.list[0];
  }

  enqueue(value) {
    this.list.push(value);

    this.siftUp(this.list, this.size() - 1); // 自底向上 sift
  }

  dequeue() {
    this.swap(this.list, 0, this.size() - 1); // 首尾交换
    const value = this.list.pop();
    this.siftDown(this.list, 0); // 自顶向下 sift

    return value;
  }

  siftUp(list, index) {
    if (index === 0) {
      return;
    }

    const parentIndex = Math.floor((index - 1) / 2);
    if(this.comparator(list[parentIndex], list[index]) > 0) {
      this.swap(list, index, parentIndex);
    }

    this.siftUp(list, parentIndex);
  }

  siftDown(list, index) {
    if (index >= this.size() - 1) {
      return;
    }

    let left = index * 2 + 1;
    let right = index * 2 + 2;
    let max = index;

    if (left < this.size()) {
      if (this.comparator(list[max], list[left]) > 0) {
        max = left;
      }
    }
    if (right < this.size()) {
      if (this.comparator(list[max], list[right]) > 0) {
        max = right;
      }
    }

    if (max !== index) {
      this.swap(list, max, index);
      this.siftDown(list, max);
    }
  }

  swap(list, i, j) {
    let temp = list[i];
    list[i] = list[j];
    list[j] = temp;
  }
}

347. 前 K 个高频元素¶

大根堆解法

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
  const countMap = {};
  for(let i = 0; i < nums.length; i++) {
    countMap[nums[i]] = countMap[nums[i]] || 0;
    countMap[nums[i]]++;
  }

  const priorityTree = [];
  for(let key in countMap) {
    priorityTree.push({
      key,
      value: countMap[key]
    });
  }

  const result = [];
  for (let i = 0; i < k; i++) {
    buildHeap(priorityTree, 0);
    result[i] = priorityTree.shift().key;
  }

  return result;
};

function buildHeap(arr, i) {  
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  let max = i;

  if (left <= arr.length - 1) {
    buildHeap(arr, left)
    if (arr[max].value < arr[left].value) {
      max = left;
    }  
  }
  if (right <= arr.length - 1) {
    buildHeap(arr, right)
    if (arr[max].value < arr[right].value) {
      max = right;
    }
  }

  if (max === i) {
    return;
  }

  let temp = arr[i];
  arr[i] = arr[max];
  arr[max] = temp;

  buildHeap(arr, max);
}

优化思路

topk （前k大）用 小根堆，维护堆大小不超过 k 即可。每次压入堆前和堆顶元素比较，如果比堆顶元素还小，直接扔掉，否则压入堆。检查堆大小是否超过 k，如果超过，弹出堆顶。复杂度是 nlogk

避免使用大根堆，因为你得把所有元素压入堆，复杂度是 O(nlogn)，而且还浪费内存。如果是海量元素，那就挂了。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
  // 1. 收集词频
  const count = {};
  for(let i = 0; i < nums.length; i++) {
    count[nums[i]] = count[nums[i]] || 0;
    count[nums[i]]++;
  }
  const arr = Object.entries(count).map(([key, value]) => ({ key, value }));

  // 2. 建立小根堆
  const queue = new PriorityQueue((a, b) => {
    return a.value < b.value ? -1 : 1;
  });

  for(let i = 0; i < arr.length; i++) {
    if(queue.size() < k) {
      queue.enqueue(arr[i]);
    } else if (queue.top().value < arr[i].value) {
      queue.dequeue();
      queue.enqueue(arr[i]);
    }
  }

  return queue.list.map(i => i.key);
}

图¶

概念
- 阶/度
- 树/森林/环
- 有向图/无向图/完全有向图/完全无向图
- 连通图/连通分量
- 图的存储：邻接矩阵，邻接链表
算法
- 深度优先遍历/广度优先遍历
- 环的检测
- 拓扑排序
- 联合-查找方法（Union-Find）
- 最短路径算法：Dijkstra, Bellman-Ford, Floyd Warshall
- 连通性算法：Kasaraju, Trajan
- 图的着色，旅行商问题等

785. 判断二分图¶

算法思想：转化为图的着色问题。找到一个使用两种颜色的着色方案，使每条边的两顶点颜色不同。

/**
 * @param {number[][]} graph
 * @return {boolean}
 */
const marked = {};

var isBipartite = function(graph) {
  // 考虑图是否连通
  for(let i = 0; i < graph.length; i++) {
    if (!marked[i]) {
      if (!dfs(graph, i)) {
        return false;
      }
    }
  }

  return true;
};

function dfs(graph, root, visit) {
  const stack = [];

  stack.push(root);
  marked[root] = 'RED';
  visit && visit(root);

  while (stack.length) {
    let v = stack.pop();
    for(let i = 0; i < graph[v].length; i++) {
      let u = graph[v][i];
      if (!marked[u]) {
        // 没访问过
        stack.push(u);
        marked[u] = marked[v] === 'RED' ? 'BLUE' : 'RED';
        visit && visit(u);
      } else if (marked[u] === marked[v]){
        // 撞色
        return false;
      }
    }
  }

  return true;
}

空间复杂度 O(V)
时间复杂度 O(V + E)

前缀树¶

也称 字典树，常用于字典搜索
每个孩子至少包含两个基础属性
- chilren: 罗列每个分支包含的所有字符
- isEnd: 该节点是否为字符串结尾
根节点为空
除了根，所有节点都可能是单词结尾

212. 单词搜索 II¶

/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
class Node {
  constructor(key) {
    this.key = key;
    this.children = {};
    this.isEnd = false;
    this.word = null;
  }
}

class Trie {
  constructor(words = []) {
    this.root = new Node(null)

    if (words.length) {
      this.build(words);
    }
  }

  build(words) {
    for(let i = 0; i < words.length; i++) {
      let node = this.root;
      for (let c of words[i]) {
        node.children[c] =  node.children[c] || new Node(c);
        node = node.children[c];
      }
      node.isEnd = true;
      node.word = words[i];
    }
  }
}

function dfs(board, node, x, y, visit) {
  if (x < 0 || y < 0 || x > board.length - 1 || y > board[0].length - 1) {
    return;
  }

  const c = board[x][y];
  node = node.children[c];
  if (c === '#' || !node) {
    return;
  }
  board[x][y] = '#'; // 标记已访问

  if (node.isEnd) {
    console.log(node.word);
    visit && visit(node);
  }

  dfs(board, node, x - 1, y, visit);
  dfs(board, node, x + 1, y, visit);
  dfs(board, node, x, y - 1, visit);
  dfs(board, node, x, y + 1, visit);

  board[x][y] = c; // 一次递归结束之后，还原 board
}

var findWords = function(board, words) {
  let rows = board.length;
  let cols = rows > 0 && board[0].length;

  let trie = new Trie(words);
  console.log(trie);

  const result = new Set();
  for(let i = 0; i < rows; i++) {
    for(let j= 0; j < cols; j++) {
      dfs(board, trie.root, i, j, node => result.add(node.word))
    }
  }

  return Array.from(result);
};

线段树¶

线段树是一棵二叉树
一种按照二叉树形式存储数据的结构，每个节点保存的都是数组里某一段的总和。

315. 计算右侧小于当前元素的个数¶

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function(nums) {
  // TO DO
};

树状数组¶

也称 Binary Indexed Tree / Fenwick Tree
树状数组是多叉树
树状数组第一个元素为空节点
若 tree[y] 是 tree[x] 的父节点，则需满足 y = x - (x & (-x))
「树状数组」这个数据结构用于高效地解决「前缀和查询」与「单点更新」问题

数组 C 的值由数组 A 的哪些元素而来	数组 A 的元素个数
C[1] = A[1]	1
C[2] = A[1] + A[2]	2
C[3] = A[3]	1
C[4] = A[1] + A[2] + A[3] + A[4]	4
C[5] = A[5]	1
C[6] = A[5] + A[6]	2
C[7] = A[7]	1
C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8]	8

class FenwickTree {
  constructor(numers) {
    this.len = nums.length + 1;
    this.tree = []; // size: this.len + 1
    for (let i = 1; i <= len; i++) {
      this.update(i, nums[i]);
    }
  }

  static lowbit (x) {
    return x & (-x);
  }

  /**
   * 单点更新
   * @param i     原始数组索引 i
   * @param delta 变化值 = 更新以后的值 - 原始值
   */
  update(i, delta) {
    // 从下到上更新，注意，预处理数组，比原始数组的 len 大 1，故 预处理索引的最大值为 len
    while (i <= this.len) {
      this.tree[i] += delta;
      i += FenwickTree.lowbit(i);
    }
  }

  /**
   * 查询前缀和
   * @param i 前缀的最大索引，即查询区间 [0, i] 的所有元素之和
   */
  query(int i) {
    // 从右到左查询
    let sum = 0;
    while (i > 0) {
      sum += this.tree[i];
      i -= FenwickTree.lowbit(i);
    }
    return sum;
  }
}

308. 二维区域和检索 - 可变¶

求一个动态变化的二维矩阵里，任意子矩阵里数的总和。

// TO DO