0%

By Long Luo

前言

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

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

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

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

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

cn=Δω2π+f(t)ejwtdtc_{n}=\frac{\Delta\omega}{2\pi}\int_{-\infty}^{+\infty} f(t)e^{-jwt}dt

我们会发现这里的 cnc_n 是趋于 00 的。

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

得到:

f(t)=+(Δω2π+f(t)ejwtdt)ejωt=+12π(+f(t)ejωtdt)ejωtdω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(ω)=+f(t)ejωtdtF(\omega)=\int_{-\infty}^{+\infty}f(t)e^{-j\omega t}dt

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

我们一般也用频率 ff 来进行傅里叶变换:

F(f)=+f(t)ej2πftdtF(f)=\int_{-\infty}^{+\infty}f(t)e^{-j2\pi f t}dt

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

同时,计算机也只能计算出有限个频率上对应的幅值密度,即 ff 也是离散的。

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

阅读全文 »

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 2n2^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(2n)O(2^n)
  • Space Complexity: O(n)O(n)

DP

The equation:

dp[i]=max(dp[j])+1,0j<iandnums[j]<nums[i]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.

Backtrack

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
class 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]);
}
}
}

Analysis

Time Complexity: O(nSum(target))O(n^Sum(target))
Space Complexity: O(target)O(target)

阅读全文 »

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.

858

阅读全文 »

By Long Luo

This article is the solution 3 Approaches: Sorting, Merge Sort, Binary Search of Problem 378. Kth Smallest Element in a Sorted Matrix.

Here shows 3 Approaches to slove this problem: Sorting, Merge Sort, Binary Search.

Sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int[] array = new int[n * n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
array[i * n + j] = matrix[i][j];
}
}

Arrays.sort(array);

return array[k - 1];
}

Analysis

  • Time Complexity: O(n2logn)O(n^2logn)
  • Space Complexity: O(n2)O(n^2)

Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;

PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);

for (int i = 0; i < n; i++) {
pq.offer(new int[]{matrix[i][0], i, 0});
}

for (int i = 0; i < k - 1; i++) {
int[] cur = pq.poll();

if (cur[2] != n - 1) {
pq.offer(new int[]{matrix[cur[1]][cur[2] + 1], cur[1], cur[2] + 1});
}
}

return pq.poll()[0];
}

Analysis

  • Time Complexity: O(klogn)O(klogn)
  • Space Complexity: O(n)O(n)
阅读全文 »

By Long Luo

This article is the solution 3 Approaches: DP, Recursion, Math of Problem 62. Unique Paths.

Here shows 3 Approaches to slove this problem: Dynamic Programming, Recursion, Math.

Dynamic Programming

The equation is: f(i,j)=f(i1,j)+f(i,j1)f(i, j) = f(i−1, j) + f(i, j−1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];

for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}

for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}

for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i][j - 1] + 1, dp[i][j - 1] + dp[i - 1][j]);
}
}

return dp[m - 1][n - 1];
}

Analysis

  • Time Complexity: O(mn)O(mn)
  • Space Complexity: O(mn)O(mn)

Recursion

The DFS is top-down dynamic programming with memoization. If we do ordinary DFS without proper memoization, it will have a TLE error.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int uniquePaths(int m, int n) {
return dfs(new HashMap<Pair, Integer>(), 0, 0, m, n);
}

private static int dfs(Map<Pair, Integer> cache, int r, int c, int rows, int cols) {
Pair p = new Pair(r, c);

if (cache.containsKey(p)) {
return cache.get(p);
}

if (r == rows - 1 || c == cols - 1) {
return 1;
}

cache.put(p, dfs(cache, r + 1, c, rows, cols) + dfs(cache, r, c + 1, rows, cols));
return cache.get(p);
}

Analysis

  • Time Complexity: O(mn)O(mn)
  • Space Complexity: O(mn)O(mn)
阅读全文 »

By Long Luo

This article is the solution 4 Approaches: BFS, DFS, Floyd, Union Find of Problem 399. Evaluate Division.

Here shows 4 Approaches to slove this problem: BFS, DFS, Floyd, Union Find.

BFS

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
int len = equations.size();
Map<String, Integer> varMap = new HashMap<>();
int varCnt = 0;
for (int i = 0; i < len; i++) {
if (!varMap.containsKey(equations.get(i).get(0))) {
varMap.put(equations.get(i).get(0), varCnt++);
}
if (!varMap.containsKey(equations.get(i).get(1))) {
varMap.put(equations.get(i).get(1), varCnt++);
}
}

List<Pair>[] edges = new List[varCnt];
for (int i = 0; i < varCnt; i++) {
edges[i] = new ArrayList<>();
}

for (int i = 0; i < len; i++) {
int va = varMap.get(equations.get(i).get(0));
int vb = varMap.get(equations.get(i).get(1));
edges[va].add(new Pair(vb, values[i]));
edges[vb].add(new Pair(va, 1.0 / values[i]));
}

int queriesCnt = queries.size();
double[] ans = new double[queriesCnt];
for (int i = 0; i < queriesCnt; i++) {
List<String> query = queries.get(i);
double result = -1.0;
if (varMap.containsKey(query.get(0)) && varMap.containsKey(query.get(1))) {
int idxA = varMap.get(query.get(0));
int idxB = varMap.get(query.get(1));
if (idxA == idxB) {
result = 1.0;
} else {
Queue<Integer> points = new LinkedList<>();
points.offer(idxA);
double[] ratios = new double[varCnt];
Arrays.fill(ratios, -1.0);
ratios[idxA] = 1.0;
while (!points.isEmpty() && ratios[idxB] < 0) {
int cur = points.poll();
for (Pair pair : edges[cur]) {
int y = pair.index;
double value = pair.value;
if (ratios[y] < 0) {
ratios[y] = ratios[cur] * value;
points.offer(y);
}
}
}

result = ratios[idxB];
}
}

ans[i] = result;
}

return ans;
}

class Pair {
int index;
double value;

public Pair(int index, double value) {
this.index = index;
this.value = value;
}
}
}

Analysis

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

DFS

1

Analysis

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

Floyd

1

Analysis

  • Time Complexity: O(nlog(r-l)
  • Space Complexity: O(1)

Union Find

1

Analysis

  • Time Complexity: O(nlog(r-l)
  • Space Complexity: O(1)

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗

By Long Luo

This article is the solution 3 Approaches: DP, Recursion, Math of Problem 34. Find First and Last Position of Element in Sorted Array.

Here shows 2 Approaches to slove this problem: Brute Force and Binary Search.

Brute Force

The easiest method is scan the array from left to right. Use two variables to record the index of the first and last element target\textit{target}. The time complexity is O(n)O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int[] searchRange(int[] nums, int target) {
int[] ans = {-1, -1};
int len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] == target && ans[0] == -1) {
ans[0] = i;
} else if (nums[i] > target && ans[0] >= 0) {
ans[1] = i - 1;
return ans;
}
}

if (ans[0] >= 0) {
ans[1] = len - 1;
}

return ans;
}

Analysis

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

Binary Search

Since the array is sorted in ascending order, so we can binary search to speed up the search.

Considering the start and end positions of target, in fact, what we are looking for is “the first position in the array equal to target” (recorded as leftIdx\textit{leftIdx} ) and “the first position greater than The position of target minus one” (recorded as rightIdx\textit{rightIdx} ).

In binary search, looking for leftIdx\textit{leftIdx} is to find the first index greater than or equal to target in the array, and looking for rightIdx\textit{rightIdx} is to find the first index greater than target in the array index of target, then decrement the index by one.

Finally, since target\textit{target} may not exist in the array, we need to re-check the two indices we got leftIdx\textit{leftIdx} and rightIdx\textit{rightIdx} to see if they meet the conditions, if so It returns [leftIdx,rightIdx][\textit{leftIdx}, \textit{rightIdx}], if it does not match, it returns [1,1][-1, -1].

阅读全文 »

By Long Luo

This article is the solution 5 Approaches: BF, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis of Problem 240. Search a 2D Matrix II.

The similar question and solution is 74. Search a 2D Matrix.

Here shows 5 Approaches to slove this problem: Brute Force, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis.

Brute Force

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 boolean searchMatrix_bf(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}

int row = matrix.length;
int col = matrix[0].length;

if (matrix[0][0] > target || matrix[row - 1][col - 1] < target) {
return false;
}

for (int i = 0; i < row; i++) {
if (matrix[i][col - 1] < target) {
continue;
}

for (int j = 0; j < col; j++) {
if (matrix[i][j] == target) {
return true;
}
}
}

return false;
}

Analysis

  • Time Complexity: O(mn)O(mn).
  • Space Complexity: O(1)O(1).

Binary Search(Row)

阅读全文 »

By Long Luo

This article is the solution Leetcode Jump Game Problems Series.

1. 55. Jump Game

55. Jump Game

Brute Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean canJump(int[] nums) {
int len = nums.length;
boolean[] visited = new boolean[len];
visited[0] = true;
for (int i = 0; i < len; i++) {
int steps = nums[i];
if (visited[i] && steps > 0) {
for (int j = 1; j <= steps && i + j < len; j++) {
visited[i + j] = true;
}
}
}

return visited[len - 1];
}

Analysis

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

Greedy

Jump to the farest postion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean canJump(int[] nums) {
int len = nums.length;
int maxIdx = 0;
for (int i = 0; i < len; i++) {
int steps = nums[i];
if (maxIdx >= i) {
maxIdx = Math.max(maxIdx, i + steps);
if (maxIdx >= len - 1) {
return true;
}
}
}

return false;
}

Analysis

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

2. 45. Jump Game II

45. Jump Game II

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int jump_dp(int[] nums) {
int len = nums.length;
if (len <= 1) {
return 0;
}

int[] dp = new int[len];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
int minStep = Integer.MAX_VALUE;
for (int i = 0; i < len; i++) {
int num = nums[i];
for (int j = 1; j <= num && i + j < len; j++) {
dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
if (i + j >= len - 1) {
minStep = Math.min(minStep, dp[i] + 1);
return minStep;
}
}
}

return minStep;
}

Analysis

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

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int jump(int[] nums) {
int maxPosition = 0;
int end = 0;
int steps = 0;
for (int i = 0; i < nums.length - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
steps++;
}
}

return steps;
}

Think reverse, from destination to origin position.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int jump(int[] nums) {
int ans = 0;
int position = nums.length - 1;
while (position > 0) {
for (int i = 0; i < position; i++) {
if (i + nums[i] >= position) {
ans++;
position = i;
break;
}
}
}

return ans;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(1)O(1)
阅读全文 »