0%

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.

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
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(m2n2)O(m^2n^2).
  • Space Complexity: O(mn)O(mn).
阅读全文 »

By Long Luo

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

Intuition

  1. 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.

  2. BFS will try every possible path at the same time.

  3. 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.

阅读全文 »

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.

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

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
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)O(n).
  • Space Complexity: O(n)O(n).
阅读全文 »

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.

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
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((Mk)×k)O({M \choose k} \times k), MM is the size of combinations, M=9M = 9, the total combinations is (Mk)M \choose k.

  • Space Complexity: O(M+k)O(M + k), size of pathpath is kk, the recursion stack is O(M)O(M).

阅读全文 »

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 234234 for example, look at the tree:

Tree

Brute Froce(4 Loops)

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

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

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
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(4N)O(4^N)
  • Space Complexity: O(N)O(N)

Backtracking

For the first number, there are 33 options, and 33 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.

阅读全文 »

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.

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
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:

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

阅读全文 »

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 33 elements which is 132132 pattern, but the time complexity is O(n3)O(n^3), so it wouldn’t accepted as timeout.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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(n3)O(n^3).
  • Space Complexity: O(1)O(1).

BF O(n^2)

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

  1. Scan left from jj to 00, 0<=i<j0 <= i < j, whether there is num[i]<nums[j]num[i] < nums[j], update the mininum leftMinleftMin;

  2. Scan right from jj to the end, j+1<=k<lenj + 1 <= k < len, whether there is num[k]<nums[j]num[k] < nums[j], update the maxinum rightMaxrightMax;

  3. If exists and leftMin<rightMaxleftMin < rightMax, return truetrue.

阅读全文 »

By Long Luo

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

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

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

快速数论变换(NTT)

FFT\textit{FFT} 的本质是什么?

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

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

  • 单位复根

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

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

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

原根

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

FFT\textit{FFT} 中,我们总共用到了单位复根的这些性质:

  1. nn 个单位复根互不相同;
  2. ωnk=ω2n2k\omega_n^k=\omega_{2n}^{2k}
  3. ωnk=ωnk+n/2\omega_n^{k}=-\omega_n^{k+n/2}
  4. ωna×ωnb=ωna+b\omega_n^a\times\omega_n^b=\omega_n^{a+b}

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

nn 为大于 1122 的幂,pp 为素数且 n(p1)n \mid (p-1)ggpp 的一个原根。

我们设 gn=gp1ng_n=g^{\frac{p-1}{n}}

  1. gnn=gnp1n=gp1g_n^n=g^{n\cdot\frac{p-1}{n}}=g^{p-1}

  2. gnn2=gp12g_n^{\frac{n}{2}}=g^{\frac{p-1}{2}}

  3. ganak=gak(p1)an=gk(p1)n=gnkg_{an}^{ak}=g^{\frac{ak(p-1)}{an}}=g^{\frac{k(p-1)}{n}}=g_n^k

显然

  1. gnn1(modp)g_n^n \equiv 1 \pmod p

  2. gnn21(modp)g_n^{\frac{n}{2}} \equiv -1 \pmod p

  3. (gnk+n2)2=gn2k+ngn2k(modp)(g_n^{k+\frac{n}{2}})^2=g_n^{2k+n} \equiv g_n^{2k} \pmod p

证毕。

所以将 gnkg_n^kgnk+n2g_n^{k+\frac{n}2} 带入本质上和将 ωnk\omega_n^{k}ωnk+n2\omega_n^{k+\frac{n}{2}} 带入的操作无异。

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

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

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

这里 N1N^{-1}amn(modM)a^{-mn} \pmod M 为模意义下的乘法逆元。

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

阅读全文 »

By Long Luo

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

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

Cooley–Tukey FFT Algorithm

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

FFT 分治过程

FFT

具体操作流程可以分为 33 步:

  1. Divide:按照奇偶分为 22 个子问题。
  2. Conquer:递归处理 22 个子问题
  3. Combine:合并 22 个子问题。

蝴蝶操作

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

Butterfly Operations

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

阅读全文 »

By Long Luo

Leetcode 396. 旋转函数 题解。

方法一: 暴力法

思路与算法

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 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(N2)O(N^2),其中 NN 是数组 nums\textit{nums} 的长度。

  • 空间复杂度:O(1)O(1)

方法二: 动态规划

思路与算法:

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

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

F(1)=1×nums[0]+2×nums[1]++0×nums[n1]=F(0)+i=0n1nums[i]n×nums[n1]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)+i=0n1nums[i]n×nums[nk],0k<nF(k+1) = F(k) + \sum_{i=0}^{n-1}nums[i]-n \times nums[n-k], 0 \le k \lt n

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 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)O(1)

阅读全文 »