二维傅里叶变换(2D Fourier Transforms)可视化

发表于 2022-08-09 更新于 2022-08-16 分类于 Data Structures and Algorithms 阅读次数：本文字数： 6k 阅读时长 ≈ 5 分钟

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$ 都是离散的傅里叶变换。

阅读全文 »

[LeetCode][300. Longest Increasing Subsequence] 3 Approaches: Backtrack, DP, Binary Search

发表于 2022-08-08 分类于 Data Structures and Algorithms 阅读次数：本文字数： 2.3k 阅读时长 ≈ 2 分钟

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!

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]$ .

阅读全文 »

[LeetCode][377. Combination Sum IV] 2 Approaches: Backtrack and DP with Follow Up Analysis

发表于 2022-08-05 分类于 Data Structures and Algorithms 阅读次数：本文字数： 2k 阅读时长 ≈ 2 分钟

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

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(n^Sum(target))$
Space Complexity: $O(target)$

阅读全文 »

[LeetCode][858. Mirror Reflection] What If the Ray Not Reflected and Expand the Room with Image Explanation

发表于 2022-08-04 分类于 Data Structures and Algorithms 阅读次数：本文字数： 969 阅读时长 ≈ 1 分钟

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

阅读全文 »

[Leetcode][378. Kth Smallest Element in a Sorted Matrix] 3 Approaches: Sorting, Merge Sort, Binary Search

发表于 2022-08-02 分类于 Data Structures and Algorithms 阅读次数：本文字数： 1.8k 阅读时长 ≈ 2 分钟

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

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

Merge Sort

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)$
Space Complexity: $O(n)$

阅读全文 »

[Leetcode][62. Unique Paths] 3 Approaches: Dynamic Programming, Recursion, Math

发表于 2022-08-01 更新于 2022-08-02 分类于 Data Structures and Algorithms 阅读次数：本文字数： 2.3k 阅读时长 ≈ 2 分钟

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(i−1, j) + f(i, j−1)$ .

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)$
Space Complexity: $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.

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)$
Space Complexity: $O(mn)$

阅读全文 »

[LeetCode][399. Evaluate Division] 4 Approaches: BFS, DFS, Floyd, Union Find

发表于 2022-07-31 更新于 2022-08-05 分类于 Data Structures and Algorithms 阅读次数：本文字数： 2.4k 阅读时长 ≈ 2 分钟

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

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

Analysis

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

Floyd

Analysis

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

Union Find

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. 😉😃💗

[Leetcode][34. Find First and Last Position of Element in Sorted Array] Binary Search Twice

发表于 2022-07-25 更新于 2022-08-11 分类于 Data Structures and Algorithms 阅读次数：本文字数： 2.9k 阅读时长 ≈ 3 分钟

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 $\textit{target}$ . The time complexity is $O(n)$ .

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)$
Space Complexity: $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 $\textit{leftIdx}$ ) and “the first position greater than The position of target minus one” (recorded as $\textit{rightIdx}$ ).

In binary search, looking for $\textit{leftIdx}$ is to find the first index greater than or equal to target in the array, and looking for $\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 $\textit{target}$ may not exist in the array, we need to re-check the two indices we got $\textit{leftIdx}$ and $\textit{rightIdx}$ to see if they meet the conditions, if so It returns $[\textit{leftIdx}, \textit{rightIdx}]$ , if it does not match, it returns $[-1, -1]$ .

阅读全文 »

[Leetcode][240. Search a 2D Matrix II] 5 Approaches: BF, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis

发表于 2022-07-24 更新于 2022-08-02 分类于 Data Structures and Algorithms 阅读次数：本文字数： 5.8k 阅读时长 ≈ 5 分钟

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

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)$ .
Space Complexity: $O(1)$ .

Binary Search(Row)

阅读全文 »

[Leetcode] Problem Series of Jump Game

发表于 2022-07-10 更新于 2022-07-14 分类于 Data Structures and Algorithms 阅读次数：本文字数： 4.1k 阅读时长 ≈ 4 分钟

By Long Luo

This article is the solution Leetcode Jump Game Problems Series.

1. 55. Jump Game

55. Jump Game

Brute Force

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

Greedy

Jump to the farest postion.

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)$
Space Complexity: $O(1)$

2. 45. Jump Game II

45. Jump Game II

DP

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

Greedy

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.

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)$
Space Complexity: $O(1)$

阅读全文 »