最近在看数据结构与算法之美，结合刷题。留点经验书方便以后复习。

### 1. 数组
**数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。**
连续的空间和相同类型的数据的限制使得数组支持：随机访问的特性。根据下标随机访问的时间复杂度为O(1)。  

为什么数组都下标从0开始而不是1？  
`从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用a来表示数组的首地址，a[0]就是偏移为0的位置，也就是首地址，a[k]就表示偏移k个type_size的位置，所以计算a[k]的内存地址只需要用这个公式： a[k]_address = base_address + k * type_size 但是，如果数组从1开始计数，那我们计算数组元素a[k]的内存地址就会变为： a[k]_address = base_address + (k-1)*type_size 对比两个公式，我们不难发现，从1开始编号，每次随机访问数组元素都多了一次减法运算，对于CPU来说，就是多了一次减法指令。 数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从0开始编号，而不是从1开始。`

##### 关于数组的一道算法题：

> 给定一个整数数组 `nums` 和一个整数目标值 `target`，请你在该数组中找出 **和为目标值** *`target`*  的那 **两个** 整数，并返回它们的数组下标。  
>
> 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。  
> 你可以按任意顺序返回答案。

**示例 1：**
```
输入： nums = [2,7,11,15], target = 9
输出： [0,1]
解释： 因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
```
这是一道典型的空间换时间的算法题，如果暴力解法时间复杂度为O(n^2)。  
`转换思路，将出现过的值使用Map的键值做记录，只需要循环一次。时间复杂度为O(n)。  `  
`该算法题可推广到多种数组多重循环的场景。`
```
var twoSum = function(nums, target) {
  let result
  const map = new Map()
  // some return true end
  nums.some((num, index) => {
    if(map.has(target - num)) {
      result = [map.get(target - num), index]
      return true
    } else {
      map.set(num, index)
    }
  })
  return result ?? new Error('not have num can be sum')
};
```

### 2. 链表
链表通过“指针”将一组**零散的内存块**串联起来存储数据。我们把内存块称为链表的“**结点**”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。我们把这个记录下个结点地址的指针叫作**后继指针next**。  
针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是O(1)。链表随机访问的性能没有数组好，需要O(n)的时间复杂度。尽管单纯的删除操作时间复杂度是O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为O(n)。根据时间复杂度分析中的加法法则，**删除值等于给定值的结点对应的链表操作的总时间复杂度为O(n)**。

#### 数组 vs 链表
> 在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。
>
> 数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。
> 
> 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。

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

> 维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
>
> 1.如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
>
> 2.如果此数据没有在缓存链表中，又可以分为两种情况：
>
>-   如果此时缓存未满，则将此结点直接插入到链表的头部；
>-   如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

#### 链表的算法题
##### 1. 求链表相加。  
解题感悟：对于链表一般的循环都是while节点是否存在，循环体中写入指针移动操作。
对于链表的操作，很多时候加个头节点或者尾节点占位可以减少判断的逻辑。
```
var addTwoNumbers = function(l1, l2) {
  let carry = 0
  const head = new ListNode()
  let cur = head

  while(l1 || l2 || carry){
    if(l1){
      carry += l1.val
      l1 = l1.next
    }
    if(l2){
      carry += l2.val
      l2 = l2.next
    }

    cur.next = new ListNode(carry % 10)
    cur = cur.next
    carry = carry >= 10 ? 1 : 0
  }

  return head.next
};
```
##### 2. 链表删除操作
给你一个链表，删除链表的倒数第 `n` 个结点，并且返回链表的头结点。
解题感悟：  
1. 最暴力的解法就是循环一次，知道链表的总长度然后第二次循环到倒数第n个节点去做删除。  
2. 一开始我想的是，沿用数组减少循环的思想，用一个数组在循环的时候记录整张链表，可以在数组中做操作去指定节点拼接。代价是空间复杂度比较高。
3. 在只循环一次的时候记录链表这个想法应该是时间复杂度最低的只要O(n),减低空间复杂度的话需要思考的是如何不记录整张链表就可以操作倒数第n个节点。显然找到倒数第n个节点是最关键的。我们并不需要存储每个链表节点。用一个指针去记录就可以了，一个指针又没办法做好标志，因为你不知道哪个节点是最后一个节点。所以需要一个参照位。`即：用两个快慢指针，快指针比慢指针多移位n位，当快指针指向最后一个节点时，慢指针就是倒数第n位。`
```
// 使用两个指针而非存储整个链表
var removeNthFromEnd = function(head, n) {
  const header = new ListNode(null, head)
  let cur = header
  let pre = header

  while(n--){
    pre = pre.next
  }

  while (pre.next) {
    cur = cur.next
    pre = pre.next
  }
  
  cur.next = cur.next?.next ?? null
  return header.next
};
```
##### 3. 合并两个有序链表
将两个升序链表合并为一个新的 **升序** 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路：  
1. 按照之前总结的规律，先创建一个头指针方便代码实现。
2. 链表循环正常思路判断节点是否存在然后指针后移。
3. 比大小，小的入新链表。
4. 当有一个链表为空时，剩下的就不用循环了直接接尾。
正常的解题思路，判空做好就可以。

```
var mergeTwoLists = function(l1, l2) {
  const head = new ListNode(null)
  let cur = head
  while(l1 && l2){
    const l1val = l1.val
    const l2val = l2.val
    if(l1val < l2val){
      cur.next = new ListNode(l1val)
      l1 = l1.next
    } else {
      cur.next = new ListNode(l2val)
      l2 = l2.next
    }
    cur = cur.next
  }
  // 一个链表空了之后就不用判断了
  cur.next = l1 ? l1 : l2
  return head.next
};
```
还有就是比较简洁的递归写法：
```
var mergeTwoLists = function(l1, l2) {
  //递归的结束条件，如果l1和l2中有一个为空就返回
  if (l1 == null || l2 == null) {
    return l1 ? l1 : l2
  }
  //如果l1的值<=l2的值，就继续递归，比较l1.next的值和l2的值
  if (l1.val <= l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
  }
};
```
##### 4. 反转链表
给你单链表的头节点 `head` ，请你反转链表，并返回反转后的链表。  
思路：  
1. 最简单的迭代法：循环整张链表，将链表压入一个栈中，再逐一出栈即可。时间复杂度O(2n)，空间复杂度O(2n)。
2. 更好的解题思路： 要将链表反向，其实只要每个节点的指针从后向前指就可以。所以创建新的链表去重排，核心思路是用一个指针记住前一个节点的位置。然后将当前节点的next指向前一个节点。问题在于将当前节点的next指向前一个节点就会丢失下一个节点。`cur.next = pre`这行代码执行完之后当前节点的后一个节点就会丢失。所以需要提前保存下一个节点。完成next指针的反选之后将节点都后移一位直到链尾。
```
var reverseList = function(head) {
  let cur = head
  let pre = null
  while(cur){
    // 保存下一个节点
    const next = cur.next
    // 将下一个节点的指针反向
    cur.next = pre

    // 两个指针都后移一位
    pre = cur
    cur = next
  }
  return pre
};
```
3. 递归的解法：写一个反向指针的函数，明确退出条件。

```
var reverseList = function(head) {
  const reverse = (pre, cur) => {
    if(!cur) return pre

    const next = cur.next
    cur.next = pre
    
    return reverse(cur, next)
  }
  return reverse(null, head)
};
```
##### 5.链表的环检测
解题思路：  
1. 将每个节点存储入一个集合，判断是否存在相同的节点。时间复杂度O(n)，空间复杂度O(n)
`顺便记录一个知识点 WeakSet 的成员只能是对象，而不能是其他类型的值。WeakSet 中的对象都是弱引用，即垃圾回收机制不考虑 WeakSet 对该对象的引用，也就是说，如果其他对象都不再引用该对象，那么垃圾回收机制会自动回收该对象所占用的内存，不考虑该对象还存在于 WeakSet 之中。WeakSet 的成员是不适合引用的，因为它会随时消失。另外，由于 WeakSet 内部有多少个成员，取决于垃圾回收机制有没有运行，运行前后很可能成员个数是不一样的，而垃圾回收机制何时运行是不可预测的，因此 ES6 规定 WeakSet 不可遍历。`
```
var hasCycle = function(head) {
  const set = new WeakSet()
  while(head) {
    if(set.has(head)) return true

    set.add(head)
    head = head.next
  }
  return false
};
```
2. 成环判断可以是重复的节点，也可以利用跑圈原理即快慢指针在环内相遇可以作为成环判断。定义一个快指针每次跑两步，一个慢指针每次跑一步。当快慢指针相遇时，表示链表成环，反则不成环。  
由此可以衍生出求入环处的解法如下：
```
var detectCycle = function(head) {
  let fast = head, slow = head
  while (fast?.next) {
    slow = slow.next
    fast = fast.next.next

    if(fast === slow){
      let start = head
      while(start !== slow){
        start = start.next
        slow = slow.next
      }
      return start
    }
  }
  return null 
};
```

### 3. 栈
**先进后出，后进先出即为栈。**  实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。  
栈作为一个比较基础的数据结构，应用场景还是蛮多的。1. 比较经典的一个应用场景就是函数调用栈。2. 编译器利用栈来实现表达式求值。3. 栈在括号匹配中的应用。
#### 栈的算法题
##### 1. 有效括号
给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串 `s` ，判断字符串是否有效。
有效字符串需满足：1. 左括号必须用相同类型的右括号闭合。2. 左括号必须以正确的顺序闭合。

<details>
<summary>有效括号(点击查看)</summary>

```
var isValid = function(s) {
  const stack = []
  const map = {
    ')': '(',
    ']': '[',
    '}': '{'
  }
  for (let i = 0; i < s.length; i++) {
    if(Object.values(map).includes(s[i])) {
      stack.push(s[i])
    } else {
      if(stack.pop() !== map[s[i]]){
        return false
      }
    }
  }
  return !stack.length
}
```
</details>

##### 2. 基本计算器
大家感兴趣可以自己试着写一下。  
类似输入'1+2--(4--5)+6'，可以返回正确答案即可。
<details>
<summary>基本计算器 粗略实现(点击查看)</summary>

```
function calculate(s) {
  let i = 0
  const op_stack = []
  const nums = [0]

  const cal = () => {
    if([0, 1].includes(nums.length)) return
    if(!op_stack.length) return

    const a = nums.pop()
    const b = nums.pop()
    const op = op_stack.pop()
    nums.push(op === '+' ? a + b : b - a)
  }

  const isNum = n => /[0-9]/.test(n)

  const getNum = () => {
    let num = ''
    while(isNum(s[i])){
      num += s[i++]
    }
    return Number(num)
  }

  while(i < s.length) {
    if(s[i] === ' '){
      i++
      continue
    }

    if(s[i] === '('){
      op_stack.push(s[i++])
    }

    if(s[i] === ')') {
      while(op_stack[op_stack.length - 1] !== '(') {
        cal()
      }
      i++
      op_stack.pop()
    }

    if(isNum(s[i])){
      const num = getNum()
      nums.push(num)
    }

    if(['-', '+'].includes(s[i])){
      while(op_stack.length && op_stack[op_stack.length - 1] !== '('){
        cal()
      }

      if(s[i-1] === '('){
        nums.push(0)
      }

      op_stack.push(s[i++])
    }

  }

  while(op_stack.length) {
    cal()
  }

  return nums[1] ?? nums[0]
};
```
</details>

### 3. 队列
**先进先出就是典型的队列。** 队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素。  
作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。  
实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？

> 基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
>
> 而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

### 4. 递归
**递归是一种应用非常广泛的算法（或者编程技巧）。** 
> 递归需要满足的三个条件  
> 1. 一个问题的解可以分解为几个子问题的解
> 2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
> 3. 存在递归终止条件
所以编写递归代码最重要的思路就是：将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
> 递归还有两个比较常见的问题：  
> 1. 递归代码要警惕堆栈溢出  
> 2. 递归代码要警惕重复计算

文章首发于juejin