By Long Luo

This article is the solution 3 Approaches: Brute Force, Stack, Slow Fast Pointers with Animation of Problem 19. Remove Nth Node From End of List .

Here shows 3 Approaches to slove this problem: Brute Force, Stack, Slow Fast Pointers.

Brute Froce

It’s easy to think of the way that we traverse the linked list first, from the head node to the end node, to get the length of the linked list \(L\).

Then we traverse the linked list from the head node again. When the \(L-n+1\) th node is traversed, it is the node we need to delete.

We can traverse \(L-n+1\) nodes starting from the dummy node. When traversing to the \(L-n+1\)th node, its next node is the node we need to delete, so we only need to modify the pointer once to complete the deletion operation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public static ListNode removeNthFromEnd(ListNode head, int n) {
    if (head.next == null && n == 1) {
        return null;
    }

    List<ListNode> nodeList = new ArrayList<>();
    ListNode pNode = head;
    int size = 0;
    while (pNode != null) {
        nodeList.add(pNode);
        size++;
        pNode = pNode.next;
    }

    if (n == size) {
        return head.next;
    } else if (n == 1) {
        pNode = nodeList.get(size - 2);
        pNode.next = null;
    } else {
        pNode = nodeList.get(size - n - 1);
        pNode.next = pNode.next.next;
    }

    return head;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)

By Long Luo

This article is the solution From Brute Force to DP to Two Pointers with Detail Explaination of Problem 42. Trapping Rain Water .

Intuition

It’s like Leetcode 11. Container With Most Water , we can consider the black block as a wall, the blue block as water. Given an array, each element represents the height of the wall from left to right, find out how many units of water can be held.

The solution can be refered 2 Approaches: BF and Two Pointers with Image Explaination .

1. Brute Force

It’s easy to use the brute force approach. The time complexity is \(O(max^n)\) , so it will TLE.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// Row time: O(max * n) space: O(1)
// TLE
public static int trap_row(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int ans = 0;
    int len = height.length;
    int maxHeight = 0;

    for (int x : height) {
        maxHeight = Math.max(maxHeight, x);
    }

    for (int i = 1; i <= maxHeight; i++) {
        boolean flag = false;
        int water = 0;
        for (int j = 0; j < len; j++) {
            if (flag && height[j] < i) {
                water++;
            }

            if (height[j] >= i) {
                ans += water;
                water = 0;
                flag = true;
            }
        }
    }

    return ans;
}

Analysis

• Time Complexity: \(O(max^n)\)
• Space Complexity: \(O(1)\)

By Long Luo

大学时学通信专业课程 计算机网络¹ 时，需要学习 TCP/IP 协议族 ² 。在学习网络层的路由协议时， \(\textit{Dijkstra}\) ³ 算法是必须要掌握的。不过读书时，对这个算法是懵懵懂懂的，当时是死记硬背记住的，并没有理解其原理，过了一段时间之后就完全忘记了。如今在 2022 年我重新学习 搜索算法⁴ 时，已经彻底理解 \(\textit{Dijkstra}\) 算法了。更确切的说，如果我们掌握了其原理，我们也可以重新发明 \(\textit{Dijkstra}\) 算法，就让我们从一个自驾游例子开始吧！

到达目的地哪条路径最快？

假期时，我们想从深圳自驾去上海，怎么去呢？打开地图软件，地图会给你规划好几条路线，在找到这些路线的背后就用到了 \(\textit{A Star}\)⁵ 算法 或者 \(\textit{Dijkstra}\) 算法，它们都属于 最短路径算法⁶ 。这个例子解释 用来\(\textit{Dijkstra}\) 算法并不是特别好，但方便大家理解。

假如回到那个 2G 时代，没有导航软件只有一张地图，大家会怎么做呢？

我们可能要根据到高速和城市之间里程来计算，比如北上赣州，经南昌、杭州到上海和经福建、温州、宁波再到上海哪个更快，不同城市之间高速路况情况，每段之间耗时多长，最后得到了一条路线。虽然大部分人并不知道 \(\textit{Dijkstra}\) 算法，但并不妨碍我们天生就会用 \(\textit{Dijkstra}\) 算法，所以我们把这个思考过程写下来，实际上就是 \(\textit{Dijkstra}\) 算法。

让我们重新一步一步来发现 \(\textit{Dijkstra}\) 算法吧！

从 BFS 开始

由于找合适的国内城市路线图和制图太花时间，刚好维基上的 Breadth-first search algorithm⁷ 的页面上就提供了德国国内城市地图的例子，这里就借用下，如下图所示：

如果我们从 法兰克福(Frankfurt) 出发，很容易得到到达各个城市的最快方式，如下图所示：

以下面这个动图为例，我们来看看 \(\textit{BFS}\) 是如何做的？

从上图可以看出，\(\textit{BFS}\) 的运行过程可以描述如下：

1. 首先选择一个顶点作为起始结点，并将其染成蓝色，其余未访问结点为黑色；
2. 将起始结点放入队列中；
3. 从队列首部选出一个顶点，并找出所有与之邻接的结点，将找到的邻接结点放入队列尾部，将已访问过结点涂成蓝色，没访问过的结点是黑色。如果顶点的颜色是蓝色，表示已经发现并且放入了队列，如果顶点的颜色是黑色，表示还未访问；
4. 按照同样的方法处理队列中的下一个结点，直到所有节点都访问完毕。

伪代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

procedure BFS(G, source) is
      let Q be a queue
      label source as explored
	  
      Q.enqueue(source)
	  
      while Q is not empty do
          v := Q.dequeue()
		  
          if v is the goal then
              return v
        
          for all edges from v to w in G.adjacentEdges(v) do
              if w is not labeled as explored then
                  label w as explored
                  w.parent := v
                  Q.enqueue(w)

By Long Luo

This article is the solution Just One Line Code with Detailed Explanation of Problem 342. Power of Four .

Math

If \(n\) is a power of \(4\), it must be \(n = 4^x, x \ge 0\).

Then:

\[ 4^x \equiv (3+1)^x \equiv 1^x \equiv 1 \quad (\bmod ~3) \]

If \(n = 2^x\) but \(n \ne 4^x\), it must be \(n = 4^x \times 2\), which means \(n \equiv 2 \quad (\bmod ~3)\).

Therefore, we can check whether \(n = 4^x\) by whether \(n \equiv 1 \quad(\bmod ~3)\).

By Long Luo

矩阵存图法

图中的顶点我们已经编好了号，那么我们需要储存的和图相关的信息，就只剩下点与点之间的连边了。

一个很直观的想法就是用一个二维数组来存图，下标代表点，值代表连边的情况。这就是所谓的矩阵存图法，也被称作为邻接矩阵存图法。

更具体地，我们一般使用 bool 数组来储存点与点之间的连边信息：

如果 con[i][j] 的值为 true ，表示点 i 与点 j 之间连了一条从 i 指向 j 的边。 如果 con[i][j] 的值为 false ，表示点 i 与点 j 之间没有连边。

以下图为例：

邻接表存图法

前面我们说过，矩阵存图的最大的劣势，就是在面对稀疏图时，有很多空间没有储存有效信息（对于一个图，我们往往更加关注哪些点之间有连边，而不关注哪些点之间没有连边），被浪费掉了。一个优化的思路是：我们不再考虑储存每一个点对之间的连边信息，而只考虑那些有连边的点对。这样我们就能够保证所储存下来的信息都会是有效的。

针对上述思路，对于一个有 nn 的点的图，我们可以利用 nn 个链表，第 ii 个链表里存着所有从 ii 直接连向的点。以下图为例：

参考资料

1. Breadth-First Search
2. Depth-First Search
3. Connected Components
4. LeetBook 图
5. Prim Minimum Cost Spanning Treeh
6. LeetBook BFS Graph Theory — History & Overview Part I — What Is Graph Theory & Why Is It Relevant Today? Graph Theory — Basic Properties Graph Theory — On To Network Theory Graph Theory — Set & Matrix Notation