Javascript 数据结构与算法

2021年04月02日

算法

栈

一个后进先出的数据结构
javascript 中没有栈可以用 Array 实践栈的所有功能

const stack = [];
stack.push(1);
stack.push(2);
const item1 = stack.pop();
const item2 = stack.pop();

使用场景：所有后进先出的场景函数调用堆栈
leetcode 练习题：20

队列

一个先进先出的数据结构
javascript 中没有队列可以用 Array 实践队列的所有功能

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

使用场景：需要先进先出的场景 js 中异步任务队列
leetcode 练习题：933

链表

对个元素组成的列表
元素存储不连续用 next 指针连在一起

数组：增删非首尾元素时需要移动元素
链表：增删非首尾元素不需要移动元素只需要改 next 指向即可

链表常用操作：修改 next 遍历链表

js 中无链表结构可用 Object 模拟链表

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;
}
// 插入
const e = { val: "e" };
c.next = e;
e.next = d;
// 删除
c.next = d;

leetcode 练习题：237 206 2 83 141
141 环形链表的判断用一快一慢两个指针遍历链表如果指针能够相逢那么链表就有圈

集合

一种无序且唯一的数据结构
ES6 中有集合 Set
集合常用操作去重求交集判断元素是否在集合中

// 去重
const arr = [1, 1, 2, 2];
const arr2 = [...new Set(arr)];
// 判断元素是否在集合中
const set = new Set(arr);
const has = set.has(3);
// 求交集
const set2 = new Set([2, 3]);
const set3 = new Set([...set].filter((item) => set2.has(item)));
// 求差集
const difference = new Set([...set].filter((x) => !set2.has(x)));

leetcode 练习题：349

字典

一种存储唯一值的数据结构但它是以键值对的形式来存储
ES6 中有字典 Map
常用操作键值对的增删改查

const m = new Map();
// 增
m.set("a", "aa");
m.set("b", "bb");
// 删
m.delete("b");
// m.clear();
// 改
m.set("a", "aaa");

leetcode 练习题： 1 3 76

树

一种分层数据的抽象模型
DOM 树级联选择树形控件
js 中没有树但可以用 Object 和 Array 构建树

树的常用操作：深度/广度优先遍历先中后序遍历

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); //root.children.forEach(dfs);
  // if (root.left) dfs(root.left);
  // if (root.right) dfs(root.right);
  const q = [root];
  while (q.length > 0) {
    const n = q.pop();
    console.log(n.val);
    n.children.forEach((child) => {
      q.push(child);
    });
  }
};
dfs(tree);

广度优先遍历

const bfs = (root) => {
  const q = [root];
  while (q.length > 0) {
    const n = q.shift();
    console.log(n.val);
    n.children.forEach((child) => {
      q.push(child);
    });
  }
};
bfs(tree);

二叉树

树中每个节点最多只能有两个子节点
js 中通常用 object 模拟二叉树

const binaryTree = {
  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,
    },
  },
};

先序遍历

访问顺序：根左右

const preorder = (root) => {
  if (!root) {
    return;
  }
  console.log(root.val);
  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 inorder = (root) => {
  if (!root) {
    return;
  }
  inorder(root.left);
  console.log(root.val);
  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);

后序遍历

访问顺序：左右根

const postorder = (root) => {
  if (!root) {
    return;
  }
  postorder(root.left);
  postorder(root.right);
  console.log(root.val);
};
// 非递归写法
// const postorder = (root) => {
//     if (!root) { return; }
//     const outputStack = [];
//     const stack = [root];
//     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);

leetcode 练习题：104 111 102 94 112

堆

是一种特殊的完全二叉树
所有的节点都大于等于(最大堆)或小于等于(小于等于)它的子节点

js 中通常用数组表示堆
左侧子节点的位置是2* index+1
右侧子节点的位置是2*index+2
父节点位置是(index-1)/2

堆能高效快速的找出最大值最小值时间复杂度 O(1)
找出第 K 个最大(小)元素

class MinHeap {
  constructor() {
    this.heap = [];
  }
  getParentIndex(i) {
    // return Math.floor((i-1)/2);
    return (i - 1) >> 1; // 右移一位 即除二取商操作
  }
  getLeftIndex(i) {
    return i * 2 + 1;
  }
  getRightIndex(i) {
    return i * 2 + 2;
  }
  swap(i1, i2) {
    const temp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
  }
  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() {
    if (this.size() === 1) return this.heap.shift();
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
  }
  peek() {
    return this.heap[0];
  }
  size() {
    return this.heap.length;
  }
}

leetcode 练习题：215 347 23

图

是网络结构的抽象模型是一组由边连接的节点可表示任何二元关系
js 中没有图但可以用 object 和 array 构建图邻接矩阵领接表

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

常用操作深度优先遍历广度优先遍历

深度优先遍历

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

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

广度优先遍历

新建一个队列根节点入队
对头出队并访问
把队头的没有访问过的相邻节点入队

const visited = new Set();
const q = [2];
while (q.length) {
  const n = q.shift();
  console.log(n);
  visited.add(n);
  graph[n].forEach((c) => {
    if (!visited.has(c)) {
      q.push(c);
    }
  });
}

leetcode 练习题： 417 133

排序和搜索算法

冒泡排序

比较所有相邻元素如果第一个比第二个大则交换位置一轮下来可以保证最后一个数是最大的
时间复杂度 O(n^2)

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 相邻元素两两对比
        const temp = arr[j + 1]; // 元素交换
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
时间复杂度 O(n^2)

function selectionSort(arr) {
  var len = arr.length;
  var minIndex, temp;
  for (var i = 0; i < len - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        // 寻找最小的数
        minIndex = j; // 将最小数的索引保存
      }
    }
    if (minIndex !== i) {
      temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}

插入排序

时间复杂度 O(n^2)
原理：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤 2~5。

function insertionSort(arr) {
  var len = arr.length;
  var preIndex, current;
  for (let i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
  }
  return arr;
}

归并排序

时间复杂度 O(nlogn)
算法描述：
把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

function mergeSort(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 = mergeSort(left);
  const orderRight = mergeSort(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;
}

快速排序

算法描述：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

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

二分搜索

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

时间复杂度 O(logN)

function binarySearch(arr, item) {
  const orderArr = arr.sort();
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = (low + high) >> 1;
    const element = arr[mid];
    if (element < item) {
      low = mid + 1;
    } else if (element > item) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

分而治之

是一种算法思想
将一个问题分成多个和原问题相似的小问题递归解决小问题再将结果合并以解决原来的问题

归并排序快速排序
leetcode 练习题：374 226 10 101

寻找最长递增序列

leetcode 练习题：300
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

原文链接: https://jesse121.github.io/blog/articles/2021/04/02.html

版权声明: 转载请注明出处.

前端之路

路漫漫其修远兮，吾将上下而求索

Javascript 数据结构与算法

栈

队列

链表

集合

字典

树

深度优先遍历

广度优先遍历

二叉树

先序遍历

中序遍历

后序遍历

堆

图

深度优先遍历

广度优先遍历

排序和搜索算法

冒泡排序

选择排序

插入排序

归并排序

快速排序

二分搜索

分而治之

寻找最长递增序列

文章目录