前端算法与数据结构之图、堆、搜索排序(三)

前端算法与数据结构之栈、队列、链表(一)

前端算法与数据结构之集合、字典、树(二)

11、图

11-1图是什么?
  • 图是网络结构的抽象模型,是一-组由边连接的节点。

  • 图可以表示任何二元关系,比如道路、航班。

  • JS中没有图,但是可以用ObjectArray构建图。

  • 图的表示法:邻接矩阵、邻接表、关联矩….

img

如果节点A能连接到节点B,那么矩阵B对应的行或者列表示为1,否则为0

img

节点A能连接到节点B,那么A:[“B”],这个比较好理解的。

图的常用操作

  • 深度优先遍历
  • 广度优先遍历
11-2图的深度优先遍历算法口诀
  1. 访问根节点。
  2. 对根节点的没访问过的相邻节点挨个进行深度优先遍历。

img

没访问过的相邻节点:如上图所示,如果从节点2开始遍历,优先遍历节点0,节点0在返回到节点2就会造成死循环,如果加个没访问过的相邻节点判断,就会寻找下个非访问过的节点了。

代码实现

// graph.js
const graph = {
  0:[1,2],
  1:[2],
  2:[0,3],
  3:[3]
}
module.exports = graph;
// dfs.js
const graph = require('./graph');
// 声明一个集合,记录已遍历过的节点
const isVistive = new Set();
const dfs =(n) => {
  console.log(n); // 2,0,1,3
  isVistive.add(n); // 记录已遍历过的节点
  graph[n].forEach(item => {
    if(!isVistive.has(item)) {
      dfs(item)
    }
  })
}
dfs(2);
复制代码
11-3图的广度优先遍历算法口诀
  1. 新建一个队列,把根节点入队。
  2. 把队头出队并访问。
  3. 把队头的没访问过的相邻节点入队。
  4. 重复第二、三步,直到队列为空。

代码实现

const graph = require('./graph');
// 声明一个集合,记录已遍历过的节点
const isVistive = new Set();
isVistive.add(2) // 先把初始节点添加到集合
const bfs = () => {
  const q = [2];
  while (q.length) {
    const n = q.shift();
    console.log(n);// 2,0,3,1
    graph[n].forEach(item => {
      if (!isVistive.has(item)) {
        q.push(item)
        isVistive.add(item);
      }
    })
  }
}
bfs();
复制代码
11-4 算法题
65. 有效数字

img

图片描述: 编号1,开始走节点6的位置,最终停留在节点6,所以0是有效数字。编号3,a开头无路可走,所以编号3是无效数字。只有遍历到节点3、5、6的时候,数字才是有效数字。

解题步骤

  1. 构建一个表示状态的图。
  2. 遍历字符串,并沿着图走,如果到了某个节点无路可走就返false
  3. 遍历结束,如走到3/5/6,就返回true,否则返回false。
/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {
    const graph = {
        0:{'blank':0,'digit':6,'sign':1,'.':2},
        1:{'digit':6, '.':2},
        2:{'digit':3},
        3:{'digit':3, 'e':4},
        4:{'digit':5,'sign':7},
        5:{'digit':5},
        6:{'digit':6, '.':3, 'e':4},
        7:{'digit':5}
    }
    let state = 0; // 初始状态值为0;
    for(item of s.trim()) {
        if(item >= '0' && item <= '9') {
            item = 'digit'
        }else if(item === '') {
            item = 'blank'
        }else if(item === '+' || item === '-') {
            item = 'sign'
        }else if(item === 'e' || item === 'E') {
            item = 'e'
        }
        state = graph[state][item]
        if(state == undefined) {
            return false;
        }
    }
    if(state == 3 || state == 6 || state == 5) {
        return true;
    }
    return false;
};
复制代码
417. 太平洋大西洋水流问题
给定下面的 5x5 矩阵:
  太平洋 ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * 大西洋
复制代码

解题步骤

  1. 新建两个矩阵,分别记录能流到两个大洋的坐标。
  2. 从海岸线,多管齐下,同时深度优先遍历图,过程中填充上述矩阵。
  3. 遍历两个矩阵,找出能流到两个大洋的坐标。
/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function (heights) {
    if (!heights || !heights[0] || !heights[0].length) return []
    const m = heights.length
    const n = heights[0].length
    // 逆流而上,走出一条通道
    // 存放太平洋->大西洋的路径
    const flow1 = Array.from({ length: m }, () => {
        return Array.from({ length: n }, () => false)
    })
    // 存放大西洋->太平洋的路径
    const flow2 = Array.from({ length: m }, () => {
        return Array.from({ length: n }, () => false)
    })
    const dfs = (r, c, flow) => {
        flow[r][c] = true;
        [[r - 1, c], [r, c + 1], [r + 1, c], [r, c - 1]].forEach(([nr, nc]) => {
            if (nr >= 0 && nr < m &&
                nc >= 0 && nc < n &&
                !flow[nr][nc] &&
                heights[nr][nc] >= heights[r][c]
            ) {
                dfs(nr, nc, flow)
            }
        })
    }
    //多管齐下, 第一行遍历到最后行,第一列遍历到最后列
    for (let i = 0; i < m; i++) {
        dfs(i, 0, flow1)
        dfs(i, n - 1, flow2)
    }
    for (let i = 0; i < n; i++) {
        dfs(0, i, flow1)
        dfs(m - 1, i, flow2)
    }
    // 找出两条路都能走通的节点
    const res = []
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (flow1[i][j] && flow2[i][j]) {
                res.push([i, j])
            }
        }
    }
    return res
};
复制代码
133. 克隆图

12、堆

12-1堆是什么?

img

img

上图解释:index指的是数组的下标索引。

12-2堆的应用
  • 堆能高效、快速地找出最大值和最小值,时间复杂度: 0(1)。
  • 找出第K个最大(小)元素。

找出第K个最大元素

img

  1. 构建一个最小堆,并将元素依次插入堆中。
  2. 当堆的容量超过K,就删除堆顶。
  3. 插入结束后,堆顶就是第K个最大元素。

实现最小堆类

实现步骤:

  1. 在类里,声明-一个数组,用来装元素。
  2. 主要方法:插入、删除堆顶、获取堆顶、获取堆大小。
插入方法
  1. 将值插入堆的底部,即数组的尾部。
  2. 然后上移:将这个值和它的父节点进行交换,直到父节点小于等于这个插入的值。
  3. 大小为k的堆中插入元素的时间复杂度为O(logk)。

代码实现

// 插入方法,获取第K个最小元素
class MinHeap {
  constructor() {
    this.heap = [];
  }
  // 交换函数
  swap(i1,i2){
    let temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp;
  }
  // 获取父节点的位置  (index -1 ) / 2 的余数
  getParentIndex(i) {
    return (i - 1) >> 1
  }
  // 上移操作:将这个值和它的父节点进行交换,直到父节点小于等于这个插入的值。
  shiftUp(index){
    // index == 0 到栈顶了, 就返回
    if(index == 0) {return;}
    const parentIndex = this.getParentIndex(index);
    // 和父节点交换
    if(this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex,index)
      this.shiftUp(parentIndex)
    }
  }
  // 将值插入堆的底部
  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }
}
const h = new MinHeap();

h.insert(3)
h.insert(2)
h.insert(1)
复制代码
删除堆顶
  1. 用数组尾部元素替换堆顶(直接删除堆顶会破坏堆结构)。
  2. 然后下移:将新堆顶和它的子节点进行交换,直到子节点大于等于这个新堆顶。
  3. 大小为k的堆中删除堆顶的时间复杂度为O(logk)。

代码实现

// 插入方法,获取第K个最小元素
class MinHeap {
  constructor() {
    this.heap = [];
  }
  // 交换函数
  swap(i1,i2){
    let temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp;
  }
  // 获取父节点的位置  (index -1 ) / 2 的余数
  getParentIndex(i) {
    return (i - 1) >> 1
  }
  // 获取左节点的位置 index * 2 + 1
  getLeftIndex(i) {
    return i * 2 + 1;
  }
  // 获取右节点的位置 index * 2 + 2
  getRightIndex(i) {
    return i * 2 + 2;
  }
  // 上移操作:将这个值和它的父节点进行交换,直到父节点小于等于这个插入的值。
  shiftUp(index){
    // index == 0 到栈顶了, 就返回
    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() {
    this.heap[0] = this.heap.pop(); // 用数组尾部元素替换堆顶
    this.shiftDown(0)
  }
}
const h = new MinHeap();

h.insert(3)
h.insert(2)
h.insert(1)
h.pop();
复制代码
获取堆顶和堆的大小
  1. 获取堆顶,返回数组的头部
  2. 获取堆得大小:返回数组的长度
// 获取堆顶,返回数组的头部
  peek() {
    return this.heap[0]
  }
  // 获取堆得大小:返回数组的长度
  size() {
    return this.heap.length
  }
复制代码

img

12-3算法题解
215. 数组中的第K个最大元素

解题思路

  1. 构建一个最小堆,一次把元素插入堆中
  2. 如果堆得大小超过 k ,就删除堆顶
  3. 元素插入结束后,返回堆顶,即最大的第k个元素
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 获取最小堆类,前面已经写过了,直接拿来用即可
var findKthLargest = function(nums, k) {
    const h = new MinHeap();
    nums.forEach(item => {
        h.insert(item);
        if(h.size() > k) {
            h.pop();
        }
    })
    return h.peek();
};
复制代码
347. 前 K 个高频元素
// 插入方法,获取第K个最小元素
class MinHeap {
  constructor() {
    this.heap = [];
  }
  // 交换函数
  swap(i1, i2) {
    let temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp;
  }
  // 获取父节点的位置  (index -1 ) / 2 的余数
  getParentIndex(i) {
    return (i - 1) >> 1
  }
  // 获取左节点的位置 index * 2 + 1
  getLeftIndex(i) {
    return i * 2 + 1;
  }
  // 获取右节点的位置 index * 2 + 2
  getRightIndex(i) {
    return i * 2 + 2;
  }
  // 上移操作:将这个值和它的父节点进行交换,直到父节点小于等于这个插入的值。
  shiftUp(index) {
    // index == 0 到栈顶了, 就返回
    if (index == 0) {
      return;
    }
    const parentIndex = this.getParentIndex(index);
    // 和父节点交换
    if (this.heap[parentIndex]&&this.heap[parentIndex].value > this.heap[index].value) {
      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[leftIndex].value < this.heap[index].value) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex);
    }
    if (this.heap[rightIndex]&&this.heap[rightIndex].value < this.heap[index].value) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex);
    }
  }
  // 将值插入堆的底部
  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }
  pop() {
    this.heap[0] = this.heap.pop(); // 用数组尾部元素替换堆顶
    this.shiftDown(0)
  }
  // 获取堆顶,返回数组的头部
  peek() {
    return this.heap[0]
  }
  // 获取堆得大小:返回数组的长度
  size() {
    return this.heap.length
  }
}
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const map = new Map();
    nums.forEach(n => {
        map.set(n, map.has(n) ? map.get(n) + 1: 1)
    })
    const h = new MinHeap();
    map.forEach((value,key) => {
        h.insert({value, key})
        if(h.size() > k) {
            h.pop();
        }
    })
    return h.heap.map( n => n.key)
};
复制代码

13、进阶算法-搜索排序

JS中的排序:数组的sort方法。

JS中的搜索:数组的indexOf方法。

  • 十大经典算法排序总结对比

img

名词解释:

n: 数据规模
k:“桶”的个数
In-place: 占用常数内存,不占用额外内存
Out-place: 占用额外内存
稳定性:排序后2个相等键值的顺序和排序之前它们的顺序相同

13-1 排序算法常见类型
  1. 冒泡排序
  2. 选择排序
  3. 插入排序
  4. 归并排序
  5. 快速排序 等等
13-2搜索算法常见类型
  1. 顺序搜索
  2. 二分搜索
13-3冒泡排序

冒泡排序的思路

算法动画网址

  1. 比较所有相邻元素,如果第一个比第二个大,则交换它们。
  2. 一轮下来,可以保证最后一个数是最大的。
  3. 执行n-1轮,就可以完成排序。
  • 冒泡排序动图演示

img

代码实现

Array.prototype.bubbleSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    for (let j = 0; j < this.length - 1 - i; j++) {
      if (this[j] > this[j + 1]) {
        const temp = this[j]
        this[j] = this[j + 1];
        this[j + 1] = temp;
      }
    }
  }
}
const arr = [5, 4, 3, 2, 1]
arr.bubbleSort();
复制代码
13-4选择排序

选择排序思路

  1. 找到数组中的最小值,选中它并将其放置在第一位。
  2. 接着找到第二小的值,选中它并将其放置在第二位。
  3. 以此类推,执行n- 1轮。

选择排序须知:

在时间复杂度上表现最稳定的排序算法之一,因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

选择排序动图演示:

img

代码实现

Array.prototype.selectionSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    let indexMin = i;
    for (let j = i; j < this.length; j++) {
      if (this[j] < this[indexMin]) {
        indexMin = j;
      }
    }
    if (indexMin !== i) { // 当前索引的值不需要和自己比
      const temp = this[i];
      this[i] = this[indexMin]
      this[indexMin] = temp;
    }
  }
}
const arr = [5, 4, 3, 2, 1]
arr.selectionSort();
复制代码
13-5插入排序

插入排序思路

  1. 从第二个数开始往前比。
  2. 比它大就往后排。
  3. 以此类推进行到最后一个数。

插入排序动图演示:

img

代码实现

Array.prototype.insertionSort = function () {
  for (let i = 1; i < this.length; i++) {
    const temp = this[i];
    let j = i;
    while (j > 0) {
      if (this[j - i] > temp) {
        this[j] = this[j - i];
      } else {
        break;
      }
      j--;
    }
    this[j] = temp;
  }
}
const arr = [5, 4, 3, 2, 1]
arr.insertionSort();
复制代码
13-6归并排序
  1. 分:把数组劈成两半,再递归地对子数组进行,“分”操作,直到分成一个个单独的数。
  2. 合:把两个数合并为有序数组,再对有序数组进行合并,直到全部子数组合并为一个完整数组。

合并两个有序数组

  1. 新建一个空数组res,用于存放最终排序后的数组。
  2. 比较两个有序数组的头部,较小者出队并推入res中。
  3. 如果两个数组还有值,就重复第二步。

归并排序动画:

img

代码实现

Array.prototype.mergeSort = function () {
  // 把数组劈成两半,再递归地对子数组进行分,直到把数组分成一个个元素
  const rec = (arr) => {
    if (arr.length == 1) {
      return arr;
    }
    const mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid)
    let right = arr.slice(mid, arr.length)
    const orderLeft = rec(left) // 有序左数组
    const orderRight = rec(right) // 有序右数组
    const res = []; // 新建一个空数组res,用于存放最终排序后的数组。
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        // 比较两个有序数组的头部,较小者出队并推入res中。
        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;
  }
  // 挂到原始数组里去
  const res = rec(this)
  res.forEach((n, i) => {
    this[i] = n;
  })
}
const arr = [5, 4, 3, 2, 1]
arr.mergeSort();
复制代码
13-7快速排序

快速排序思路

  1. 分区:从数组中任意选择一个“基准”,所有比基准小的元素放在基准前面,比基准大的元素放在基准的后面。
  2. 递归:递归地对基准前后的子数组进行分区。

快速排序动画:

img

代码实现

Array.prototype.quickSort = function () {
  const rec = (arr) => {
    if (arr.length === 1) {
      return arr;
    }
    const left = []; // 存放基准前面的元素
    const right = []; // 存放基准前面的元素
    const base = arr[0]; // 基准,这里选择第一个元素
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] < base) {
        left.push(arr[i])
      } else {
        right.push(arr[i])
      }
    }
    return [...rec(left), base, ...rec(right)]
  }
  // 挂到原始数组里去
  const res = rec(this)
  res.forEach((n, i) => {
    this[i] = n;
  })
}
const arr = [2, 4, 5, 3, 1]
arr.quickSort();
复制代码
13-8顺序搜索

顺序搜索思路

  1. 遍历数组
  2. 找到跟目标值相等的元素,就返回它的下标。
  3. 遍历结束后,如果没有搜索到目标值,就返回-1

代码实现

Array.prototype.sequenceSeach = function (target) {
  for (let i = 0; i < this.length; i++) {
    if (this[i] == target) {
      return i
    }
  }
  return -1;
}
const res = [1, 2, 3, 4, 5].sequenceSeach(3)
复制代码
13-9二分搜索

二分搜索思路

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

代码实现

Array.prototype.binarySearch = function (target) {
  let low = 0; // 最小索引
  let heigh = this.length - 1; // 最大索引
  while (low <= heigh) {
    const mid = Math.floor((low + heigh) / 2) // 获取中间元素下标
    const ele = this[mid] // 获取中间元素的值
    if (ele < target) {
      low = mid + 1;
    } else if (ele > target) {
      heigh = mid - 1
    } else {
      return mid; // 如果中间元素正好是目标值,则搜索结束。
    }
  }
  return -1;
}
const res = [1, 2, 3, 4, 5].binarySearch(4)
复制代码
13-10算法题
21. 合并两个有序链表

解题步骤

  1. 新建一个新链表,作为返回结果。
  2. 用指针遍历两个有序链表,并比较两个链表的当前节点较小者先接入新链表,并将指针后移一步。
  3. 链表遍历结束,返回新链表。
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    const res = new ListNode(0);
    let p = res;
    let p1 = l1;
    let p2 = l2;
    while(p1 && p2) {
        if(p1.val < p2.val) {
            p.next = p1;
            p1 = p1.next;
        }else {
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }
    if(p1) {
        p.next = p1;
    }
    if(p2) {
        p.next = p2;
    }
    return res.next;
};
复制代码
374. 猜数字大小

解题步骤

二分搜索思路

  1. 从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束。
  2. 如果目标值大于或者小于中间元素,则在大于或小于中间元素的那一半数组中搜索。
/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return 	            -1 if num is lower than the guess number
 *			             1 if num is higher than the guess number
 *                       otherwise return 0
 * var guess = function(num) {}
 */

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function(n) {
    let low = 1;
    let heigh = n;
    while(low <= heigh) {
        // 获取中间元素的值
        const mid = Math.floor((low + heigh) / 2);
        const res = guess(mid) // 来获取猜测结果,也就是中间元素
        if(res === 0) {
            return mid
        }else if(res === 1) {
            low = mid + 1;
        }else {
            heigh = mid - 1;
        }
    }
};
复制代码
© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享