0%

By Long Luo

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.

## Analysis

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

By Long Luo

# 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

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.

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

## Analysis

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

By Long Luo

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.

## 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)$.

By Long Luo

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

# Intuition

Take the $234$ for example, look at the 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.

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

By Long Luo

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.

## Analysis

• Time Complexity:

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

By Long Luo

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.

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

1. Scan left from $j$ to $0$, $0 <= i < j$, whether there is $num[i] < nums[j]$, update the mininum $leftMin$;

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

3. If exists and $leftMin < rightMax$, return $true$.

By Long Luo

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

# 快速数论变换(NTT)

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

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

• 单位复根

# 原根

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

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

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

1. $g_n^n=g^{n\cdot\frac{p-1}{n}}=g^{p-1}$

2. $g_n^{\frac{n}{2}}=g^{\frac{p-1}{2}}$

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

1. $g_n^n \equiv 1 \pmod p$

2. $g_n^{\frac{n}{2}} \equiv -1 \pmod p$

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

$\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$

By Long Luo

# Cooley–Tukey FFT Algorithm

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

## FFT 分治过程

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

By Long Luo

# 方法一： 暴力法

## 复杂度分析：

• 时间复杂度：$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)$，并求出最大值。