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}\)

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

By Long Luo

This article is the solution 3 Approaches: Backtrack, DP, Binary Search of Problem 300. Longest Increasing Subsequence.

Here shows 3 Approaches to slove this problem: Backtrack, DP, Binary Search.

Backtrack

The Brute Force approach, there are \(2^n\) subsequences, use Backtrack to find the answer.

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

class Solution {
    int minCount = Integer.MAX_VALUE;

    public int coinChange(int[] coins, int amount) {
        if (amount <= 0) {
            return 0;
        }

        minCount = Integer.MAX_VALUE;
        dfs(coins, amount, 0);
        return minCount == Integer.MAX_VALUE ? -1 : minCount;
    }

    private int dfs(int[] coins, int remain, int count) {
        if (remain < 0) {
            return -1;
        }

        if (remain == 0) {
            minCount = Math.min(minCount, count);
            return count;
        }
        
        for (int x : coins) {
            dfs(coins, remain - x, count + 1);
        }

        return -1;
    }
}

Analysis

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

DP

The equation:

\(dp[i] = \textit{max}(dp[j]) + 1, 0 \leq j < i and \textit{nums}[j] < \textit{nums}[i]\).