JS数据结构与算法

数据结构

栈

class Stack {
  items = [];
  pop() {
    return this.items.pop();
  }
  push(data) {
    this.items.push(data);
  }
  peek() {
    return this.items.at(-1);
  }
  isEmpty() {
    return this.items.length == 0;
  }
  clear() {
    this.items = [];
  }
  size() {
    return this.items.length;
  }
  toString() {
    return this.items.join(",");
  }
}

队列

class Queue {
  items = [];
  lowCount = 0;
  count = 0;
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    let value = this.items[this.lowCount];
    delete this.items[this.lowCount];
    this.lowCount++;
    return value;
  }
  enqueue(data) {
    this.items[this.count] = data;
    this.count++;
  }
  front() {
    return this.items[this.lowCount];
  }
  isEmpty() {
    return this.size() === 0;
  }
  clear() {
    this.items = {};
    this.lowCount = 0;
    this.count = 0;
  }
  size() {
    return this.count - this.lowCount;
  }
  toString() {
    let str = "";
    for (let i = this.lowCount; i < this.count; i++) {
      str += `${this.items[i]},`;
    }
    return str.substr(0, str.length - 1);
  }
}

双端队列

class DeQueue {
  items = [];
  lowCount = 0;
  count = 0;
  addFront(data) {
    if (this.isEmpty()) {
      return this.addBack(data);
    } else if (this.lowCount > 0) {
      this.lowCount--;
      this.items[this.lowCount] = data;
    } else if (this.lowCount === 0) {
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1];
      }
      this.items[0] = data;
      this.count++;
    }
  }
  addBack(data) {
    this.items[this.count] = data;
    this.count++;
  }
  removeFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    let value = this.items[this.lowCount];
    delete this.items[this.lowCount];
    this.lowCount++;
    return value;
  }
  removeBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    let value = this.items[this.count];
    delete this.items[this.count];
    this.count--;
    return value;
  }
  peekFront() {
    return this.items[this.lowCount];
  }
  peekBack() {
    return this.items[this.count - 1];
  }
  isEmpty() {
    return this.size() === 0;
  }
  clear() {
    this.items = {};
    this.lowCount = 0;
    this.count = 0;
  }
  size() {
    return this.count - this.lowCount;
  }
  toString() {
    let str = "";
    for (let i = this.lowCount; i < this.count; i++) {
      console.log(i);
      str += `${this.items[i]},`;
    }
    return str.substr(0, str.length - 1);
  }
}

单向链表

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}
class LinkedList {
  constructor() {
    this.count = 0;
    this.head = null;
  }
  push(element) {
    const node = new Node(element);
    if (this.head === null) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = node;
    }
    this.count++;
    return true;
  }
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      let current = this.head;
      if (index === 0) {
        node.next = current;
        this.head = node;
      } else {
        let previous = this.getNodeAt(index - 1);
        current = previous.next;
        previous.next = node;
        node.next = current;
      }
      this.count++;
      return true;
    }
  }
  getNodeAt(index) {
    if (index >= 0 && index < this.count) {
      let node = this.head;
      for (let i = 0; i < index; i++) {
        node = node.next;
      }
      return node;
    }
  }
  indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.count; i++) {
      if (element.next === current.element) {
        return i;
      }
      current = current.next;
    }
    return -1;
  }
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = this.head.next;
        return current.element;
      } else {
        let previous = this.getNodeAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
  }
  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }
  isEmpty() {
    return this.size() === 0;
  }
  size() {
    return this.count;
  }
  getHead() {
    return this.head;
  }
}

双向链表

class DoublyNode {
  constructor(element) {
    this.element = element;
    this.prev = null;
    this.next = null;
  }
}
class DoublyLinkedList {
  constructor() {
    this.count = 0;
    this.head = null;
    this.tail = null;
  }
  push(element) {
    const node = new DoublyNode(element);
    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this.count++;
    return true;
  }
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      let current = this.head;
      if (index === 0) {
        current.prev = node;
        node.next = current;
        this.head = node;
      } else {
        let previous = this.getNodeAt(index - 1);
        current = previous.next;
        node.prev = previous;
        node.next = current;
        previous.next = node;
      }
      this.count++;
      return true;
    }
  }
  getNodeAt(index) {
    if (index >= 0 && index < this.count) {
      let node = this.head;
      for (let i = 0; i < index; i++) {
        node = node.next;
      }
      return node;
    }
  }
  indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.count; i++) {
      if (element.next === current.element) {
        return i;
      }
      current = current.next;
    }
    return -1;
  }
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = this.head.next;
        this.head.prev = null;
        return current.element;
      } else {
        let previous = this.getNodeAt(index - 1);
        current = previous.next;
        current.next.prev = previous;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
  }
  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }
  isEmpty() {
    return this.size() === 0;
  }
  size() {
    return this.count;
  }
  getHead() {
    return this.head;
  }
  getTail() {
    return this.tail;
  }
}

循环链表

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}
class CirularLinkedList {
  constructor() {
    this.count = 0;
    this.head = null;
  }
  push(element) {
    const node = new Node(element);
    if (this.head === null) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next !== this.head) {
        current = current.next;
      }
      current.next = node;
    }
    node.next = this.head;
    this.count++;
    return true;
  }
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      let current = this.head;
      if (index === 0) {
        if (this.head === null) {
          this.head = node;
          node.next = this.head;
        } else {
          node.next = this.head;
          current = this.getNodeAt(this.size() - 1);
          current.next = node;
          this.head = node;
        }
      } else {
        let previous = this.getNodeAt(index - 1);
        current = previous.next;
        previous.next = node;
        node.next = current;
      }
      this.count++;
      return true;
    }
  }
  getNodeAt(index) {
    if (index >= 0 && index < this.count) {
      let node = this.head;
      for (let i = 0; i < index; i++) {
        node = node.next;
      }
      return node;
    }
  }
  indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.count; i++) {
      if (element.next === current.element) {
        return i;
      }
      current = current.next;
    }
    return -1;
  }
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        if (this.size() === 1) {
          this.head = null;
        } else {
          const last = this.getNodeAt(this.size() - 1);
          this.head = this.head.next;
          last.next = this.head;
          return current.element;
        }
      } else {
        let previous = this.getNodeAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
  }
  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }
  isEmpty() {
    return this.size() === 0;
  }
  size() {
    return this.count;
  }
  getHead() {
    return this.head;
  }
}

集合

new Set();

字典

new Mep();

哈希表

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
}
class HashTable {
  table = {};
  toStrFn(item) {
    if (item === null) {
      return "NULL";
    } else if (item === undefined) {
      return "UNDEFINED";
    } else if (typeof item === "string" || item instanceof String) {
      return item;
    } else {
      return JSON.stringify(item);
    }
  }
  hashCode(key) {
    if (typeof key === "number") {
      return key;
    } else {
      const tableKey = this.toStrFn(key);
      let hash = 5381;
      for (let i = 0; i < tableKey.length; i++) {
        hash = hash * 33 + tableKey.charCodeAt(i);
      }
      return hash % 1013;
    }
  }
  set(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key);
      this.table[position] = new ValuePair(key, value);
      return true;
    }
    return false;
  }
  get(key) {
    const valuepair = this.table[this.hashCode(key)];
    return valuepair === null ? undefined : valuepair.value;
  }
  remove(key) {
    const hash = this.hashCode(key);
    const valuepair = this.table[hash];
    if (valuepair != null) {
      delete this.table[hash];
      return true;
    }
    return false;
  }
}

二叉搜索树

左子节点的值小于父节点，右子节点的值大于父节点

const Compare = {
  less: -1,
  bigger: 1,
  equ: 0,
};
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  compareFn(a, b) {
    if (a === b) {
      return Compare.equ;
    }
    return a < b ? Compare.less : Compare.bigger;
  }
  insert(key) {
    if (this.root == null) {
      this.root = new Node(key);
    } else {
      this.insertNode(this.root, key);
    }
  }
  insertNode(node, key) {
    if (this.compareFn(key, node.key) === Compare.less) {
      if (node.left == null) {
        node.left = new Node(key);
      } else {
        this.insertNode(node.left, key);
      }
    } else if (this.compareFn(key, node.key) === Compare.bigger) {
      if (node.right == null) {
        node.right = new Node(key);
      } else {
        this.insertNode(node.right, key);
      }
    }
  }
  inOrderMap(callback) {
    this.inOrderMapNode(this.root, callback);
  }
  inOrderMapNode(node, callback) {
    if (node != null) {
      this.inOrderMapNode(node.left, callback);
      callback(node.key);
      this.inOrderMapNode(node.right, callback);
    }
  }
  preOrderMap(callback) {
    this.preOrderMapNode(this.root, callback);
  }
  preOrderMapNode(node, callback) {
    if (node != null) {
      callback(node.key);
      this.preOrderMapNode(node.left, callback);
      this.preOrderMapNode(node.right, callback);
    }
  }
  postOrderMap(callback) {
    this.postOrderMapNode(this.root, callback);
  }
  postOrderMapNode(node, callback) {
    if (node != null) {
      this.postOrderMapNode(node.left, callback);
      this.postOrderMapNode(node.right, callback);
      callback(node.key);
    }
  }
  min() {
    return this.minNode(this.root);
  }
  minNode(node) {
    let current = node;
    while (current != null && current.left != null) {
      current = current.left;
    }
    return current;
  }
  max() {
    return this.maxNode(this.root);
  }
  maxNode(node) {
    let current = node;
    while (current != null && current.right != null) {
      current = current.right;
    }
    return current;
  }
  search(key) {
    return this.searchNode(this.root, key);
  }
  searchNode(node, key) {
    if (node == null) {
      return false;
    } else if (this.compareFn(key, node.key) === Compare.less) {
      return this.searchNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.bigger) {
      return this.searchNode(node.right, key);
    } else if (this.compareFn(key, node.key) === Compare.equ) {
      return true;
    }
  }
  remove(key) {
    this.root = this.removeNode(this.root, key);
  }
  removeNode(node, key) {
    if (node == null) {
      return null;
    } else if (this.compareFn(key, node.key) === Compare.less) {
      node.left = this.removeNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.bigger) {
      node.right = this.removeNode(node.right, key);
    } else if (this.compareFn(key, node.key) === Compare.equ) {
      if (node.left == null && node.right == null) {
        node = null;
      } else if (node.left == null) {
        node = node.right;
      } else if (node.right == null) {
        node = node.left;
      } else {
        const target = this.minNode(node.right);
        node.key = target.key;
        node.right = this.removeNode(node.right, target.key);
      }
    }
    return node;
  }
}

二叉堆

const Compare = {
  less: -1,
  bigger: 1,
  equ: 0,
};

// 最小堆
class MinHeap {
  heap = [];
  getLeftIndex(index) {
    return 2 * index + 1;
  }
  getRightIndex(index) {
    return 2 * index + 2;
  }
  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }
  compareFn(a, b) {
    if (a === b) {
      return Compare.equ;
    }
    return a < b ? Compare.less : Compare.bigger;
  }
  swap(arr, a, b) {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }
  insert(value) {
    if (value != null) {
      this.heap.push(value);
      this.shiftUp(this.heap.length - 1);
      return true;
    }
    return false;
  }
  shiftUp(index) {
    let parent = this.getParentIndex(index);
    while (
      index > 0 &&
      this.compareFn(this.heap[parent], this.heap[index]) === Compare.bigger
    ) {
      this.swap(this.heap, parent, index);
      index = parent;
      parent = this.getParentIndex(index);
    }
  }
  shiftDown(index) {
    let current = index;
    let left = this.getLeftIndex(index);
    let right = this.getRightIndex(index);
    let size = this.size();
    if (
      left < size &&
      this.compareFn(this.heap[current], this.heap[left]) === Compare.bigger
    ) {
      current = left;
    }
    if (
      right < size &&
      this.compareFn(this.heap[current], this.heap[right]) === Compare.bigger
    ) {
      current = right;
    }
    if (index !== current) {
      this.swap(this.heap, index, current);
      this.shiftDown(current);
    }
  }
  size() {
    return this.heap.length;
  }
  isEmpty() {
    return this.size() == 0;
  }
  findTarget() {
    return this.heap[0];
  }
  extract() {
    if (this.isEmpty()) {
      return;
    }
    if (this.size() == 1) {
      return this.heap.shift();
    }
    const removed = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
    return removed;
  }
}

// 最大堆
class MaxHeap extends MinHeap {
  constructor() {
    super();
  }
  compareFn(a, b) {
    if (a === b) {
      return Compare.equ;
    }
    return a > b ? Compare.less : Compare.bigger;
  }
}

---

常用算法

引用站外地址

visualgo

数据结构和算法动态可视化

冒泡排序

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

选择排序

function selectionSort(arr) {
  const length = arr.length;
  let indexMin;
  for (let i = 0; i < length - 1; i++) {
    indexMin = i;
    for (let j = i; j < length; j++) {
      if (arr[j] < arr[indexMin]) {
        indexMin = j;
      }
    }
    if (i !== indexMin) {
      swap(arr, i, indexMin);
    }
  }
}

插入排序

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

归并排序

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  let i = 0,
    j = 0;
  const result = [];
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  return result.concat(left.slice(i), right.slice(j));
}

快速排序

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivot = arr.pop();
  const left = [];
  const right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

计数排序

function countingSort(arr) {
  const len = arr.length;
  if (len <= 1) {
    return arr;
  }
  let max = arr[0];
  for (let i = 1; i < len; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  const countArr = new Array(max + 1).fill(0);
  for (let i = 0; i < len; i++) {
    countArr[arr[i]]++;
  }
  for (let i = 1; i <= max; i++) {
    countArr[i] += countArr[i - 1];
  }
  const result = new Array(len);
  for (let i = len - 1; i >= 0; i--) {
    result[countArr[arr[i]] - 1] = arr[i];
    countArr[arr[i]]--;
  }
  return result;
}

桶排序

function bucketSort(arr, bucketSize = 5) {
  if (arr.length === 0) {
    return arr;
  }
  let min = arr[0];
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) {
      min = arr[i];
    } else if (arr[i] > max) {
      max = arr[i];
    }
  }
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = [];
  }
  for (let i = 0; i < arr.length; i++) {
    const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
    buckets[bucketIndex].push(arr[i]);
  }
  const sortedArray = [];
  for (let i = 0; i < bucketCount; i++) {
    const bucket = buckets[i];
    if (bucket) {
      const sortedBucket = bucketSort(bucket, bucketSize);
      sortedArray.push(...sortedBucket);
    }
  }

  return sortedArray;
}

基数排序

function radixSort(arr) {
  if (arr.length === 0) {
    return arr;
  }
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  const maxLength = max.toString().length;
  for (let i = 0; i < maxLength; i++) {
    const buckets = new Array(10).fill().map(() => []);
    for (let j = 0; j < arr.length; j++) {
      const digit = getDigit(arr[j], i);
      buckets[digit].push(arr[j]);
    }
    arr = [].concat(...buckets);
  }

  return arr;
}
function getDigit(num, place) {
  return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

搜索算法

随机算法

动态规划

贪心算法

回溯算法

算法复杂度