Leetcode刷题系列2 - 《计算机基础-算法》

剑指offer22. 链表的倒数第K个节点
剑指offer24. 反转链表
933. 最近的请求次数
树深度优先遍历
树广度优先遍历
图广度优先遍历
堆

剑指offer22. 链表的倒数第K个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

解法一：先遍历一遍链表，算出总共有多少个节点，然后再遍历一遍节点，循环次数为总数减去K，就是说倒数K个等于正数N-K个，这不是很简单嘛，上代码：

let getKthFromEnd = (head, k) => {
    let count = 0;
    let p = head;
    while(head) {
        head = head.next;
        count++;
    }
    for(let i = 0; i < count - k; i++) {
        p = p.next;
    }
    return p;
};

解法二：维护一个以K为长度的队列，遍历链表，依次入队，如果队列满了，队尾元素出队，新元素入队，遍历完链表后，队尾元素就是链表的倒数K个节点

let getKthFromEnd = function(head, k) {
    const list = [];
    while(head) {
        if(list.length >= k) {
            // 队列满了，队尾元素出队，新元素入队
            list.pop();
            list.unshift(head);
            head = head.next;
            continue;
        }
        // 队列从头插入
        list.unshift(head);
        head = head.next;
    }
    // 返回队尾元素
    return list.pop();
};

解法三：双指针，P1指向第一个节点，P2指向正数第K个节点，同时循环右移，P2到尾部时，P1指向的就是我们要找的那个
微信图片_20201019233517.png

let getKthFromEnd = function(head, k) {
    let p1 = head;
    let p2 = head;
    for(let i = 1; i < k; i++) {
        p2 = p2.next;
    }
    while(p2.next) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
};

剑指offer24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

var reverseList = function(head) {
    // if only has 0 or 1 node, return head directly
    if(head == null || head.next == null) {
        return head;
    }

    // recursion
    let newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
};

var reverseList = function(head) {
    let newHead = null;
    while(head != null) {
        let tmp = head.next;
        head.next = newHead;
        newHead = head;
        head = tmp;
    }
    return newHead;
};

迭代法图解：

依次迭代就行

933. 最近的请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证每次对 ping 的调用都使用比之前更大的 t 值。

输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

var RecentCounter = function() {
    this.q = [];
};

RecentCounter.prototype.ping = function(t) {
    this.q.push(t);
    while(this.q[0] < t - 3000) {
        this.q.shift();
    }
    return this.q.length;
};

树深度优先遍历

访问根节点，对根节点的children挨个进行深度优先遍历

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 = (tree) => {
  console.log(tree.val);
  tree.children.forEach(dfs);
};

dfs(tree);

树广度优先遍历

新建一个队列，把根节点入队
把队头出队访问
把对头children挨个入队
重复2、3步，直到队列为空 ```javascript const tree = { val: “a”, children: [ { val: “b”, children: [
```
 {
   val: "d",
   children: [],
 },
 {
   val: "e",
   children: [],
 },
```
], }, { val: “c”, children: [
```
 {
   val: "f",
   children: [],
 },
 {
   val: "g",
   children: [],
 },
```
], }, ], };

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

bfs(tree);


<a name="uRBQJ"></a>
## 图
邻接矩阵<br />![WeChat Image_20210116204014.jpg](https://cdn.nlark.com/yuque/0/2021/jpeg/493315/1610800899714-b7918ae8-f7d9-47b1-9c73-9070b652fd4d.jpeg#align=left&display=inline&height=715&margin=%5Bobject%20Object%5D&name=WeChat%20Image_20210116204014.jpg&originHeight=715&originWidth=1920&size=69599&status=done&style=none&width=1920)<br />邻接表<br />![WeChat Image_20210116204024.jpg](https://cdn.nlark.com/yuque/0/2021/jpeg/493315/1610800908308-9bd933a9-40cd-4e2a-a0fc-a8f33cb50ece.jpeg#align=left&display=inline&height=686&margin=%5Bobject%20Object%5D&name=WeChat%20Image_20210116204024.jpg&originHeight=686&originWidth=1920&size=69366&status=done&style=none&width=1920)
<a name="kDbi7"></a>
## 图深度优先遍历
访问根节点<br />对根节点的**没访问过的相邻节点**挨个进行深度遍历
```javascript
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);

图广度优先遍历

新建一个队列，把根节点入队
把队头出队访问
把对头没访问过的相邻节点挨个入队
重复2、3步，直到队列为空 ```javascript const graph = { 0: [1, 2], 1: [2], 2: [0, 3], 3: [3], };

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


<a name="yM8G9"></a>
## 太平洋大西洋水流问题
给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
```javascript
给定下面的 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  *
          *   *   *   *   * 大西洋

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

新建2个矩阵，分别记录能流到2个大洋的坐标
从海岸线多管齐下，同时深度优先遍历图，过程中填充上述矩阵

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function(matrix) {
    if(!matrix || !matrix[0]) {
        return [];
    }
    const m = matrix.length;
    const n = matrix[0].length;
    // 记录能流到太平洋的坐标
    const flow1 = Array.from({length:m}, () => new Array(n).fill(false));
    // 记录能流到大西洋的坐标
    const flow2 = Array.from({length:m}, () => new Array(n).fill(false));

    const dfs = (r, c, flow) => {
        flow[r][c] = true;
        [[r-1, c], [r+1,c],[r,c-1],[r,c+1]].forEach(([nr, nc]) => {    
            if(
                // 保证节点在矩阵中
                nr >= 0 && nr < m && 
                nc >= 0 && nc < n &&
                // 防止死循环
                !flow[nr][nc] &&
                // 保证逆流而上
                matrix[nr][nc] >= matrix[r][c]
            ) {
                dfs(nr, nc, flow);
            }
        })
    };

    // 沿着海岸线逆流而上
    for(let r = 0; r < m; r++) {
        dfs(r, 0, flow1);
        dfs(r, n - 1, flow2);
    }

    for(let c = 0; c < n; c++) {
        dfs(0, c, flow1);
        dfs(m-1, c, flow2);
    }

    const res = [];
    for(let r = 0; r < m; r++) {
        for(let c = 0; c < n; c++) {
            if(flow1[r][c] && flow2[r][c]) {
                res.push([r, c]);
            }
        }
    }
    return res;
};

堆

WeChat Image_20210116212711.jpg
堆能快速找出最大值和最小值
找出第K个最大或最小元素

找出第K个最大元素

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

class MinHeap {
  constructor() {
    this.heap = [];
  }
  getParentIndex(i) {
    return (i - 1) >> 1;
  }
  getLeftIndex(i) {
    return i * 2 + 1;
  }
  getRightIndex(i) {
    return i * 2 + 2;
  }
  swap(i1, i2) {
    const tmp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = tmp;
  }
  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() {
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
  }
  // get top of heap
  peek() {
    return this.heap[0];
  }

  // get size of heap
  size() {
    return this.heap.length;
  }
}

// 获取数组中第K大的元素
let findKthLargest = (nums, k) => {
  const h = new MinHeap();
  nums.forEach(n => {
    h.insert(n);
    if(h.size() > k) {
      h.pop();
    }
  })
  return h.peek();
}