[LeetCode][329. Longest Increasing Path in a Matrix] 4 Approaches: BFS, Memory + DFS, DP, Topological Sorting

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

By Long Luo

This article is the solution of Problem 329. Longest Increasing Path in a Matrix.

Here shows 4 Approaches to slove this problem: BFS, Memory + DFS, DP, Topological Sorting.

BFS

The simplest method that comes to my mind is BFS. We start search from each node, spread out like water, to see how far it can flood, and record the maximum flood path length of all nodes.

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int row = matrix.length;
        int col = matrix[0].length;
        if (row == 1 && col == 1) {
            return 1;
        }

        int max = 1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                max = Math.max(max, bfs(matrix, i, j));
            }
        }

        return max;
    }

    public int bfs(int[][] matrix, int x, int y) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

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

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});

        while (!queue.isEmpty()) {
            int size = queue.size();
            ans++;

            for (int i = 0; i < size; i++) {
                int[] curPos = queue.poll();

                for (int[] dir : dirs) {
                    int nextX = curPos[0] + dir[0];
                    int nextY = curPos[1] + dir[1];

                    if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) {
                        continue;
                    }

                    if (matrix[nextX][nextY] <= matrix[curPos[0]][curPos[1]]) {
                        continue;
                    }

                    queue.offer(new int[]{nextX, nextY});
                }
            }
        }

        return ans;
    }
}

Analysis

Time Complexity: $O(m^2n^2)$ .
Space Complexity: $O(mn)$ .

阅读全文 »

[LeetCode][1091. Shortest Path in Binary Matrix] Why Use BFS? Search Every Possible Path vs Search A Possible Path

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

By Long Luo

This article is the solution of Problem 1091. Shortest Path in Binary Matrix.

Intuition

If we want to find a possible path, DFS will be more efficient. Because DFS will return a possible path if found, while it may not the shortest path.
BFS will try every possible path at the same time.
If we want to find the shortest of all possible paths, BFS is more efficient. It’s impossible for DFS to determine which is the shortest before trying all possible paths.

BFS

Use BFS to Level Traversal.

阅读全文 »

[LeetCode][117. Populating Next Right Pointers in Each Node II] 3 Approaches: BFS, BFS + LinkedList, Recursion

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

By Long Luo

This article is the solution of Problem 117. Populating Next Right Pointers in Each Node II.

Here shows 3 Approaches to slove this problem: BFS, BFS + LinkedList, Recursion.

BFS

Use BFS to level traversal, a List to store the Nodes of each level.

public Node connect_bfs(Node root) {
    if (root == null) {
        return root;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Node> levelNodes = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            Node curNode = queue.poll();
            levelNodes.add(curNode);
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }

        for (int i = 0; i < levelNodes.size() - 1; i++) {
            Node node = levelNodes.get(i);
            node.next = levelNodes.get(i + 1);
        }
    }

    return root;
}

In fact, we just need a Node to store the Previous Node.

public Node connect_bfs(Node root) {
    if (root == null) {
        return root;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelCount = queue.size();
        Node prev = null;
        for (int i = 0; i < levelCount; i++) {
            Node curNode = queue.poll();

            if (prev != null) {
                prev.next = curNode;
            }

            prev = curNode;

            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
    }

    return root;
}

Analysis

Time Complexity: $O(n)$ .
Space Complexity: $O(n)$ .

阅读全文 »

[LeetCode][216. Combination Sum III] 2 Approaches: Backtracking and Bit Mask

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

By Long Luo

This article is the solution of Problem 216. Combination Sum III.

Here shows 2 Approaches to slove this problem: Backtracking and Bit Mask.

Backtracking

A very easy backtracking solution. Just refer to 17. Letter Combinations of a Phone Number.

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> ans = new ArrayList<>();

    // corner cases
    if (k <= 0 || n <= 0 || k > n) {
        return ans;
    }

    // The upper bound of n: [9, 8, ... , (9 - k + 1)], sum is (19 - k) * k / 2
    if (n > (19 - k) * k / 2) {
        return ans;
    }

    backtrack(ans, new ArrayList<>(), 1, k, n);
    return ans;
}

public void backtrack(List<List<Integer>> res, List<Integer> path, int start, int k, int target) {
    if (k < 0 || target < 0) {
        return;
    }

    if (k == 0 && target == 0) {
        res.add(new ArrayList<>(path));
        return;
    }

    for (int i = start; i <= 9; i++) {
        // trim 
        if (i > target) {
            break;
        }
			
        // trim
        if (target - i == 0 && k > 1) {
            break;
        }

        path.add(i);
        backtrack(res, path, i + 1, k - 1, target - i);
        path.remove(path.size() - 1);
    }
}

Analysis

Time Complexity: $O({M \choose k} \times k)$ , $M$ is the size of combinations, $M = 9$ , the total combinations is $M \choose k$ .
Space Complexity: $O(M + k)$ , size of $path$ is $k$ , the recursion stack is $O(M)$ .

阅读全文 »

[LeetCode][17. Letter Combinations of a Phone Number] 4 Approaches: BF 4 Loops, Backtracking, BFS, Queue with Image Explaination

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

By Long Luo

This article is the solution of Problem 17. Letter Combinations of a Phone Number.

Here shows 4 Approaches to slove this problem: Brute Force, Backtracking, BFS and Queue.

Intuition

Take the $234$ for example, look at the tree:

Tree

Brute Froce(4 Loops)

Since the $digits.length <= 4$ , we can just use the brute force approach $4$ Loops to search all the possible combinations.

The total states is $A(n,n)=A(4,4)=4!$ . We have to enumerate all these states to get the answer.

public static List<String> letterCombinations_4Loops(String digits) {
    List<String> ans = new ArrayList<>();
    if (digits == null || digits.length() == 0) {
        return ans;
    }

    String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    int len = digits.length();
    int[] digitsArr = new int[len];
    for (int i = 0; i < len; i++) {
        digitsArr[i] = digits.charAt(i) - '0';
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++) {
        sb.append("a");
    }

    for (int i = 0; i < letters[digitsArr[0] - 2].length(); i++) {
        sb.replace(0, 1, letters[digitsArr[0] - 2].charAt(i) + "");
        if (len == 1) {
            ans.add(sb.substring(0, 1));
        }

        for (int j = 0; len >= 2 && j < letters[digitsArr[1] - 2].length(); j++) {
            sb.replace(1, 2, letters[digitsArr[1] - 2].charAt(j) + "");
            if (len == 2) {
                ans.add(sb.toString());
            }

            for (int k = 0; len >= 3 && k < letters[digitsArr[2] - 2].length(); k++) {
                sb.replace(2, 3, letters[digitsArr[2] - 2].charAt(k) + "");
                if (len == 3) {
                    ans.add(sb.toString());
                }

                for (int l = 0; len >= 4 && l < letters[digitsArr[3] - 2].length(); l++) {
                    sb.replace(3, 4, letters[digitsArr[3] - 2].charAt(l) + "");
                    ans.add(sb.toString());
                }
            }
        }
    }

    return ans;
}

Analysis

Time Complexity: $O(4^N)$
Space Complexity: $O(N)$

Backtracking

For the first number, there are $3$ options, and $3$ options for the second number and so on.

The combinations from the first to the last will expand into a recursive tree.

When the index reaches the end of digits, we get a combination, and add it to the result, end the current recursion. Finally we will get all the combinations.

阅读全文 »

[LeetCode][341. Flatten Nested List Iterator] 2 Approaches: DFS, Iteration(Using Stack)

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

By Long Luo

This article is the solution of Problem 341. Flatten Nested List Iterator.

Here are 2 approaches to solve this problem in Java, DFS and Iteration approach.

DFS

We can store all the integers in an array, just traversing the array.

public class NestedIterator implements Iterator<Integer> {
    List<Integer> numList;
    int idx;

    public NestedIterator(List<NestedInteger> nestedList) {
        numList = new ArrayList<>();
        idx = 0;
        dfs(nestedList);
    }

    private void dfs(List<NestedInteger> nestedList) {
        if (nestedList == null) {
            return;
        }

        for (int i = idx; i < nestedList.size(); i++) {
            NestedInteger nested = nestedList.get(i);
            if (nested.isInteger()) {
                numList.add(nested.getInteger());
            } else {
                dfs(nested.getList());
            }
        }
    }

    @Override
    public Integer next() {
        return numList.get(idx++);
    }

    @Override
    public boolean hasNext() {
        if (idx < numList.size()) {
            return true;
        }

        return false;
    }
}

Analysis

Time Complexity:
- $\texttt{NestedIterator}$ : $O(n)$ .
- $\texttt{next()}$ : $O(1)$
- $\texttt{hasNext()}$ : $O(1)$
Space Complexity: $O(n)$ .

阅读全文 »

[LeetCode][456. 132 Pattern] 6 Approaches: BF O(n^3), BF O(n^2), TreeMap, Monotonic Stack

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

By Long Luo

This article is the solution of Problem 456. 132 Pattern.

Here are 6 approaches to solve this problem in Java.

BF O(n^3)

It’s easy to use 3 loops to find $3$ elements which is $132$ pattern, but the time complexity is $O(n^3)$ , so it wouldn’t accepted as timeout.

public boolean find132pattern_bf(int[] nums) {
    int len = nums.length;
    if (len < 3) {
        return false;
    }

    for (int i = 0; i < len - 2; i++) {
        for (int j = i + 1; j < len - 1; j++) {
            for (int k = j + 1; k < len; k++) {
                if (nums[i] < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
    }

    return false;
}

Analysis

Time Complexity: $O(n^3)$ .
Space Complexity: $O(1)$ .

BF O(n^2)

Noticed that $nums[j]$ is the peak of the $3$ elements, suppose the current element is $nums[j]$ , we have to find the element $nums[k]$ that is smaller than $nums[j]$ after $j$ , and the element $nums[i]$ that is smaller than $nums[k]$ before $j$ .

Scan left from $j$ to $0$ , $0 <= i < j$ , whether there is $num[i] < nums[j]$ , update the mininum $leftMin$ ;
Scan right from $j$ to the end, $j + 1 <= k < len$ , whether there is $num[k] < nums[j]$ , update the maxinum $rightMax$ ;
If exists and $leftMin < rightMax$ , return $true$ .

阅读全文 »

快速数论变换(Number Theoretic Transform)

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

By Long Luo

之前的文章快速傅里叶变换(FFT)算法和快速傅里叶变换(FFT)算法的实现及优化详细介绍了 $\textit{FFT}$ 的具体实现及其实现。

$\textit{FFT}$ 优点很多，但缺点也很明显。例如单位复根的实部和虚部分别是一个正弦及余弦函数，有大量浮点数计算，计算量很大，而且浮点数运算产生的误差会比较大。

如果我们操作的对象都是整数的话，其实数学家已经发现了一个更好的方法：快速数论变换 $\textit{(Number Theoretic Transform)}$ ^[1]。

快速数论变换(NTT)

$\textit{FFT}$ 的本质是什么？

将卷积操作变成了乘法操作。

是什么让 $\textit{FFT}$ 做到了 $O(nlogn)$ 的复杂度？

是单位复根。

那有没有什么其他的东西也拥有单位根的这些性质呢？

答案当然是有的，原根^[2]就具有和单位根一样的性质。

所以快速数论变换 $\textit{NTT}$ 就是以数论为基础的具有循环卷积性质的，用有限域上的单位根来取代复平面上的单位根的 $\textit{FFT}$ 。

原根

仿照单位复数根的形式，也将原根的取值看成一个圆，不过这个圆上只有有限个点，每个点表达的是模数的剩余系中的值。

在 $\textit{FFT}$ 中，我们总共用到了单位复根的这些性质：

$n$ 个单位复根互不相同；
$\omega_n^k=\omega_{2n}^{2k}$ ；
$\omega_n^{k}=-\omega_n^{k+n/2}$ ；
$\omega_n^a\times\omega_n^b=\omega_n^{a+b}$ 。

我们发现原根具有和单位复根一样的性质，简单证明^[3]：

令 $n$ 为大于 $1$ 的 $2$ 的幂， $p$ 为素数且 $n \mid (p-1)$ ， $g$ 为 $p$ 的一个原根。

我们设 $g_n=g^{\frac{p-1}{n}}$ ：

$g_n^n=g^{n\cdot\frac{p-1}{n}}=g^{p-1}$
$g_n^{\frac{n}{2}}=g^{\frac{p-1}{2}}$
$g_{an}^{ak}=g^{\frac{ak(p-1)}{an}}=g^{\frac{k(p-1)}{n}}=g_n^k$

显然

$g_n^n \equiv 1 \pmod p$
$g_n^{\frac{n}{2}} \equiv -1 \pmod p$
$(g_n^{k+\frac{n}{2}})^2=g_n^{2k+n} \equiv g_n^{2k} \pmod p$

证毕。

所以将 $g_n^k$ 和 $g_n^{k+\frac{n}2}$ 带入本质上和将 $\omega_n^{k}$ 和 $\omega_n^{k+\frac{n}{2}}$ 带入的操作无异。

利用Vandermonde矩阵性质，类似 $\textit{NTT}$ 那样，我们可以从 $\textit{NTT}$ 变换得到逆变换 $\textit{INTT}$ 变换，设 $x(n)$ 为整数序列，则有：

$\textit{NTT}$ : $X(m) = \sum\limits_{i=0}^{N}x(n)a^{mn} \pmod M$

$\textit{INTT}$ : $X(m) = N^{-1}\sum\limits_{i=0}^{N}x(n)a^{-mn} \pmod M$

这里 $N^{-1}$ ， $a^{-mn} \pmod M$ 为模意义下的乘法逆元。

当然， $\textit{NTT}$ 也是有自己的缺点的：比如不能够处理小数的情况，以及不能够处理没有模数的情况。对于模数的选取也有一定的要求，首先是必须要有原根，其次是必须要是 $2$ 的较高幂次的倍数。

阅读全文 »

快速傅里叶变换(FFT)算法的实现及优化

发表于 2022-04-29 更新于 2022-05-19 分类于 Data Structures and Algorithms 阅读次数：本文字数： 8.2k 阅读时长 ≈ 7 分钟

By Long Luo

之前的文章快速傅里叶变换(FFT)算法详细介绍了 $\textit{FFT}$ 的具体实现，也实现了分治版的 $\textit{FFT}$ 。

分治版 $\textit{FFT}$ 代码很容易理解，但递归会消耗 $O(logn)$ 的栈空间，同时代码实现中还有很多优化空间，这篇文章我们就来优化 $\textit{FFT}$ 下的实现。

Cooley–Tukey FFT Algorithm

$\textit{Cooley–Tukey FFT Algorithm}$ ^[1]通过使用分治算法^[2]实现将复杂问题简单化。

FFT 分治过程

FFT

具体操作流程可以分为 $3$ 步：

Divide：按照奇偶分为 $2$ 个子问题。
Conquer：递归处理 $2$ 个子问题
Combine：合并 $2$ 个子问题。

蝴蝶操作

分治的前 $2$ 步之前已经详细讲述过了，第 $3$ 步合并操作是通过**蝴蝶操作(Butterfly Operations)**来实现的，其示意图如下所示：

Butterfly Operations

蝴蝶操作可能会让人看了一头雾水，不过没关系，我们一步一步来，彻底弄懂她！

阅读全文 »

[Leetcode][396. 旋转函数] 3种方法：暴力法，动态规划，前缀和 + 滑动窗口

发表于 2022-04-22 更新于 2022-05-17 分类于 Data Structures and Algorithms 阅读次数：本文字数： 3.7k 阅读时长 ≈ 3 分钟

By Long Luo

Leetcode 396. 旋转函数题解。

方法一：暴力法

思路与算法

很容易想到的方法是遍历，使用 $2$ 个循环，很明显最多只能有 $len$ 次旋转，因为对称性，所以数组下标可能会 $>= len$ ，所以要取余 $(i+j) \mod len$ 。

每次旋转更新最大值，时间复杂度为 $O(N^2)$ 。

// BF time: O(n^2) space: O(1)
   public int maxRotateFunction(int[] nums) {
       int len = nums.length;
       if (len <= 1) {
           return 0;
       }

       int ans = Integer.MIN_VALUE;
       for (int i = 0; i < len; i++) {
           int sum = 0;
           for (int j = 0; j < len; j++) {
               sum += j * nums[(i + j) % len];
           }

           ans = Math.max(ans, sum);
       }

       return ans;
   }

复杂度分析：

时间复杂度： $O(N^2)$ ，其中 $N$ 是数组 $\textit{nums}$ 的长度。
空间复杂度： $O(1)$ 。

方法二：动态规划

思路与算法：

方法一会超时，其实观察旋转数组的变化：

F(0) = 0 \times nums[0] + 1 \times nums[1] + \ldots + (n-1) \times nums[n-1]

F(1) = 1 \times nums[0] + 2 \times nums[1] + \ldots + 0 \times nums[n-1] = F(0) + \sum_{i=0}^{n-1}nums[i] - n \times nums[n-1]

我们很容易发现相邻旋转的递推关系：

F(k+1) = F(k) + \sum_{i=0}^{n-1}nums[i]-n \times nums[n-k], 0 \le k \lt n

从 $F(0)$ 出发，迭代计算出不同的 $F(k)$ ，并求出最大值。

很容易使用DP写出如下代码：

// DP time: O(n) space: O(n)
public int maxRotateFunction_dp(int[] nums) {
    int len = nums.length;
    if (len <= 1) {
        return 0;
    }

    int[] dp = new int[len];
    int sum = 0;
    for (int i = 0; i < len; i++) {
        dp[0] += i * nums[i];
        sum += nums[i];
    }

    int ans = dp[0];
    for (int i = 1; i < len; i++) {
        dp[i] = dp[i - 1] + sum - len * nums[(len - i) % len];
        ans = Math.max(ans, dp[i]);
    }

    return ans;
}

观察上述代码，我们发现dp[]数组只是记录数值，实际上可以将空间复杂度优化到 $O(1)$ 。

阅读全文 »

BFS

Analysis

Intuition

BFS

BFS

Analysis

Backtracking

Analysis

Intuition

Brute Froce(4 Loops)

Analysis

Backtracking

DFS

Analysis

BF O(n^3)

Analysis

BF O(n^2)

快速数论变换(NTT)

原根

Cooley–Tukey FFT Algorithm

FFT 分治过程

蝴蝶操作

方法一： 暴力法

复杂度分析：

方法二： 动态规划

方法一：暴力法

方法二：动态规划