By Long Luo

This article is the solution 2 Approaches: Brute Force and Two Pointers with Image Explanation of Problem 11. Container With Most Water .

Here shows 2 Approaches to slove this problem: Brute Force and Two Pointers.

Intuition

Suppose two pointers \(i\), \(j\), the heights of the vertical lines are \(h[i]\), \(h[j]\), and the area in this state is \(S(i, j)\).

As we all known, the container is determined by the short line, the area formula can be easily obtained:

\[ S(i, j) = min(h[i], h[j]) \times (j - i) \]

Brute Froce

It’s easy to use the brute force approach, the total states is \(C(n, 2)= n \times (n - 1) / 2\), we have to enumerate all these states to get the max area.

The time complexity is \(O(n^2)\), exceed the time limit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// BF time: O(n^2) space: O(1)
// TimeOut
public static int maxArea_bf(int[] height) {
    int len = height.length;
    int max = 0;
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            int area = Math.min(height[i], height[j]) * (j - i);
            max = Math.max(max, area);
        }
    }

    return max;
}

Analysis

• Time Complexity: \(O(n^2)\)
• Space Complexity: \(O(1)\)

By Long Luo

This article is the solution 3 Approaches: Swapping Values and Swapping Nodes with Image Explanation of Problem 1721. Swapping Nodes in a Linked List .

Here shows 3 Approaches to slove this problem: ArrayList and Two Pointers.

Intuition

Since the \(\texttt{ListNode}\) only contain values, we can just just swap the values of two nodes. It’s very easy. All we need to do is to find these two nodes and swap their values.

If we swap nodes, it will be more difficult than swap values.

ArrayList(Swapping Values)

We can use an \(\texttt{ArrayList}\) to record all the nodes of the linked list. We can just swap the values of two nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

  // BF List time: O(n) space: O(n)
  public static ListNode swapNodes_bf_list(ListNode head, int k) {
      ListNode pNode = head;
      List<ListNode> nodeList = new ArrayList<>();
// store these nodes.
      while (pNode != null) {
          nodeList.add(pNode);
          pNode = pNode.next;
      }

// swap their values.
      int len = nodeList.size();
      int temp = nodeList.get(k - 1).val;
      nodeList.get(k - 1).val = nodeList.get(len - k).val;
      nodeList.get(len - k).val = temp;

      return head;
  }

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)

By Long Luo

This article is the solution Two Pointers Solution with Detailed Explanation of Problem 31. Next Permutation.

Intuition

• How to make a number larger?

Pick a larger number from the lower digit and swap it with the higher digit smaller number.

• How to find the permutation which is just larger than the given number?

The increase should be as small as possible.

Two Pointers

Take a example, \([3,2,1]\) which is decreasing order, there is no next permutation, it is already stable and cannot get larger.

Like \([1,5,2,4,3,2]\), how can it be just larger than the given number?

1. Scanning from right to left, find the first number which is smaller than the right digit, and swap it to the lower digit;
   • For example, \(1 5 (2) 4 3 2\), the \(2\) in the middle is the found one.
2. Scanning from right to left, searching for the first number which is larger than it, and swap them.
   • For example, \(1 5 (2) 4 (3) 2\), after swap: \(1 5 (3) 4 (2) 2\).

However, it’s not over yet!

The magnitude of the increase can be made smaller, the \(3rd\) digit from right has become slightly larger, and the last three can be made smaller.

The last three digits are definitely decreasing, and they are flipped to become \([1,5,3,2,2,4]\), which is what is required.

By Long Luo

之前的文章 傅里叶变换(Fourier Transform) 详细介绍了傅里叶变换 \((\textit{Fourier Transform})\) 是什么和做什么，相信你已经感受到了傅里叶变换的强大之处。

但理论要联系实际，今天我们就来学习 快速傅里叶变换 \((\textit{Fast Fourier Transform, FFT})\) ¹ 的实际运用：多项式乘法。

快速傅里叶变换(Fast Fourier Transform, FFT)

快速傅里叶变换 \((\textit{Fast Fourier Transform, FFT})\) ² 是一种可在 \(O(nlogn)\) 时间内完成的 离散傅里叶变换³ \((\textit{Discrete Fourier transform, DFT})\) 算法。

FFT可以做什么？

傅里叶变换 \((\textit{Fourier Transform})\) 本质上是信号与三角函数进行卷积运算，而快速傅里叶变换 \((\textit{FFT})\) 就是提高卷积的计算效率，时间复杂度从 \(O(n^2)\) 降低到 \(O(n \log n)\)。

\(\textit{FFT}\) 在算法中的运用主要是用来加速多项式乘法或大数乘法。

多项式乘法

正如之前的文章 卷积(Convolution) 所说，多项式乘法也是一种卷积运算。

在计算中，泰勒级数⁴ 可以使用多项式函数来逼近一个函数，所以计算中多项式乘法非常重要。

大数乘法

超大数字乘法，可以参考 超大数字的四则运算是如何实现的呢？ 。朴素的算法就是列竖式做乘法，算法时间复杂度为 \(O(n^2)\) ，如果数字太大的话，效率也不够高，如果应用 \((\textit{FFT})\) 则可以使算法时间复杂度降至 \(O(n \log n)\)。

不妨设十进制数字 \(num = 123456789\) ，很容易知道：

\[ 123456789 = 1 \times 10^8 + 2 \times 10^7 + 3 \times 10^6 + 4 \times 10^5 + 5 \times 10^4 + 6 \times 10^3 + 7 \times 10^2 + 8 \times 10^1 + 9 \times 10^0 \]

令 \(x = 10\)，则可以转化为：

\[ 1 \times x^8 + 2 \times x^7 + 3 \times x^6 + 4 \times x^5 + 5 \times x^4 + 6 \times x^3 + 7 \times x^2 + 8 \times x^1 + 9 \times x^0 \]

所以大数乘法就是 \(x = 10\) 情况下的多项式乘法！

那下面我们就以多项式乘法的为例来学习快速傅里叶变换 \((\textit{FFT})\) 具体是如何做的。

多项式

在学习多项式乘法之前，我们需要先学习下有关多项式的知识。

多项式有两种表示方法: 系数表示法与点值表示法。

系数表示法

设多项式 \(A(x)\) 为一个 \(n\) 项 \(n - 1\) 次的多项式，显然，所有项的系数组成的系数向量 \((a_0, a_1, a_2, \dots, a_{n-1})\) 唯一确定了这个多项式。

\[ A(x) = \sum_{i=0}^{n-1}a_i \cdot x^i = a_0 + a_1x^1 + a_2x^2 + \cdots + a_{n-1}x^{n-1} \iff A(x) = {a_0, a_1, \dots, a_{n-1}} \]

点值表示法

点值表示法是把这个多项式看成一个函数，从其中选取 \(n\) 个不同的点，从而利用这 \(n\) 个点来唯一地表示这个函数。

设

\[ \begin{array}{c} A(x_0) = y_0 = a_0 + a_1x_0+a_2x_0^2+a_3x_0^3+ \cdots + a_{n-1}x_0^{n-1} \\ A(x_1) = y_1 = a_0 + a_1x_1+a_2x_1^2+a_3x_1^3+ \cdots + a_{n-1}x_1^{n-1} \\ A(x_2) = y_2 = a_0 + a_1x_2+a_2x_2^2+a_3x_2^3+ \cdots + a_{n-1}x_2^{n-1} \\ \vdots \\ A(x_{n-1}) = y_{n-1} = a_0 + a_1x_{n-1}+a_2x_{n-1}^2+a_3x_{n-1}^3+ \cdots + a_{n-1}x_{n-1}^{n-1} \end{array} \]

那么用点值表示法表示 \(A(x)\) 如下：

\[ A(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1} \iff A(x) = {(x_0,y_0), (x_1,y_1), \cdots,(x_{n-1},y_{n-1})} \]

为什么用 \(n\) 个不同点就能唯一地表示一个 \(n-1\) 次函数？

证明如下：

• Proof \(1\) :

两点确定一条直线。再来一个点，能确定这个直线中的另一个参数，那么也就是说 \(n\) 个点能确定 \(n-1\) 个参数（不考虑倍数点之类的没用点）。

• Proof \(2\)⁵ :

假设原命题不成立，则存在两个不同的 \(n-1\) 次多项式函数 \(A(x)\) ，\(B(x)\) ，那么 \(A(x)\) ，\(B(x)\) 有 \(n-1\) 个交点，即任何 \(i \in [0, n-1]\)，有 \(A(x_i) = B(x_i)\) 。

令 \(C(x) = A(x) - B(x)\) ，则 \(C(x)\) 也是一个 \(n-1\) 次多项式。对于任何 \(i \in [0, n-1]\)，都有 \(C(x_i) = 0\) 。

即 \(C(x)\) 有 \(n\) 个根，这与代数基本定理（一个 \(n-1\) 次多项式在复数域上有且仅有 \(n-1\) 个根）相矛盾，故 \(C(x)\) 并不是一个 \(n-1\) 次多项式，推导矛盾。

故原命题成立。

By Long Luo

This article is the solution 2 Approaches: Two Pointers and Recursion of Problem 344. Reverse String .

Here shows 2 Approaches to slove this problem, Recursion and Two Pointers.

Two Pointers

Most of us may think about two pointers solution.

We need \(\dfrac {N}{2}\) times swap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public void reverseString(char[] s) {
    if (s == null || s.length <= 1) {
        return;
    }
    
    int left = 0;
    int right = s.length - 1;
    while (left < right) {
        char ch = s[left];
        s[left] = s[right];
        s[right] = ch;
        left++;
        right--;
    }
}

or use For Loop:

1
2
3
4
5
6
7
8
9
10
11
12
13

// Two Pointers Opt O(n) O(1)
public static void reverseString_tp_opt(char[] s) {
    if (s == null || s.length <= 1) {
        return;
    }

    int n = s.length;
    for (int left = 0, right = n - 1; left < right; ++left, --right) {
        char tmp = s[left];
        s[left] = s[right];
        s[right] = tmp;
    }
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(1)\)