By Long Luo
图中的顶点我们已经编好了号，那么我们需要储存的和图相关的信息，就只剩下点与点之间的连边了。
一个很直观的想法就是用一个二维数组来存图，下标代表点，值代表连边的情况。这就是所谓的矩阵存图法，也被称作为邻接矩阵存图法。
更具体地，我们一般使用 bool 数组来储存点与点之间的连边信息：
如果 con[i][j] 的值为 true ，表示点 i 与点 j 之间连了一条从 i 指向 j 的边。 如果 con[i][j] 的值为 false ，表示点 i 与点 j 之间没有连边。
以下图为例：
前面我们说过，矩阵存图的最大的劣势，就是在面对稀疏图时，有很多空间没有储存有效信息（对于一个图，我们往往更加关注哪些点之间有连边，而不关注哪些点之间没有连边），被浪费掉了。一个优化的思路是：我们不再考虑储存每一个点对之间的连边信息，而只考虑那些有连边的点对。这样我们就能够保证所储存下来的信息都会是有效的。
针对上述思路，对于一个有 nn 的点的图，我们可以利用 nn 个链表，第 ii 个链表里存着所有从 ii 直接连向的点。以下图为例：
By Long Luo
前几天看了一个介绍 核磁共振成像(MRI) 原理的视频：三维演示磁共振成像（MRI）原理 ，加上自己也曾做过 \(2\) 次核磁共振，一直很好奇其原理，所以花了点时间弄懂了核磁共振成像原理。
在这篇文章我们不详细介绍核磁共振成像原理，只关注其成像部分，也就是根据获取到的空间频率来还原图像，也就是二维傅里叶逆变换(\(\textit{2D Inverse Fourier Transforms}\))。
关于傅里叶变换及傅里叶逆变换，可以参考之前写过的一篇文章：傅里叶变换 。傅里叶变换本质上就是换基，推荐这篇文章：我理解的傅里叶变换 。
对于非周期函数，我们把它的周期看作无穷大。基频 \(\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\) 都是离散的傅里叶变换。
首先引入冲激函数（也叫 \(\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.
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
30class 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;
}
}
The equation:
\(dp[i] = \textit{max}(dp[j]) + 1, 0 \leq j < i and \textit{nums}[j] < \textit{nums}[i]\).
By Long Luo
This article is the solution 2 Approaches: Backtrack and DP with Follow Up Analysis of Problem 377. Combination Sum IV .
Here shows 2 Approaches to slove this problem: Backtrack and Dynamic Programming.
The Backtrack will be a complete search and its time complexity will be \(O(2^n)\).
Surely it will be 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
25class Solution {
int total = 0;
public int combinationSum4(int[] nums, int target) {
total = 0;
Arrays.sort(nums);
backtrack(nums, target);
return total;
}
private void backtrack(int[] nums, int remain) {
if (remain == 0) {
total++;
return;
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] > remain) {
break;
}
backtrack(nums, remain - nums[i]);
}
}
}
By Long Luo
This article is the solution 3 Approaches: BFS(Dijkstra), Binary Search, Union Find of Problem 858. Mirror Reflection .
What if we assume the Ray Not Reflected and Keeps Going?
Consider that there is a mirrored world behind the mirror, we can expand the room behind the mirror. The ray has not been reflected and keep going cross the room.
As the image below shows, we can easily know which receptor will the ray will meet first.