前端开发是否有必要知道或者精通数据结构和算法？答案是肯定的，在实际的应用中，做前端开发并不会用到复杂的数据结构和算法，但是，想码出好代码却应该有个扎实的数据结构和算法基础，处理问题的思路也会不同，会算法的前端会想尽办法让代码得到更低的时间复杂度/空间复杂度，应对复杂的问题，会更加信手拈来。自认为自己就是个算法渣渣，遇到问题，就是嵌套几层循环，暴力输出，虽然能解决80%的问题，但是一旦真遇到棘手需求确实是寸步难行。

举个例子，

去年在接到公司的一个需求，需要针对面包屑导航来模拟一个类似浏览器前进后退的功能（当然对高手来说，应该很简单，哈哈），绞尽脑汁，写出来后，虽然最终实现了，但是bug层出不穷，改的是心力交瘁。今年在看相关算法的书时，里面一章关于介绍栈的小节，就介绍了如何用栈来实现浏览器的前进、后退功能，下面贴一下具体图示：

于是感慨算法真是个好东西，以前觉得前端不会用到那么多算法知识的，现在才知道算法的重要性，于是想在2022年花些时间把这个短板给补一下，下面是2月份学习的基础算法知识，所记下来的一些笔记（相对基础）。

单项链表与双向链表

let head = { next: '...', data: '...' };

// 链表查找
const find = (value) => {
    const p = head;
    while (p !== null && p.data !== value) {
        p.next;
    }
    return p;
}

// 链表插入
const insert = (b, x) => {
    if (x === null) {
        x.next = head;
        head = x;
    } else {
        x.next = b.next;
        b.next = x;
    }
}

// 链表删除
const remove = (b, x) => {
    if (x === null) {
        x.next = head;
        head = x;
    } else {
        b.next = b.next.next;
    }
}
复制代码

单项链表与双向链表

interface Node {
    data: number;
    prev: Node;
    next: Node;
}


let head: Node = null;


/*******给定值删除的单向链表、双向链表，时间复杂度为O(n)******/

// 单向链表
const oneWayRmove = (val: number) => {
    let q: Node = head;
    let p: Node = null; // 前驱节点

    while(q != null && q.data != val) {
        p = q;
        q = q.next;
    }

    if (q != null) {
        if (p == null) { // 尾节点
            head = q.next;
        } else {
            p.next = q.next;
        }
    }
}

// 双向链表
const twoWayRmove = (val: number) => {
    let q: Node = head;

    while(q != null && q.data != val) {
        q = q.next;
    }

    if (q != null) {
        if (q.prev == null) { // 尾节点
            head = q.next;
        } else {
            q.prev.next = q.next;
        }
    }
}

/*******给定指针的删除的单向链表->时间复杂度为O(n)、双向链表->时间复杂度O(1)******/

// 单向链表
const oneWayPointerRmove = (q: Node) => {
    if (q == null) { return; }
    if (q == head) {
        head = q.next;
    }
    let p: Node = head;
    while (p != null && p.next != q) {
        p = p.next;
    }
    if (p.next != null) {
        p.next = q.next;
    }
}

// 双向链表
const twoWayPointerRmove = (q: Node) => {
    if (q == null) return;
    if (q.prev == null) {
        head = q.next;
    } else {
        q.prev.next = q.next;
    }
}
复制代码

反转链表

思路: 遍历链表, 暂存当前节点next指针, 改变当前节点next指向, 更新前驱节点prev, 赋值下一遍历节点

// 单链表反转
const reverseList = (head) => {
    let cur: Node = head;
    let prev: Node = null;

    while (cur != null) { // 遍历链表
        const temp = cur.next; // 暂存当前节点next指针
        cur.next = prev; // 改变当前节点next指向
        prev = cur; // 更新前驱节点
        cur = temp; // 赋值下一遍历节点
    }
}
复制代码

获取链表中间节点

const middleNode = function(head) {
    if (head == null) return;
    const results = [];
    let curNode = head;
    while(curNode != null) {
        results.push(curNode);
        curNode = curNode.next;
    }
    if (results.length % 2 === 0) {
        return [results[parseInt(results.length / 2 -1)], results[parseInt(results.length /2)]];
    } else {
        return results[parseInt(results.length /2)];
    }
};
复制代码

查找倒数第k个节点

思路一： 得到链表长度，再遍历一次链表，第k个节点，其实就是第n-k个节点 思路二： 快慢指针

interface Node {
    data: number;
    next: Node;
}

// 第k个节点，其实就是第n-k个节点
const lookupForK1 = (head: Node, k: number) => {
 let cur = head;
 let node = head;
 let n = 0;
 while (cur != null) {
    cur = cur.next;
    n++;
 }
 for (let i = 0; i < n-k; i++) {
    node = node.next;
 }
 return node;
}

// 快慢指针
const lookupForK2 = (head: Node, k: number) => {
    let fast = head; let slow = head;
    for (let i = 0; i < k; i++) {
        fast = fast.next;
    }
    
    while (fast) {
        [fast, slow] = [fast.next, slow.next];
    }

    return slow;
}
复制代码

基于链表的LRU缓存淘汰算法

思路：维护一个有序的单链表，越靠近链表尾部的节点存储的是越早访问的数据，当访问某个数据的时候，会从链表的表头节点开始遍历链表，

• 1）如果查找得到节点，将其从原来位置删除，插入到链表头部
• 2）如果查找不到节点，对应会分两种情况： 缓存空间未满，将新的数据节点插入链表头部 缓存空间已满，删除链表尾部节点，将新的数据节点插入链表头部

// 基于链表的LRU缓存淘汰算法

/* 
实现思路，维护一个有序的单链表，越靠近链表尾部的节点存储的是越早访问的数据，当访问某个数据的时候，会从链表的表头节点开始遍历链表，

1）如果查找得到节点，将其从原来位置删除，插入到链表头部
2）如果查找不到节点，对应会分两种情况：
   缓存空间未满，将新的数据节点插入链表头部
   缓存空间已满，删除链表尾部节点，将新的数据节点插入链表头部

*/


interface Node {
    data: number;
    next: Node | null;
}


let head: Node = null; // 头节点
let cacheSize = 10; // 最大缓存空间

const lruLook = (val: number) => {
  let q: Node = head;
  let p: Node = null; // 前驱第一个节点
  let e: Node = null; // 前驱第二个节点
  let i = 0; 

  while (q !== null && q.data !== val) {
      i++;
      e = p;
      p = q;
      q = q.next;
  }

  if (q !== null) {
    if (p === null) { // q为头部节点
        return q;
    } else {
        // 将其从原来位置删除，插入到链表头部
        p.next = q.next;
        q.next = head;
        head = q;
        return q;
    }
  } else {
      // 创建新节点
      const n = {
        data: val,
        next: null
      };
      if (i === 0) { // 存储空间为空
        head = n;
      } else if (i < cacheSize) { // 存储空间未满
        n.next = head;
      } else { // 存储空间未满
        e.next = null; // 此时p为尾节点，而e是倒数第二个节点
        n.next = head;
      }
      return n;
  }

}
复制代码

冒泡排序

思路： 对n个数进行排序，每次都是由前一个数跟后一个数比较，每循环一轮， 就可以将最大的数移到数组的最后， 总共循环n-1轮，完成对数组排序。

const bubbleSort  = (arr) => {
    if (arr === null) { return; }
    //i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            // j控制比较次数，第i次循环内需要比较len-i次
            // 但是由于是由arr[j]跟arr[j+1]进行比较，所以为了保证arr[j+1]不越界，j<len-i-1
            if (arr[j] > arr[j + 1]) {
                //如果前一个数比后一个数大，则交换位置将大的数往后放。
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                
            }
            
        }
    }
}
复制代码

选择排序

思路： 冒泡排序的改良版，不再是前一个数跟后一个数相比较， 而是在每一次循环内都由一个数去跟 所有的数都比较一次，每次比较都选取相对较小的那个数来进行下一次的比较，并不断更新较小数的下标。

这样在一次循环结束时就能得到最小数的下标，再通过一次交换将最小的数放在最前面，通过n-1次循环之后完成排序

const selectSort  = (arr) => {
    if (arr === null) { return; }
    //i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1
    for (let i = 0; i < arr.length - 1; i++) {
        //minIndex 用来保存每次比较后较小数的下标。
        let minPos = i;
        //j控制比较次数，因为每次循环结束之后最小的数都已经放在了最前面，
        //所以下一次循环的时候就可以跳过这个数，所以j的初始值为i+1而不需要每次循环都从0开始，并且j<len即可
        for (let j = i + 1; j < arr.length; j++) {
            //每比较一次都需要将较小数的下标记录下来
            if (arr[minPos] > arr[j]) {
                minPos = j;
            }
        }
        //当完成一次循环时，就需要将本次循环选取的最小数移动到本次循环开始的位置。
        if (minPos != i) {
            const temp = arr[minPos];
            arr[minPos] = arr[i];
            arr[i] = temp;
        }
    }
}
复制代码

插入排序

思路：首先就默认数组中的第一个数的位置是正确的，即已经排序。 然后取下一个数，与已经排序的数按从后向前的顺序依次比较，如果该数比当前位置排好序的数小，则将排好序的数的位置向后移一位。 重复上一步骤，直到找到合适的位置。

找到位置后就结束比较的循环，将该数放到相应的位置。

const insertSort  = (arr) => {
    if (arr === null) { return; }
    //i控制循环次数，因为已经默认第一个数的位置是正确的，所以i的起始值为1，i<len，循环len-1次
    for (let i = 1; i < arr.length; i++) {
        let j = i; // 变量j用来记录即将要排序的数的位置即目标数的原位置
        let target= arr[j];
        //while循环用来为目标值在已经排好序的数中找到合适的位置，
        //因为是从后向前比较，并且是与j-1位置的数比较，所以j>0
        while (j > 0 && target < arr[j-1]) {
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = target; 
    }
}
复制代码

归并排序

思路： 分而治之的思想，递归实现，将数组每次递归切分成两个小数组，再分别递归，终止条件是小数组的起始下标大于等于结束小标，

递归公式： mergeSort(p,r) = merge(mergeSort(p,q), mergeSort(q+1,r))[p>=r]

合并方法merge：我们能获得两个小数组的下标，申请长度为r-p + 1的临时数组tempArr，同时遍历两个小数组，填充临时数组tempArr,计算哪个小数组有剩，则补到临时数组tempArr后面,最后把临时数组tempArr，整合到原数组arr中

const merge = (arr, start, center, afterCenter, end) => {
    const tempArr = new Array(end - start + 1); // 申请一个大小为end - start + 1的临时数组
    let i = start, j = afterCenter, k = 0, surplusStart, surplusEnd;
    // 切分的小数组，前后下标我们都有，同时遍历，填充临时数组
    while (i <= center && j <= end) {
        if (arr[i] <= arr[j]) {
            tempArr[k++] = arr[i++];
        } else {
            tempArr[k++] = arr[j++];
        }
    }

    // 获得遍历完后剩下的数组
    surplusStart = i;
    surplusEnd = center;

    if (j <= end) {
        surplusStart = j;
        surplusEnd = end;
    }

    while (surplusStart <= surplusEnd) {
        tempArr[k++] = arr[surplusStart++];
    }

    for (let index = 0; index <= end - start; index++) {
       arr[start + index] = tempArr[index];
    }
}

const mergeSort_c = (arr, start, end) => {
    // 终止条件
    if (start >= end)  {
        return;
    }
    const center = Math.floor((start + end) / 2);
    // 分而治之，大问题切分成小问题，用递归
    mergeSort_c(arr, start, center);
    mergeSort_c(arr, center + 1, end);

    // 归并
    merge(arr, start, center, center + 1, end);
}

// 入参 arr => 待排序数组， n => 数组大小
const mergeSort = (arr, n) => {
  mergeSort_c(arr, 0, n-1);
}

// 运行结果：[1, 2, 3, 3, 7, 8, 9, 11]
const handleArr = [11, 8, 3, 9, 7, 1, 2, 3];
mergeSort(handleArr, 8);
复制代码

快速排序

思路：分而治之的思想，递归实现，与归并的区别，没有空间换时间,核心就是找到分区临界点，把小于临界点的数值，通过数组交换。换至临界点前面，依次递归

递归公式： quicksort(p,r) = (q = partition = (A, p, r)) + quicksort(p,q-1) + quicksort(q+1,r) [p>=r]

分区方法partition：以该入参数组区间最后一个值为分区点，入参数组第一个数值为起始游标，遍历该区间数组，小于分区点qivot的，交换下标i，j的值， 游标i进一，最终得到的i之前的值都是小于分区点qivot值的，交换分区点与下标r的值，返回分区点下标，那么就分区成功了

// 核心：分区方法
const partition = (A, p, r) => {
    const qivot = A[r]; // 以该区间最后一个值为分区点
    let i = p; // 起始游标
    // 遍历该区间数组，小于分区点qivot的，交换下标i，j的值， 游标i进一，最终得到的i之前的值都是小于分区点qivot值的
    for (let j = p; j < r; j++) {
        if (A[j] < qivot) {
            [A[i], A[j]] = [A[j], A[i]];
            i++;
        }
    }
    // 交换分区点与下标i的值，那么就分区成功了
    [A[i], A[r]] = [A[r], A[i]];
    return i; // 返回分区点下标
}

const quicksort_c = (A, start, end) => {
    if (start >= end) { return; } // 终止条件
    const qivot = partition(A, start, end); // 分区

    // 数组会被分成[start...qivot-1]、qivot、 [qivot+1...end]
    quicksort_c(A, start, qivot-1);
    quicksort_c(A, qivot+1, end);
}

// 快速排序
const quicksort = (A, n) => {
    quicksort_c(A, 0, n-1);
}

// 运行结果：[1, 2, 3, 3, 7, 8, 9, 11]
const handleArr = [11, 8, 3, 9, 7, 1, 2, 3];
quicksort(handleArr, 8);
复制代码

煎饼排序

思路：遍历数组(反向遍历)找到最大值的下标，如arr[0...k]，做一次数组翻转, k会变成第一个下标，然后对整个数组arr[0, end]做一次数组翻转，那么数组最大值便会出现数组的尾部，依次遍历，得到排序好的数组。

// 反转数组
const reverse = (arr, end) => {
    for (let i = 0, j = end; i < j; i++,j--) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

var pancakeSort = function(arr) {
const ret = []; 
for (let n = arr.length; n > 1 ;n--) {
    let index = 0;
    for (let i = 1; i < n; i++) {
        if (arr[index] <= arr[i]) {
            index = i
        }
    }
    if (index === n - 1) {
        continue;
    }
    reverse(arr, index);
    reverse(arr, n - 1);
    ret.push(index+1);
    ret.push(n);
}
    return ret;
};