# JS-Base

**Repository Path**: lzy_8920/js-base

## Basic Information

- **Project Name**: JS-Base
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-02-07
- **Last Updated**: 2024-04-21

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构与算法

## 一、时间复杂度

## 二、空间复杂度

## 三、数组

**数组是一种线性表数据结构。它用一组连续的内存空间，储存一组有相同类型的数据结构。**

## 四、链表

1. 单链表
2. 循环链表
3. 双向链表

| 时间复杂度 | 数组 | 链表 |
| ---------- | ---- | ---- |
| 插入、删除 | O(n) | O(1) |
| 随机访问   | O(1) | O(n) |

4. 如何基于链表实现LRU缓存淘汰算法？

   - 维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。
   - 当有一个新数据被访问时，我们从链表头开始访问。
   - 如果链表中有此结点，遍历得到该结点，删除该结点，将其插入到链表头部。
   - 如果链表中没有此结点，&&如果此时缓存未满，将此结点直接插入到链表头部。如果链表中没有此结点，&&如果此时缓存已满，先删除尾部结点，将此结点直接插入到链表头部。

5. 向空链表中插入第一个结点

   ```js
   if(head === null){
     head = new_node
   }
   ```

6. 删除链表中的最后一个结点

   ```js
   if(head.next === null){
     head = null
   }
   ```

   - 单链表反转
   - 链表中环的检测
   - 两个有序的链表合并
   - 删除链表倒数第n个结点
   - 求链表的中间结点

## 五、栈

1. 如何实现一个“栈”

   - 栈有两个操作：入栈和出栈
   - 用数组实现的栈，叫顺序栈，用链表实现的栈，叫链式栈。

   ```js
   // 剑指offer 30 包含min函数的栈
   /**
    * initialize your data structure here.
    */
   var MinStack = function () {
     this.stack = []
     this.min_stack = []
   };
   
   /** 
    * @param {number} x
    * @return {void}
    */
   MinStack.prototype.push = function (x) {
     this.stack.push(x)
     if (this.min_stack.length) {
       this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x))
     } else {
       this.min_stack.push(x)
     }
   };
   
   /**
    * @return {void}
    */
   MinStack.prototype.pop = function () {
     this.stack.pop()
     this.min_stack.pop()
   };
   
   /**
    * @return {number}
    */
   MinStack.prototype.top = function () {
     return this.stack[this.stack.length - 1]
   };
   
   /**
    * @return {number}
    */
   MinStack.prototype.min = function () {
     return this.min_stack[this.stack.length - 1]
   };
   
   /**
    * Your MinStack object will be instantiated and called as such:
    * var obj = new MinStack()
    * obj.push(x)
    * obj.pop()
    * var param_3 = obj.top()
    * var param_4 = obj.min()
    */
   ```

2. 支持动态扩容的栈
3. 栈在函数调用中的应用
4. 栈在括号匹配中的应用
   - 扫描到括号时，将其压入栈。
   - 扫描到右括号时，从栈顶取出一个做括号，看能否匹配。

思考：为什么函数调用要用“栈”来保存临时变量呢？

- 不一定非要用栈来保存临时变量，但如果这个函数调用符合后进先出的特性，用栈实现最合适。
- 从调用函数到进入被调用函数，变化的是**作用域**。
- 所以只要保证每进入一个新函数时，都是一个新的作用域就可以。
- 而实现这个，用栈最方便。在进入被调用函数时，分配一段栈空间给这个函数的变量，在函数结束时，将栈顶复位，正好回到调用函数的作用域内。

## 六、队列

队列跟栈一样，也是一种操作受限的线性表数据结构。

1. 顺序队列和链式队列
   - 队列需要两个指针，head指向头部，tail指向队尾。
   - 当tail移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据。
   - 当队列的tail指针移动到数组的最右边后，如果有新的数据入队，我们可以将head到tail之间的数据，整体搬移到数组中
     0到tail-head的位置。
2. 循环队列
3. 阻塞队列和并发队列
   - 阻塞队列：在队列基础上增加了阻塞操作。在队列为空时，从队头取数据会被阻塞，因为此时没数据可取。如果队列已满，那么插入队列的操作会被阻塞，直到队列中有空闲位置后再插入数据。
   - 并发队列：线程安全的队列叫并发队列。最简单的实现方法是在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。

## 七、递归

1. 递归需要满足的三个条件

   - 一个问题的解可以分解为几个自问题的解
   - 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
   - 存在递归终止条件

2. 如何编写递归代码

3. 递归代码要警惕堆栈溢出

   - 函数调用会用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。

4. 递归代码要警惕重复计算

   - 在计算f5时，需要先计算f4和f3，而计算f4还需要计算f3，这里f3被计算了很多次，这就是重复计算问题。

   - 为了避免重复计算，可以通过一个数据结构（如散链表）保存计算过的值。

     ```java
     public int f(int n) {
       if (n == 1) return 1;
       if (n == 2) return 2;
       
       // hasSolvedList可以理解成一个Map，key是n，value是f(n)
       if (hasSolvedList.containsKey(n)) {
         return hasSolvedList.get(n);
       }
       
       int ret = f(n-1) + f(n-2);
       hasSolvedList.put(n, ret);
       return ret;
     }
     ```

   - 递归代码中多了很多函数的调用，当这些函数调用的数量较大时，就会积聚成一个较大的时间成本。

5. 怎么讲递归改写成非递归代码

   ```js
   // 递归公式 f(n)=f(n-1)+1 其中，f(1)=1
   // 递归代码
   int f(int n) {
     if (n == 1) return 1;
     return f(n-1) + 1;
   }
   //非递归代码
   int f(int n) {
     int ret = 1;
     for (int i = 2; i <= n; ++i) {
       ret = ret + 1;
     }
     return ret;
   }
   ```

## 八、排序

1. 如何分析一个排序算法

   - 排序算法的执行效率

     - 最好情况、最坏情况、平均时间复杂度。
     - 时间复杂度的系数、常数、低阶。
     - 比较次数和交换次数。

   - 排序算法的内存消耗

     算法的内存消耗可以通过空间复杂度来衡量。

   - 排序算法的稳定性

     一组数据中出现两个相同的数，在经过某种排序后，如果前后位置没改变，叫作**稳定的排序算法**；如果顺序发生变化，叫作**不稳定的排序算法**。

2. 冒泡排序

   - 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
   - 当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。我这里还有另外一个例子，这里面给6个元素排序，只需要4次冒泡操作就可以了。

   ```java
   // 冒泡排序，a表示数组，n表示数组大小
   public void bubbleSort(int[] a, int n) {
     if (n <= 1) return;
    
    for (int i = 0; i < n; ++i) {
       // 提前退出冒泡循环的标志位
       boolean flag = false;
       for (int j = 0; j < n - i - 1; ++j) {
         if (a[j] > a[j+1]) { // 交换
           int tmp = a[j];
           a[j] = a[j+1];
           a[j+1] = tmp;
           flag = true;  // 表示有数据交换      
         }
       }
       if (!flag) break;  // 没有数据交换，提前退出
     }
   }
   ```

   - 冒泡排序是原地排序算法吗

     冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。

   - 冒泡排序是稳定的排序算法吗

     在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

   - 冒泡排序的时间复杂度是多少

     最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行n次冒泡操作，所以最坏情况时间复杂度为O(n2)。

3. 插入排序

   ```JAVA
   // 插入排序，a表示数组，n表示数组大小
   public void insertionSort(int[] a, int n) {
     if (n <= 1) return;
   
     for (int i = 1; i < n; ++i) {
       int value = a[i];
       int j = i - 1;
       // 查找插入的位置
       for (; j >= 0; --j) {
         if (a[j] > value) {
           a[j+1] = a[j];  // 数据移动
         } else {
           break;
         }
       }
       a[j+1] = value; // 插入数据
     }
   }
   ```

4. 选择排序

   选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

   ![image-20211118180658586](assets/冒泡、插入、选择.png)

5. 归并排序

   - 稳定排序算法
   - 时间复杂度 O(nlogn)
   - 空间复杂度 O(n)

6. 快速排序

   - 快排的思想是这样的：如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。
   - 我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。
   - 原地、不稳定的排序算法。
   - 时间复杂度 O(nlogn)

## 九、线性排序

1. 桶排序

   - 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了
   - 时间复杂度O(n)
   - 桶排序对要排序数据的要求是非常苛刻的：首先，要排序的数据需要很容易就能划分成m个桶，并且，桶与桶之间有着天然的大小顺序。其次，数据在各个桶之间的分布是比较均匀的。

2. 计数排序

   - **计数排序其实是桶排序的一种特殊情况**。当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

3. 基数排序

   基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了

## 十、排序优化

## 十一、二分查找

```JS
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let low = 0
  let high = nums.length - 1
  while (low <= high) {
    let mid = Math.floor((low + high) / 2)
    if (nums[mid] === target) {
      return mid
    } else if (nums[mid] > target) {
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return -1
};
```

**二分查找应用场景的局限性**

- 二分查找依赖的是顺序表结构，简单点说就是数组。
- 二分查找针对的是有序数据。
- 数据量太小不适合二分查找。
- 数据量太大也不适合二分查找。

**变形1: 查找第一个值等于给定值的元素**

```Java
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      // 如果mid等于0，那这个元素已经是数组的第一个元素，那它肯定是我们要找的；
      // 如果mid不等于0，但a[mid]的前一个元素a[mid-1]不等于value，那也说明a[mid]就是我们要找的第一个值等于给定值的元素。
      else high = mid - 1;
      // 如果经过检查之后发现a[mid]前面的一个元素a[mid-1]也等于value，那说明此时的a[mid]肯定不是我们要查找的第一个值等于给定值的元素。那我们就更新high=mid-1，因为要找的元素肯定出现在[low, mid-1]之间。
    }
  }
  return -1;
}
```

**变形2: 查找最后一个值等于给定值的元素**

```java
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}
```

**变形3: 查找第一个大于等于给定值的元素**

```JAVA
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {
      // 对于a[mid]大于等于给定值value的情况，我们要先看下这个a[mid]是不是我们要找的第一个值大于等于给定值的元素。
      // 如果a[mid]前面已经没有元素，或者前面一个元素小于要查找的值value，那a[mid]就是我们要找的元素。
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      // 如果a[mid-1]也大于等于要查找的值value，那说明要查找的元素在[low, mid-1]之间，所以，我们将high更新为mid-1。
      else high = mid - 1;
    } else {
      // 如果a[mid]小于要查找的值value，那要查找的值肯定在[mid+1, high]之间，所以，我们更新low=mid+1。
      low = mid + 1;
    }
  }
  return -1;
}
```

**变形4：查找最后一个小于等于给定值的元素**

```JAVA
public int bsearch7(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

```

## 十三、跳表

它是一种各方面性能都比较优秀的**动态数据结构**，可以支持快速地插入、删除、查找操作。

1. 如何理解跳表

   - 对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是O(n)。

   ![image-20211118180658586](assets/原始链表.png)

   - 那怎么来提高查找效率呢？如果像图中那样，对链表建立一级“索引”，查找起来是不是就会更快一些呢？每两个结点提取一个结点到上一级，我们把抽出来的那一级叫做**索引**或**索引层**

   ![image-20211118180658586](assets/索引链表.png)

   - 如果我们现在要查找16，我们可以先在索引层遍历，当遍历到索引层中值为13时，我们发现下一个结点是17，那要查找的结点16肯定就在这两个结点之间。然后我们通过索引层结点的down指针，下降到原始链表这一层，继续遍历。这时，我们只需要再遍历2个结点，就可以找到值16的这个结点了。原来如果要查找16，需要遍历10个结点，现在只需要遍历7个结点。

2. 跳表的时间复杂度：O(logn)

3. 空间复杂度：O(n)

## 十四、哈希算法

### 什么是哈希算法？

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是**哈希算法**，而通过原始数据映射之后得到的二进制值串就是**哈希值**。

### 应用一：安全加密

**MD5**（MD5 Message-Digest Algorithm，MD5消息摘要算法）和**SHA**（Secure Hash Algorithm，安全散列算法）

### 应用二：唯一标识

哈希算法可以对大数据做信息摘要，通过一个较短的二进制编码来表示很大的数据。

### 应用三：数据校验

用于校验数据的完整性和正确性。

### 应用四：散列函数

### 应用五：负载均衡

实现一个会话粘滞的负载均衡策略。

### 应用六：数据分片

对处理的海量数据进行分片，多机分布式处理，可以突破单机资源的限制

### 应用七：分布式存储

解决缓存等分布式系统的扩容、缩容导致数据大量搬移的难题

## 十五、二叉树

1. 树的高度、深度、层。

   <img src="assets/二叉树的高度深度层.png" alt="image-20211118180658586" style="zoom:50%;" />

2. 满二叉树、完全二叉树

   - 满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做**满二叉树**。
   - 完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做**完全二叉树**。

3. 二叉树的遍历

   **前序遍历**、**中序遍历**和**后序遍历**

## 十六、堆

- 堆是一个完全二叉树，完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
- 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
- 对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”。

## 十七、图

- 树中的元素我们称为节点，图中的元素我们就叫做**顶点**
- 顶点的**度**（degree），就是跟顶点相连接的边的条数
- 边有方向的图叫做“有向图”。以此类推，我们把边没有方向的图就叫做“无向图”
- 无向图中有“度”这个概念，表示一个顶点有多少条边。在有向图中，我们把度分为**入度**（In-degree）和**出度**（Out-degree）
- 顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点
- 在带权图中，每条边都有一个权重

## 十八、字符串匹配

1. BF算法：暴力对比
2. RK算法
   - 对n-m+1个子串求哈希值
   - 假设要匹配的字符串的字符集中只包含K个字符，我们可以用一个K进制数来表示一个子串，这个K进制数转化成十进制数，作为子串的哈希值
3. BM算法

## 十九、贪心算法

## 二十、分支算法

分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

## 二十一、回溯算法

回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

### 解决问题

1. 组合问题：N个数里面按一定规则找出k个数的集合
2. 切割问题：一个字符串按一定规则有几种切割方式
3. 子集问题：一个N个数的集合里有多少符合条件的子集
4. 排列问题：N个数按照一定规则全排列，有几种排列方式
5. 棋盘问题：N皇后，解数独等

### 回溯法模版

1. 回溯函数模版返回值以及参数

   ```JS
   void backtracking(参数)
   ```

2. 回溯函数终止条件

   什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

   ```JS
   if (终止条件) {
       存放结果;
       return;
   }
   ```

3. 回溯搜索的遍历过程

   在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

   ![回溯算法理论基础](README.assets/回溯搜索的遍历过程.png)

   ```JS
   for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
       处理节点;
       backtracking(路径，选择列表); // 递归
       回溯，撤销处理结果
   }
   ```

   - for循环就是遍历集合区间，可以理解一个节点有多少孩子，for循环就执行多少次
   - 从图中可以看出for循环是横向遍历，backtracking递归是纵向遍历，搜索到叶子节点就是找到一个结果了

   ```JS
   void backtracking(参数) {
       if (终止条件) {
           存放结果;
           return;
       }
   
       for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
           处理节点;
           backtracking(路径，选择列表); // 递归
           回溯，撤销处理结果
       }
   }
   ```