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

By Long Luo

前言

前几天看了一个介绍 核磁共振成像(MRI) 原理的视频：三维演示磁共振成像（MRI）原理 ，加上自己也曾做过 \(2\) 次核磁共振，一直很好奇其原理，所以花了点时间弄懂了核磁共振成像原理。

在这篇文章我们不详细介绍核磁共振成像原理，只关注其成像部分，也就是根据获取到的空间频率来还原图像，也就是二维傅里叶逆变换(\(\textit{2D Inverse Fourier Transforms}\))。

关于傅里叶变换及傅里叶逆变换，可以参考之前写过的一篇文章：傅里叶变换 。傅里叶变换本质上就是换基，推荐这篇文章：我理解的傅里叶变换 。

一维傅里叶变换(1D Fourier Transform)

对于非周期函数，我们把它的周期看作无穷大。基频 \(\omega_0=\frac{2\pi}{T}\) 则趋近于无穷小，又因为基频相当于周期函数的傅里叶级数中两个相邻频率的差值 \((n+1)\omega_0-n\omega_0\)，我们可以把它记作 \(\Delta\omega\) 或者微分 \(d\omega\)。\(n\omega_0\) 则相当于连续变量 \(\omega\)。这样就得到了针对非周期函数的频谱函数如下：

\[ c_{n}=\frac{\Delta\omega}{2\pi}\int_{-\infty}^{+\infty} f(t)e^{-jwt}dt \]

我们会发现这里的 \(c_n\) 是趋于 \(0\) 的。

将它代入 \(f(t)=\sum_{n=-\infty}^{n=+\infty}c_ne^{jn\omega_0t}\)

得到：

\[ f(t)=\sum_{-\infty}^{+\infty}(\frac{\Delta\omega}{2\pi}\int_{-\infty}^{+\infty} f(t)e^{-jwt}dt)e^{j\omega t}=\int_{-\infty}^{+\infty}\frac{1}{2\pi}(\int_{-\infty}^{+\infty}f(t)e^{-j\omega t}dt)e^{j\omega t}d\omega \]

则非周期函数的傅里叶变换定义为

\[ F(\omega)=\int_{-\infty}^{+\infty}f(t)e^{-j\omega t}dt \]

我们可以发现 \(c_n=\frac{d\omega}{2\pi}F(\omega)\) ，即我们选取了信号幅值在频域中的分布密度 \(F(\omega)\) 来表示傅里叶变换，而不是相应频率的信号幅值大小 \(c_n\) 。因为如果选择后者，那傅里叶变换的函数值就都是无穷小了，这显然对我们没有任何帮助。

我们一般也用频率 \(f\) 来进行傅里叶变换：

\[ F(f)=\int_{-\infty}^{+\infty}f(t)e^{-j2\pi f t}dt \]

在数学上 \(f(t)\) 大多是在时域 \(t\) 上是连续的，但是由于计算机采集信号在时域中是离散的，所以实际应用中的 \(f(t)\) 都是其经采样处理后得到的 \(f_s(t)\) 。

同时，计算机也只能计算出有限个频率上对应的幅值密度，即 \(f\) 也是离散的。

\(\textit{DFT(Discrete Fourier Transform)}\) 也就是 \(t\) 和 \(f\) 都是离散的傅里叶变换。

一维离散傅里叶变换

采样(Sampling)

首先引入冲激函数（也叫 \(\textit{Dirac}\) 函数）的概念。

当 \(t \neq 0\) 时 \(\delta(t)=0\)； \(\int_{-\infty}^{+\infty}\delta(t)dt=1\)。

根据它的定义，我们可知 \(\int_{-\infty}^{+\infty}\delta(t-t_0)f(t)dt=f(t_0)\) 。这是 \(\textit{Dirac}\) 函数的重要性质，容易看出，它可以筛选出 \(f(t)\) 在 \(t_0\) 处的函数值，即起到采样的作用。

但是 \(\textit{Dirac}\) 函数一次只能选取一个函数值，所以我们将很多个采样点不同的 \(\textit{Dirac}\) 函数叠加起来，就可以实现时域上的采样了。这样叠加的函数被称为梳状函数，表达式为：

\(\delta_s(t)=\sum_{n=-\infty}^{\infty}\delta(t-nT_s)\) ，其中 \(T_s\) 为采样周期。

将时域上的连续信号与它相乘，即可得到 \(f_s=\sum_{n=-\infty}^{\infty}f(t)\delta(t-nT_s)\) 。

时域离散化计算

对于采样得到的 \(x_s(t)=\sum_{n=-\infty}^{\infty}x(t)\delta(t-nT_s)\) 进行傅里叶变换。

根据傅里叶变换的定义

\[ X(\omega)=\int_{-\infty}^{+\infty}x(t)e^{-j\omega t}dt \]

则 \(X_s(\omega)=\int_{-\infty}^{\infty}(\sum_{n=-\infty}^{\infty}x(t)\delta(t-nT_s))e^{-j\omega t}dt\)

交换积分与求和顺序，得到

\[ X_s(\omega)=\sum_{n=-\infty}^{\infty}\int_{-\infty}^{\infty}x(t)\delta(t-nT_s)e^{-jwt}dt \]

根据 \(\textit{Dirac}\) 函数的筛选特性， \(X_s(\omega)=\sum_{n=-\infty}^{\infty}x(nT_s)e^{-jwnT_s}\)

这样就完成了我们的时域离散化计算。