[记录]我的数据结构学习路径

简介: [记录]我的数据结构学习路径

书单

《学习JavaScript数据结构与算法》
《大话数据结构》
《算法图解》
《剑指offer》

代码

/*
 * @Author: ADI
 * @Date: 2020-11-25 14:15:14
 * @LastEditors: ADI
 * @LastEditTime: 2020-12-19 15:34:17
 */
const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1
};
function defaultCompare(a, b) {
  if (a === b) {
    // {1}
    return 0;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; // {2}
}
// # 栈
class Stack {
  constructor() {
    this.items = [];
  }
  // 入栈
  push(item) {
    return this.items.push(item);
  }
  // 出栈
  pop() {
    return this.items.pop();
  }
  // 末位
  get peek() {
    return this.items[this.items.length - 1];
  }
  // 是否空栈
  get isEmpty() {
    return !this.items.length;
  }
  // 尺寸
  get size() {
    return this.items.length;
  }
  // 清空
  clear() {
    this.items = [];
  }
  // 打印
  print() {
    console.log("log:", this.items.toString());
  }
}

function testStack() {
  // 实例化一个栈
  const stack = new Stack();
  console.log(stack.isEmpty); // true

  // 添加元素
  stack.push(5);
  stack.push(8);

  // 读取属性再添加
  console.log(stack.peek); // 8
  stack.push(11);
  console.log(stack.size); // 3
  console.log(stack.isEmpty); // false
}
// testStack();

// # 队列
class Queue {
  constructor(items) {
    this.items = items || [];
  }
  // 添加
  enqueue(item) {
    this.items.push(item);
  }
  // 移除
  dequeue() {
    return this.items.shift();
  }
  // 第一个item
  front() {
    return this.items[0];
  }
  // 清除
  clear() {
    this.items = [];
  }
  // 大小
  get size() {
    return this.items.length;
  }
  // 是否为空
  get isEmpty() {
    return !this.items.length;
  }
  // 打印
  print() {
    console.log("print:", this.items.toString());
  }
}
function testQueue() {
  const queue = new Queue();
  console.log(queue.isEmpty); // true

  queue.enqueue("John");
  queue.enqueue("Jack");
  queue.enqueue("Camila");
  console.log(queue.size); // 3
  console.log(queue.isEmpty); // false
  queue.dequeue();
  queue.dequeue();
  queue.print(); // 'Camila'
}

// testQueue();

// # 优先队列
class PriorityQueue {
  constructor() {
    this.items = [];
  }
  enqueue(item, priority) {
    const queueItem = { item, priority };

    if (this.isEmpty) {
      this.items.push(queueItem);
    } else {
      const preIndex = this.items.findIndex(
        (item) => queueItem.priority < item.priority
      );
      console.log("preIndex", preIndex);
      if (preIndex > -1) {
        this.items.splice(preIndex, 0, queueItem);
      } else {
        this.items.push(queueItem);
      }
    }
  }
  dequeue() {
    return this.items.shift();
  }
  front() {
    return this.items[0];
  }
  clear() {
    this.items = [];
  }
  get size() {
    return this.items.length;
  }

  get isEmpty() {
    return !this.items.length;
  }

  print() {
    console.log(this.items);
  }
}
function testPriorityQueue() {
  const priorityQueue = new PriorityQueue();
  priorityQueue.enqueue("John", 2);
  priorityQueue.enqueue("Jack", 1);
  priorityQueue.enqueue("Camila", 1);
  priorityQueue.enqueue("Surmon", 3);
  priorityQueue.enqueue("skyRover", 2);
  priorityQueue.enqueue("司马萌", 1);
  priorityQueue.print();
}

// testPriorityQueue();

// # 循环队列
class LoopQueue extends Queue {
  constructor(items) {
    super(items);
  }
  getIndex(index) {
    const length = this.items.length;
    return index > length ? index % length : index;
  }
  find(index) {
    return !this.isEmpty ? this.items[this.getIndex(index)] : null;
  }
}
function testLoopQueue() {
  const loopQueue = new LoopQueue(["Surmon"]);
  loopQueue.enqueue("SkyRover");
  loopQueue.enqueue("Even");
  loopQueue.enqueue("Alice");
  console.log(loopQueue.size, loopQueue.isEmpty); // 4 false

  console.log(loopQueue.find(26)); // 'Evan'
  console.log(loopQueue.find(87651)); // 'Alice'
}

// testLoopQueue();

// # 链表
// 节点
class Node {
  constructor(item) {
    this.item = item;
    this.next = null;
  }
}
class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  append(item) {
    const node = new Node(item);
    let current = null;
    if (this.head === null) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.length++;
  }
  insert(position, item) {
    if (position >= 0 && position < this.length) {
      const node = new Node(item);
      let previous = null;
      let current = this.head;
      let index = 0;
      if (position === 0) {
        this.head = node;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        node.next = current;
        previous.next = node;
      }
      this.length++;
      return true;
    }
    return false;
  }
  removeAt(position) {
    if (position > -1 && position < this.length) {
      let previous = null;
      let current = this.head;
      let index = 0;
      if (position === 0) {
        this.head = current.next;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      this.length--;
      return current.item;
    }
    return null;
  }
  findIndex(item) {
    let current = this.head;
    let index = -1;
    while (current) {
      ++index;
      if (current.item === item) {
        return index;
      } else {
        current = current.next;
      }
    }
    return -1;
  }
  remove(item) {
    const index = this.findIndex(item);
    return this.removeAt(index);
  }
  isEmpty() {
    return !this.length;
  }
  size() {
    return this.length;
  }
  toString() {
    let current = this.head;
    let str = "";
    while (current) {
      str += `${current.item} ,`;
      current = current.next;
    }
    return str;
  }
}
function testLinkedList() {
  const linkedList = new LinkedList();

  console.log(linkedList);
  linkedList.append(1);
  linkedList.append(2);
  linkedList.append(3);
  linkedList.append(4);

  linkedList.insert(2, 33);
  console.log(linkedList.toString());
  linkedList.removeAt(linkedList.findIndex(1));
  console.log(linkedList.toString());
  console.log(linkedList.findIndex(2));
}

// testLinkedList();

// # 双向链表
class DoublyNode {
  constructor(item) {
    this.prev = null;
    this.next = null;
    this.item = item;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  append(item) {
    const node = new DoublyNode(item);
    let current = null;
    if (this.head === null) {
      this.head = node;
      this.tail = null;
    } else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
      node.prev = current;
      this.tail = node;
    }
    this.length++;
  }
  insert(position, item) {
    const node = new DoublyNode(item);
    let index = 0;
    let previous = null;
    let current = null;
    if (position > -1 && position < this.length) {
      if (position === 0) {
        if (this.head) {
          current = this.head;
          node.next = current;
          current.prev = node;
          this.head = node;
        } else {
          this.head = node;
          this.tail = null;
        }
      } else if (position === this.length - 1) {
        current = this.tail;
        node.prev = current;
        current.next = node;
        this.tail = node;
      } else {
        current = this.head;
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = node;
        current.prev = node;
        node.prev = previous;
        node.next = current;
      }
      this.length++;
      return true;
    }
    return false;
  }
  findIndex(item) {
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.item === item) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }
  removeAt(position) {
    if (position > -1 && position < this.length) {
      let previous = null;
      let current = null;
      let index = 0;
      if (position === 0) {
        current = this.head;
        this.head = current.next;
        this.head.prev = null;
        if (this.length === 1) {
          this.tail = null;
        }
      } else if (position === this.length - 1) {
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = null;
      } else {
        current = this.head;
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        current = current.next;
        previous.next = current;
        current.prev = previous;
      }
      this.length--;
      return current.item;
    }
    return false;
  }
  remove(item) {
    return this.removeAt(this.findIndex(item));
  }
  get isEmpty() {
    return !this.length;
  }
  get size() {
    return this.length;
  }
  toString() {
    const arr = [];
    let current = this.head;
    while (current) {
      arr.push(current);
      current = current.next;
    }
    return arr;
  }
}

function testDoublyLinkedList() {
  const list = new DoublyLinkedList();
  for (let index = 0; index < 5; index++) {
    list.append(index);
  }
  // list.removeAt(1);
  console.log("list.toString()", list.toString());
}
// testDoublyLinkedList();

// # 集合
class Set {
  constructor() {
    this.items = {};
  }
  has(value) {
    // eslint-disable-next-line no-prototype-builtins
    return this.items.hasOwnProperty(value);
  }
  add(value) {
    if (!this.has(value)) {
      this.items[value] = value;
      return true;
    }
    return false;
  }
  remove(value) {
    if (this.has(value)) {
      delete this.items[value];
      return true;
    }
    return false;
  }
  // 并集
  union(otherSet) {
    const unionSet = new Set();
    this.values.forEach((v, i) => unionSet.add(this.values[i]));
    otherSet.values.forEach((v, i) => unionSet.add(otherSet.values[i]));
    return unionSet;
  }
  // 交集
  intersection(otherSet) {
    const intersectionSet = new Set();
    this.values.forEach((v, i) => {
      if (otherSet.has(v)) {
        intersectionSet.add(v);
      }
    });
    return intersectionSet;
  }
  // 差集
  difference(otherSet) {
    const differenceSet = new Set();
    this.values.forEach((v, i) => {
      if (!otherSet.has(v)) {
        differenceSet.add(v);
      }
    });
    return differenceSet;
  }
  // 子集
  subset(otherSet) {
    if (this.size > otherSet.size) {
      return false;
    } else {
      return !this.values.some((v) => !otherSet.has(v));
    }
  }
  get size() {
    return Object.keys(this.items).length;
  }
  get values() {
    return Object.keys(this.items);
  }
}
function testSet() {
  const set = new Set();
  set.add(1);
  console.log(set.values); // ["1"]
  console.log(set.has(1)); // true
  console.log(set.size); // 1
  set.add(2);
  console.log(set.values); // ["1", "2"]
  console.log(set.has(2)); // true
  console.log(set.size); // 2
  set.remove(1);
  console.log(set.values); // ["2"]
  set.remove(2);
  console.log(set.values); // []
}
// testSet();

// # 字典
class Dictionary {
  constructor() {
    this.items = {};
  }
  set(key, value) {
    this.items[key] = value;
  }
  get(key) {
    return this.items[key];
  }
  remove(key) {
    delete this.items[key];
  }
  get keys() {
    return Object.keys(this.items);
  }
  get values() {
    return Object.values(this.items);
  }
}
function testDictionary() {
  const dictionary = new Dictionary();
  dictionary.set("Gandalf", "gandalf@email.com");
  dictionary.set("John", "johnsnow@email.com");
  dictionary.set("Tyrion", "tyrion@email.com");

  console.log(dictionary);
  console.log(dictionary.keys);
  console.log(dictionary.values);
  console.log(dictionary.items);
}

// testDictionary();

// # 散列表
class HashTable {
  constructor() {
    this.table = [];
  }
  // 散列函数
  static loseloseHashCode(key) {
    let hash = 0;
    for (const codePoint of key) {
      hash += codePoint.charCodeAt();
    }
    return hash % 37;
  }
  // 修改和增加元素
  put(key, value) {
    const position = HashTable.loseloseHashCode(key);
    console.log(`${position} - ${key}`);
    this.table[position] = value;
  }
  get(key) {
    return this.table[HashTable.loseloseHashCode(key)];
  }
  remove(key) {
    this.table[HashTable.loseloseHashCode(key)] = undefined;
  }
}
function testHashTable() {
  const hash = new HashTable();
  hash.put("Surmon", "surmon.me@email.com"); // 19 - Surmon
  hash.put("John", "johnsnow@email.com"); // 29 - John
  hash.put("Tyrion", "tyrion@email.com"); // 16 - Tyrion
  hash.put("yTrion", "tyrion@email.com22"); // 16 - Tyrion

  // 测试get方法
  console.log(hash);
}
// testHashTable();
class HashTableByLinkedList {
  constructor() {
    this.table = [];
  }
  // 散列函数
  static loseloseHashCode(key) {
    let hash = 0;
    for (const codePoint of key) {
      hash += codePoint.charCodeAt();
    }
    return hash % 37;
  }
  // 修改和增加元素
  put(key, value) {
    const position = HashTable.loseloseHashCode(key);
    if (this.table[position] === undefined) {
      this.table[position] = new LinkedList();
    }
    this.table[position].append({ key, value });
  }
  get(key) {
    const position = HashTable.loseloseHashCode(key);
    if (this.table[position] === undefined) return undefined;
    const getElementValue = (node) => {
      if (!node && !node.element) return undefined;
      if (Object.is(node.element.key, key)) {
        return node.element.value;
      } else {
        return getElementValue(node.next);
      }
    };
    return getElementValue(this.table[position].head);
  }
  remove(key) {
    const position = HashTable.loseloseHashCode(key);
    if (this.table[position] === undefined) return undefined;
    const getElementValue = (node) => {
      if (!node && !node.element) return false;
      if (Object.is(node.element.key, key)) {
        this.table[position].remove(node.element);
        if (this.table[position].isEmpty) {
          this.table[position] = undefined;
        }
        return true;
      } else {
        return getElementValue(node.next);
      }
    };
    return getElementValue(this.table[position].head);
  }
}

// # 树
// 二叉搜索树
class BinarySearchTreeNode {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  static BalanceFactor = {
    UNBALANCED_RIGHT: 1,
    SLIGHTLY_UNBALANCED_RIGHT: 2,
    BALANCED: 3,
    SLIGHTLY_UNBALANCED_LEFT: 4,
    UNBALANCED_LEFT: 5
  };
  insert(key) {
    const newNode = new BinarySearchTreeNode(key);
    const insertNode = (node, newNode) => {
      if (newNode.key < node.key) {
        if (node.left === null) {
          node.left = newNode;
        } else {
          insertNode(node.left, newNode);
        }
      } else {
        if (node.right === null) {
          node.right = newNode;
        } else {
          insertNode(node.right, newNode);
        }
      }
    };
    if (!this.root) {
      this.root = newNode;
    } else {
      insertNode(this.root, newNode);
    }
  }
  // 中序遍历
  inOrderTraverse(callback) {
    const inOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        inOrderTraverseNode(node.left, callback);
        callback(node.key);
        inOrderTraverseNode(node.right, callback);
      }
    };
    inOrderTraverseNode(this.root, callback);
  }
  // 前序遍历
  preOrderTraverse(callback) {
    const preOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        callback(node.key);
        preOrderTraverseNode(node.left, callback);
        preOrderTraverseNode(node.right, callback);
      }
    };
    preOrderTraverseNode(this.root, callback);
  }
  // 后序遍历
  postOrderTraverse(callback) {
    const postOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        postOrderTraverseNode(node.left, callback);
        postOrderTraverseNode(node.right, callback);
        callback(node.key);
      }
    };
    postOrderTraverseNode(this.root, callback);
  }
  // 三种遍历访问顺序的不同:
  //   - 先序遍历:节点本身 => 左侧子节点 => 右侧子节点
  //   - 中序遍历:左侧子节点 => 节点本身 => 右侧子节点
  //   - 后序遍历:左侧子节点 => 节点本身 => 右侧子节点
  min(node = this.root) {
    const minNode = (node) =>
      node ? (node.left ? minNode(node.left) : node.key) : null;
    return minNode(node);
  }
  max(node = this.root) {
    const maxNode = (node) =>
      node ? (node.right ? maxNode(node.right) : node.key) : null;
    return maxNode(node);
  }
  search(key) {
    const searchNode = (node, key) => {
      if (node === null) return false;
      if (node.key === key) return node;
      return searchNode(key < node.key ? node.length : node.right, key);
    };
    return searchNode(this.root, key);
  }
  remove(key) {
    const removeNode = (node, key) => {
      if (node === null) return false;
      if (node.key === key) {
        if (node.left === null && node.right === null) {
          const _node = node;
          node = null;
          return _node;
        } else {
          console.log("key", key);
        }
      } else if (node.left !== null && node.key > key) {
        if (node.left.key === key) {
          node.left.key = this.min(node.left.right).key;
          removeNode(node.left.right, node.left.key);
          return node.left;
        } else {
          return removeNode(node.left, key);
        }
      } else if (node.right !== null && node.key < key) {
        if (node.right.key === key) {
          node.right.key = this.min(node.right.right).key;
          removeNode(node.right.right, node.right.key);
          return node.right;
        } else {
          return removeNode(node.right, key);
        }
      } else {
        return false;
      }
      return removeNode(key < node.key ? node.left : node.right, key);
    };
    return removeNode(this.root, key);
  }
  getNodeHeight(node) {
    if (node === null) {
      return -1;
    }
    return (
      Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) +
      1
    );
  }
  getBalanceFactor(node) {
    const heightDifference =
      this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch (heightDifference) {
      case -2:
        return BinarySearchTree.BalanceFactor.UNBALANCED_RIGHT;
      case -1:
        return BinarySearchTree.BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
      case 1:
        return BinarySearchTree.BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
      case 2:
        return BinarySearchTree.BalanceFactor.UNBALANCED_LEFT;
      default:
        return BinarySearchTree.BalanceFactor.BALANCED;
    }
  }
}

function testBinarySearchTree() {
  const tree = new BinarySearchTree();
  tree.insert(4);
  tree.insert(3);
  tree.insert(5);
  tree.insert(6);
  console.log("tree", tree);
  console.log("tree.getNodeHeight(tree.root)", tree.getNodeHeight(tree.root));
  // tree.inOrderTraverse(node => {
  //   console.log("node", node);
  // });
  // console.log("tree.min", tree.min());
  // console.log("tree.max", tree.max());
  // console.log("tree.search(4)", tree.search(4));
}
// testBinarySearchTree();

// # 图
// 关联矩阵
class Graph {
  constructor() {
    this.vertices = [];
    this.adjList = new Dictionary();
  }
  // 添加顶点
  addVertex(v) {
    this.vertices.push(v);
    this.adjList.set(v, []);
  }
  // 添加线
  addEdge(v, w) {
    this.adjList.get(v).push(w);
    this.adjList.get(w).push(v);
  }
  toString() {
    return this.vertices.reduce((r, v, i) => {
      return this.adjList.get(v).reduce((r, w, i) => {
        return r + `${w} `;
      }, `${r}\n${v} => `);
    }, "");
  }
  // 广度优先遍历
  bfs(v, callback) {
    const read = [];
    const adjList = this.adjList;
    const pending = [v || this.vertices[0]];
    const readVertices = (vertices) => {
      vertices.forEach((key) => {
        // console.log("key", key);
        read.push(key);
        pending.shift();
        adjList.get(key).forEach((v) => {
          if (!pending.includes(v) && !read.includes(v)) {
            pending.push(v);
          }
        });
        if (callback) callback(key);
        // console.log("pending", pending);
        if (pending.length) readVertices(pending);
      });
    };
    readVertices(pending);
  }
  // 使用BFS寻找最短路径
  bfs2(v, callback) {
    const read = [];
    const adjList = this.adjList;
    const pending = [v || this.vertices[0]];
    const distances = new Dictionary();
    const predecessors = new Dictionary();
    const readVertices = (vertices) => {
      vertices.forEach((key) => {
        // console.log("key", key);
        read.push(key);
        pending.shift();
        distances.set(key, distances.get(key) || 0);
        predecessors.set(key, predecessors.get(key) || null);
        adjList.get(key).forEach((v) => {
          if (!pending.includes(v) && !read.includes(v)) {
            pending.push(v);
            distances.set(v, distances.get(key) + 1);
            predecessors.set(v, key);
          }
        });
        if (callback) callback(key);
        // console.log("pending", pending);
        if (pending.length) readVertices(pending);
      });
    };
    readVertices(pending);
    return { distances, predecessors };
  }
  // 打印路径
  distance(fromVertex = this.vertices[0]) {
    const vertices = this.vertices;
    const { distances, predecessors } = this.bfs2(fromVertex);
    vertices.forEach((toVertex) => {
      if (distances.get(toVertex)) {
        let preVertex = predecessors.get(toVertex);
        let slug = "";
        while (preVertex !== fromVertex) {
          slug = `${preVertex} - ${slug}`;
          preVertex = predecessors.get(preVertex);
        }
        slug = `${fromVertex} - ${slug}${toVertex}`;
        console.log("slug", slug);
        return slug;
      }
    });
  }
  // 深度优先算法
  bfs3(callback) {
    const read = [];
    const adjList = this.adjList;
    const readVertices = (vertices) => {
      vertices.forEach((key) => {
        if (read.includes(key)) return false;
        read.push(key);
        if (callback) callback(key);
        if (read.length !== this.vertices.length) {
          readVertices(adjList.get(key));
        }
      });
    };
    readVertices(adjList.keys);
  }
  //
  dfs4(callback) {
    let readTimer = 0;
    const read = [];
    const readTimes = [];
    const finishedTimes = [];
    const predecessors = [];
    const adjList = this.adjList;
    const readVertices = (vertices, predecessor) => {
      console.log("predecessor", predecessor);
      vertices.forEach((key) => {
        readTimer++;
        if (
          adjList.get(key).every((v) => read.includes(v)) &&
          !finishedTimes[key]
        ) {
          finishedTimes[key] = readTimer;
        }
        if (read.includes(key)) return false;
        readTimes[key] = readTimer;
        read.push(key);
        if (callback) callback(key);
        predecessors[key] = predecessors[key] || predecessor || null;
        if (read.length !== this.vertices.length) {
          readVertices(adjList.get(key), key);
        }
      });
    };
    readVertices(adjList.keys);
    return { readTimes, finishedTimes, predecessors };
  }
}

function testGraph() {
  const graph = new Graph();

  ["A", "B", "C", "D", "E", "F", "G", "H", "I"].forEach((c) =>
    graph.addVertex(c)
  );

  graph.addEdge("A", "B");
  graph.addEdge("A", "C");
  graph.addEdge("A", "D");
  graph.addEdge("C", "D");
  graph.addEdge("C", "G");
  graph.addEdge("D", "G");
  graph.addEdge("D", "H");
  graph.addEdge("B", "E");
  graph.addEdge("B", "F");
  graph.addEdge("E", "I");

  // console.log(graph.toString());
  // graph.bfs(graph.vertices[0], value =>
  //   console.log("Visited vertex: " + value),
  // );
  // const ret = graph.bfs2(graph.vertices[0], () => {});
  // console.log("ret", ret);

  // graph.distance();
  const ret2 = graph.dfs4((key) => console.log("key", key));
  console.log("ret2", ret2);
}

// testGraph();

function factorialIterative(num) {
  if (num <= 1) {
    return 1;
  }
  return num * factorialIterative(--num);
}
// console.log("factorialIterative(5)", factorialIterative(5));

function fibonacci(n) {
  if (n < 1) return 0;
  if (n <= 2) return 1;
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) {
    fibN = fibNMinus2 + fibNMinus1;
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}
function fibonacci2(n) {
  if (n < 1) return 0;
  if (n <= 2) return 1;
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) {
    fibN = fibNMinus2 + fibNMinus1;
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}

function fibonacci3(n) {
  if (n < 1) return 0;
  if (n <= 2) return 1;
  return fibonacci3(n - 1) + fibonacci3(n - 2);
}

function BTS() {
  class Node {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }
  class BinarySearchTree {
    constructor(value) {
      this.root = new Node(value);
    }
    _insertNode(node, value) {
      if (node.value > value) {
        if (node.left === null) {
          node.left = new Node(value);
        } else {
          this._insertNode(node.left, value);
        }
      } else {
        if (node.right === null) {
          node.right = new Node(value);
        } else {
          this._insertNode(node.right, value);
        }
      }
    }
    insert(value) {
      if (this.root === null) {
        this.root = new Node(value);
      } else {
        this._insertNode(this.root, value);
      }
      return this;
    }
    // 中序遍历: 左 -> 中 -> 右
    _inOrderTra(node, res) {
      if (node === null) {
        return;
      }
      this._inOrderTra(node.left, res);
      res.push(node.value);
      this._inOrderTra(node.right, res);
    }
    inOrderTra() {
      const res = [];
      this._inOrderTra(this.root, res);
      return res;
    }
    // 前序遍历: 中 -> 左 -> 右
    _preOrderTra(node, res) {
      if (node === null) {
        return;
      }
      res.push(node.value);
      this._preOrderTra(node.left, res);
      this._preOrderTra(node.right, res);
    }
    preOrderTra() {
      const res = [];
      this._preOrderTra(this.root, res);
      return res;
    }
    // 后序遍历: 左 -> 右 -> 中
    _postOrderTra(node, res) {
      if (node === null) {
        return;
      }
      this._postOrderTra(node.left, res);
      this._postOrderTra(node.right, res);
      res.push(node.value);
    }
    postOrderTra() {
      const res = [];
      this._postOrderTra(this.root, res);
      return res;
    }
    _getMin(node) {
      if (node.left === null) {
        return node;
      }
      return this._getMin(node.left);
    }
    getMin() {
      return this._getMin(this.root);
    }
    _getMax(node) {
      if (node.right === null) {
        return node;
      }
      return this._getMax(node.right);
    }
    getMax() {
      return this._getMax(this.root);
    }
    _search(node, value) {
      if (node.value > value) {
        if (node.left === null) {
          throw "Function Search: " + value + " 未找到";
        } else if (node.left.value === value) {
          return node.left;
        } else {
          return this._search(node.left, value);
        }
      } else {
        if (node.right === null) {
          throw "Function Search: " + value + " 未找到";
        } else if (node.right.value === value) {
          return node.right;
        } else {
          return this._search(node.right, value);
        }
      }
    }
    search(value) {
      if (value === this.root.value) {
        return this.root;
      }
      return this._search(this.root, value);
    }
    _removeNode(target, node = this.root) {
      // 寻找删除节点的父节点
      if (node.left !== target && node.right !== target) {
        if (node.value > target.value) {
          return this._removeNode(target, node.left);
        } else {
          return this._removeNode(target, node.right);
        }
      }
      if (target.left === null && target.right === null) {
        // 删除的节点无子节点
        return node.left === target ? (node.left = null) : (node.right = null);
      } else if (target.left === null || target.right === null) {
        // 删除的节点只包含一个子节点
        const son = target.left === null ? target.right : target.left;
        return node.left === target ? (node.left = son) : (node.right = son);
      } else if (target.left !== null && target.right !== null) {
        // 删除的节点包含两个子节点
        const displace = this._getMin(target.right);
        return node.left === target
          ? (node.left = displace)
          : (node.right = displace);
      }
    }
    remove(value) {
      const target = this.search(value);
      if (target === this.root) {
        throw "Function remove: 不能删除根节点";
      }
      this._removeNode(target);
      return this;
    }
  }

  class AVL extends BinarySearchTree {
    constructor(superConstructor) {
      super(superConstructor);
    }
    _getNodeHeight(node) {
      if (node === null) {
        return -1;
      }
      return (
        Math.max(
          this._getNodeHeight(node.left),
          this._getNodeHeight(node.right)
        ) + 1
      );
    }
    getNodeHeight(node = this.root) {
      return this._getNodeHeight(node);
    }
    getBalanceFactory(node) {
      const factory =
        this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
      return factory;
    }
    // 向右单旋转
    rotationLL(node) {
      const tar = node.left;
      try {
        node.left = tar.right;
      } catch {
        node.left = null;
      }
      tar.right = node;
      return tar;
    }
    // 向左单旋转
    rotationRR(node) {
      const tar = node.right;
      try {
        node.right = tar.left;
      } catch {
        node.right = null;
      }
      tar.left = node;
      return tar;
    }
    // 向右双旋转
    rotationRL(node) {
      node.right = this.rotationLL(node.right);
      return this.rotationRR(node);
    }
    // 向左双旋转
    rotationLR(node) {
      node.left = this.rotationRR(node.left);
      return this.rotationLL(node);
    }
    _changeToBalance(node) {
      let factoryLeft, factoryRight;
      switch (this.getBalanceFactory(node)) {
        case 2:
          factoryLeft = this.getBalanceFactory(node.left);
          if ([0, 1].indexOf(factoryLeft) !== -1 || factoryLeft > 2) {
            console.info("2 0 1");
            node = this.rotationLL(node);
          } else if (factoryLeft === -1) {
            console.info("2 -1");
            node = this.rotationLR(node);
          } else if (factoryLeft === 2) {
            console.info("2 2");
            node.left = this._changeToBalance(node.left);
          } else if (factoryLeft === -2) {
            console.info("2 -2");
            node.left = this._changeToBalance(node.left);
          }
          return node;
        case -2:
          factoryRight = this.getBalanceFactory(node.right);
          if ([0, 1].indexOf(factoryRight) !== -1) {
            console.info("-2 0 1");
            node = this.rotationRL(node);
          } else if (factoryRight === -1 || factoryRight < -2) {
            console.info("-2 -1");
            node = this.rotationRR(node);
          } else if (factoryRight === 2) {
            console.info("-2 2");
            node.right = this._changeToBalance(node.right);
          } else if (factoryRight === -2) {
            console.info("-2 -2");
            node.right = this._changeToBalance(node.right);
            console.info(node.right);
          }
          return node;
      }
      return node;
    }
    checkIsBalance() {
      this.root = this._changeToBalance(this.root);
      return this;
    }
    insert(value) {
      super.insert(value);
      return this.checkIsBalance();
    }
    remove(value) {
      super.remove(value);
      return this.checkIsBalance();
    }
  }

  const avlTree = new BinarySearchTree(0);

  avlTree.insert(1);
  avlTree.insert(2);
  avlTree.insert(3);
  avlTree.insert(4);
  avlTree.insert(5);
  avlTree.insert(6);
  avlTree.insert(7);
  avlTree.insert(14);
  avlTree.insert(15);
  avlTree.insert(13);
  avlTree.insert(12);
  avlTree.insert(11);
  console.log("avlTree", avlTree);
  console.log("avlTree.remove(15)", avlTree.remove(15));
  console.log("avlTree.inOrderTra()", avlTree.inOrderTra());
}

// BTS();

/**
 * 堆
 */
// 非叶子结点的下标为:i = Math.floor(arr.length/2 - 1)
// testHeap();
function testHeap() {
  const Compare = {
    LESS_THAN: -1,
    EQUALS: 0,
    BIGGER_THAN: 1
  };
  function defaultCompare(a, b) {
    if (a === b) {
      return Compare.EQUALS;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
  }
  function swap(array, a, b) {
    [array[a], array[b]] = [array[b], array[a]];
  }
  function reverseCompare(compareFn) {
    return (a, b) => compareFn(b, a);
  }
  class MinHeap {
    constructor(compareFn = defaultCompare) {
      this.compareFn = compareFn;
      this.heap = [];
    }
    getLeftIndex(index) {
      return 2 * index + 1;
    }
    getRightIndex(index) {
      return 2 * index + 2;
    }
    getParentIndex(index) {
      if (index === 0) {
        return undefined;
      }
      return Math.floor((index - 1) / 2);
    }
    size() {
      return this.heap.length;
    }
    isEmpty() {
      return this.size() <= 0;
    }
    clear() {
      this.heap = [];
    }
    getAsArray() {
      return this.heap;
    }
    findMinimum() {
      return this.isEmpty() ? undefined : this.heap[0];
    }
    insert(value) {
      if (value != null) {
        this.heap.push(value);
        const index = this.heap.length - 1;
        this.siftUp(index);
        return true;
      }
      return false;
    }
    siftUp(index) {
      let parent = this.getParentIndex(index);
      while (
        index > 0 &&
        this.compareFn(this.heap[parent], this.heap[index]) ===
          Compare.BIGGER_THAN
      ) {
        swap(this.heap, parent, index);
        index = parent;
        parent = this.getParentIndex(index);
      }
    }
    extract() {
      if (this.isEmpty()) {
        return undefined;
      }
      if (this.size() == 1) {
        return this.heap.shift();
      }
      const removedValue = this.heap[0];
      this.heap[0] = this.heap.pop();
      this.siftDown(0);
      return removedValue;
    }
    siftDown(index) {
      let element = index;
      const left = this.getLeftIndex(index);
      const right = this.getRightIndex(index);
      const size = this.size();
      if (
        left < size &&
        this.compareFn(this.heap[element], this.heap[left]) ===
          Compare.BIGGER_THAN
      ) {
        element = left;
      } else if (
        right < size &&
        this.compareFn(
          this.heap[element],
          this.heap[right] === Compare.BIGGER_THAN
        )
      ) {
        element = right;
      }
      if (index !== element) {
        swap(this.heap, index, element);
        this.siftDown(element);
      }
    }
    heapify(array) {
      if (array) {
        this.heap = array;
      }
      const maxIndex = Math.floor(this.size() / 2) - 1;
      for (let i = 0; i <= maxIndex; i++) {
        this.siftDown(i);
      }
      return this.heap;
    }
  }

  const heap = new MinHeap();
  heap.insert(2);
  heap.insert(3);
  heap.insert(4);
  heap.insert(5);
  // console.log(heap);

  class MaxHeap extends MinHeap {
    constructor(compareFn = defaultCompare) {
      super(compareFn);
      this.compareFn = compareFn;
      this.compareFn = reverseCompare(compareFn);
    }
  }
  function heapify(array, index, heapSize, compareFn) {
    let largest = index;
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    // console.log(
    //   "array, index, left, right, heapSize",
    //   array,
    //   index,
    //   left,
    //   right,
    //   heapSize
    // );
    if (left < heapSize && compareFn(array[left], array[index]) > 0) {
      largest = left;
    }
    if (right < heapSize && compareFn(array[right], array[largest]) > 0) {
      largest = right;
    }
    if (largest !== index) {
      swap(array, index, largest);
      heapify(array, largest, heapSize, compareFn);
    }
  }

  function buildMaxHeap(array, compareFn) {
    for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
      heapify(array, i, array.length, compareFn);
    }
    return array;
  }

  function heapSort(array = [], compareFn = defaultCompare) {
    let heapSize = array.length;
    const ret = buildMaxHeap(array, compareFn);
    console.log("buildMaxHeap(array, compareFn)", ret);
    while (heapSize > 1) {
      swap(array, 0, --heapSize);
      heapify(array, 0, heapSize, compareFn);
    }
    return array;
  }

  const array = [5, 3, 6];

  // console.log("Before sorting: ", array);
  // console.log("After sorting: ", heapSort(array));
}

testGraph();
function testGraph() {
  class Graph {
    constructor(isDirected = false) {
      this.isDirected = isDirected;
      this.vertices = [];
      this.adjList = new Dictionary();
    }
    addVertex(v) {
      if (!this.vertices.includes(v)) {
        this.vertices.push(v);
        this.adjList.set(v, []);
      }
    }
    addEdge(v, w) {
      if (!this.adjList.get(v)) {
        this.addVertex(v);
      }
      if (!this.adjList.get(w)) {
        this.addVertex(w);
      }
      this.adjList.get(v).push(w);
      if (!this.isDirected) {
        this.adjList.get(w).push(v);
      }
    }
    getVertices() {
      return this.vertices;
    }
    getAdjList() {
      return this.adjList;
    }
    toString() {
      let s = "";
      for (let i = 0; i < this.vertices.length; i++) {
        s += `${this.vertices[i]} -> `;
        const neighbors = this.adjList.get(this.vertices[i]);
        for (let j = 0; j < neighbors.length; j++) {
          s += `${neighbors[j]} `;
        }
        s += "\n";
      }
      return s;
    }
  }
  const Colors = {
    WHITE: 0,
    GREY: 1,
    BLACK: 2
  };
  const initializeColor = (vertices) => {
    const color = {};
    for (let i = 0; i < vertices.length; i++) {
      color[vertices[i]] = Colors.WHITE;
    }
    return color;
  };
  // 广度优先搜索
  const breadthFirstSearch = (graph, startVertex, callback) => {
    // 顶点
    const vertives = graph.getVertices();
    // 联表
    const adjList = graph.getAdjList();
    // 初始化颜色
    const color = initializeColor(vertives);
    // 队列
    const queue = new Queue();
    // 添加头顶点
    queue.enqueue(startVertex);
    // 当队列不为空时
    while (!queue.isEmpty) {
      const u = queue.dequeue();
      const neighbors = adjList.get(u);
      color[u] = Colors.GREY;
      // 循环联表节点
      for (let i = 0; i < neighbors.length; i++) {
        const w = neighbors[i];
        // 当节点为白色添加到队列中
        if (color[w] === Colors.WHITE) {
          color[w] = Colors.GREY;
          queue.enqueue(w);
        }
      }
      // 设置节点为黑色
      color[u] = Colors.BLACK;
      // 调用callback
      callback && callback(u);
    }
  };
  // 最短路径搜索
  const BFS = (graph, startVertex) => {
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();
    const color = initializeColor(vertices);
    const queue = new Queue();
    // 间距字典
    const distances = {};
    // 上一个节点字典
    const predecessors = {};
    queue.enqueue(startVertex);
    // 初始化字典
    for (let i = 0; i < vertices.length; i++) {
      distances[vertices[i]] = 0;
      predecessors[vertices[i]] = null;
    }
    // 循环遍历队列
    while (!queue.isEmpty) {
      const u = queue.dequeue();
      const neighbors = adjList.get(u);
      // 设置当前节点为灰色
      color[u] = Colors.GREY;
      // 遍历子节点
      for (let i = 0; i < neighbors.length; i++) {
        const w = neighbors[i];
        // 子节点为白色时,添加间距字典与记录上一个节点字典,添加到待遍历队列
        if (color[w] === Colors.WHITE) {
          color[w] = Colors.GREY;
          distances[w] = distances[u] + 1;
          predecessors[w] = u;
          queue.enqueue(w);
        }
      }
      // 节点遍历结束标记会黑色
      color[u] = Colors.BLACK;
    }
    return {
      distances,
      predecessors
    };
  };
  // 深度优先搜索
  const depthFirstSearchVisit = (u, color, adjList, callback) => {
    color[u] = Colors.GREY;
    if (callback) {
      callback(u);
    }
    const neighbors = adjList.get(u);
    for (let i = 0; i < neighbors.length; i++) {
      const w = neighbors[i];
      if (color[w] === Colors.WHITE) {
        depthFirstSearchVisit(w, color, adjList, callback);
      }
    }
    color[u] = Colors.BLACK;
  };
  // DFS
  const DFS = (graph) => {
    const vertives = graph.getVertices();
    const adjList = graph.getAdjList();
    const color = initializeColor(vertives);
    // 距离字典
    const d = {};
    // 首次完成时间
    const f = {};
    // 前一个节点字典
    const p = {};
    // 时间
    const time = { count: 0 };
    // 初始化节点字典
    for (let i = 0; i < vertives.length; i++) {
      d[vertives[i]] = 0;
      f[vertives[i]] = 0;
      p[vertives[i]] = null;
    }
    for (let i = 0; i < vertives.length; i++) {
      if (color[vertives[i]] === Colors.WHITE) {
        DFSVisit(vertives[i], color, d, f, p, time, adjList);
      }
    }
    return {
      discovery: d,
      finished: f,
      predecessors: p
    };
  };
  const DFSVisit = (u, color, d, f, p, time, adjList) => {
    color[u] = Colors.GREY;
    d[u] = ++time.count;
    const neighbors = adjList.get(u);
    for (let i = 0; i < neighbors.length; i++) {
      const w = neighbors[i];
      if (color[w] === Colors.WHITE) {
        p[w] = u;
        DFSVisit(w, color, d, f, p, time, adjList);
      }
    }
    color[u] = Colors.BLACK;
    f[u] = ++time.count;
  };

  // const graph = new Graph();
  // const myVertives = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
  // for (let i = 0; i < myVertives.length; i++) {
  //   graph.addVertex(myVertives[i]);
  // }
  // graph.addEdge("A", "B");
  // graph.addEdge("A", "C");
  // graph.addEdge("A", "D");
  // graph.addEdge("C", "D");
  // graph.addEdge("C", "G");
  // graph.addEdge("D", "G");
  // graph.addEdge("D", "H");
  // graph.addEdge("B", "E");
  // graph.addEdge("B", "F");
  // graph.addEdge("E", "I");
  // console.log(graph.toString());
  // breadthFirstSearch(graph, "A", (v) => {
  //   console.log("v", v);
  // });
  // console.log("BFS()", BFS(graph, "A"));
  graph = new Graph(true); // 有向图
  myVertices = ["A", "B", "C", "D", "E", "F"];
  for (i = 0; i < myVertices.length; i++) {
    graph.addVertex(myVertices[i]);
  }
  graph.addEdge("A", "C");
  graph.addEdge("A", "D");
  graph.addEdge("B", "D");
  graph.addEdge("B", "E");
  graph.addEdge("C", "F");
  graph.addEdge("F", "E");
  const result = DFS(graph);
  console.log("result", result);
  const fTimes = result.finished;
  s = "";
  for (let count = 0; count < myVertices.length; count++) {
    let max = 0;
    let maxName = null;
    for (i = 0; i < myVertices.length; i++) {
      if (fTimes[myVertices[i]] > max) {
        max = fTimes[myVertices[i]];
        maxName = myVertices[i];
      }
    }
    s += " - " + maxName;
    delete fTimes[maxName];
  }
  console.log(s);
}

/**
 * Node 深度/广度遍历
 */
// node tree
const nodes = [
  {
    name: "A",
    children: [
      { name: "B", children: [{ name: "C", children: [] }] },
      { name: "D", children: [] }
    ]
  },
  {
    name: "E",
    children: []
  }
];
// 深度
function deep(nodes = [], ret = []) {
  nodes.forEach((node) => {
    ret.push(node.name);
    node.children && deep(node.children, ret);
  });
  return ret;
}
// 广度
function span(nodes = []) {
  const queue = nodes;
  const ret = [];
  while (queue.length) {
    [...queue].forEach((node) => {
      queue.shift();
      ret.push(node.name);
      node.children && queue.push(...node.children);
    });
  }
  return ret;
}

目录
相关文章
|
2月前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
61 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
2月前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
55 0
数据结构与算法学习十五:哈希表
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】