Long Luo's Life Notes

By Long Luo

This article is the solution 4 Approaches: BF 4 Loops, Backtracking, BFS, Queue with Image Explanation 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:

Brute Froce(4 Loops)

Since the \(\textit{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.

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

This article is the solution 2 Approaches: DFS and Iteration(Using Stack) 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:
  • \(\texttt{NestedIterator}\): \(O(n)\).
  • \(\texttt{next()}\): \(O(1)\)
  • \(\texttt{hasNext()}\): \(O(1)\)
• Space Complexity: \(O(n)\).

By Long Luo

This article is the solution 4 Approaches: BF O(n^3), BF O(n^2), TreeMap, Monotonic Stack of Problem 456. 132 Pattern .

Here are 4 approaches to solve this problem in Java: BF \(O(n^3)\) , BF \(O(n^2)\) , TreeMap, Monotonic Stack.

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 TLE!

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(n^3)\).
• Space Complexity: \(O(1)\).

BF O(n^2)

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

1. Scan left from \(j\) to \(0\), \(0 \le i \lt j\), whether there is \(\textit{nums}[i] < \textit{nums}[j]\), update the mininum \(\textit{leftMin}\);

2. Scan right from \(j\) to the end, \(j + 1 \le k \lt len\), whether there is \(\textit{nums}[k] < \textit{nums}[j]\), update the maxinum \(\textit{rightMax}\);

3. If exists and \(\textit{leftMin} < \textit{rightMax}\) , return true.

By Long Luo

The Solutions of LeetCode Top Interview Questions | 精选 TOP 面试题

By Long Luo

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

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

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

快速数论变换(NTT)

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

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

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

• 是单位复根。

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

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

所以快速数论变换 \(\textit{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\) 的一个原根。

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

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

证毕。

所以将 \(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\) 的较高幂次的倍数。