Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 857 阅读时长 ≈ 1 分钟

By Long Luo

207. 课程表

代码如下所示：

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
public boolean canFinish(int numCourses, int[][] prerequisites) {
    if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0) {
        return true;
    }

    int[] indegree = new int[numCourses];
    for (int[] pre : prerequisites) {
        indegree[pre[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
        }
    }

    while (!queue.isEmpty()) {
        Integer currId = queue.poll();
        numCourses--;
        for (int[] pre : prerequisites) {
            if (pre[1] == currId) {
                indegree[pre[0]]--;
                if (indegree[pre[0]] == 0) {
                    queue.offer(pre[0]);
                }
            }
        }
    }

    return numCourses == 0;
}

复杂度分析

  • 时间复杂度：\(O(V + E)\)，其中 \(n\) 为字符串长度。
  • 空间复杂度：\(O(V)\)。哈希表和字符串均需要存储 \(n\) 个元素。

参考资料

  1. Topological Sorting
  2. 拓扑排序
  3. Topological Sort (Indegree)
  4. Topological Sort (DFS)

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 11k 阅读时长 ≈ 10 分钟

By Long Luo

Leetcode 43. 字符串相乘 其实就是大数乘法，常规的大数方法可以参考 超大数字的四则运算是如何实现的呢？ ，还可以使用快速傅里叶变换 \((\textit{FFT})\) 和快速数论变换 \((\textit{NTT})\) 实现。

快速傅里叶变换(FFT)

快速傅里叶变换 \((\textit{FFT})\) 详细解释可以参考这几篇文章：

快速傅里叶变换(FFT)算法

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

下面分别给出递归版和迭代版代码实现：

递归(Recursion)

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
class Solution {
public:
    const double PI = acos(-1.0);  // PI = arccos(-1)

    struct Complex {
        double re, im;

        Complex(double _re = 0.0, double _im = 0.0) {
            re = _re;
            im = _im;
        }

        inline void real(const double &re) {
            this->re = re;
        }

        inline double real() {
            return re;
        }

        inline void imag(const double &im) {
            this->im = im;
        }

        inline double imag() {
            return im;
        }

        inline Complex operator-(const Complex &other) const {
            return Complex(re - other.re, im - other.im);
        }

        inline Complex operator+(const Complex &other) const {
            return Complex(re + other.re, im + other.im);
        }

        inline Complex operator*(const Complex &other) const {
            return Complex(re * other.re - im * other.im, re * other.im + im * other.re);
        }

        inline void operator/(const double &div) {
            re /= div;
            im /= div;
        }

        inline void operator*=(const Complex &other) {
            *this = Complex(re * other.re - im * other.im, re * other.im + im * other.re);
        }

        inline void operator+=(const Complex &other) {
            this->re += other.re;
            this->im += other.im;
        }

        inline Complex conjugate() {
            return Complex(re, -im);
        }
    };

    /**
     * FFT Recursion 实现
     *
     * @param a
     * @param invert true means IFFT, else FFT
     * @return im
     */
    vector<Complex> FFT(vector<Complex> &a, bool invert) {
        //第一个参数为一个多项式的系数, 以次数从小到大的顺序, 向量中每一项的实部为该项系数
        int n = a.size();

        // 如果当前多项式仅有常数项时直接返回多项式的值
        if (n == 1) {
            return a;
        }

        vector<Complex> Pe(n / 2), Po(n / 2); // 文中的Pe与Po的系数表示法

        for (int i = 0; 2 * i < n; i++) {
            Pe[i] = a[2 * i];
            Po[i] = a[2 * i + 1];
        }

        // Divide 分治
        // 递归求 ye = Pe(xi), yo = Po(xi)
        vector<Complex> ye = FFT(Pe, invert);
        vector<Complex> yo = FFT(Po, invert);

        // Combine
        vector<Complex> y(n);

        // Root of Units
        double ang = 2 * PI / n * (invert ? -1 : 1);
        Complex wn(cos(ang), sin(ang)); // wn为第1个n次复根,
        Complex w(1, 0);   // w为第零0个n次复根, 即为 1

        for (int i = 0; i < n / 2; i++) {
            y[i] = ye[i] + w * yo[i];  // 求出P(xi)
            y[i + n / 2] = ye[i] - w * yo[i]; // 由单位复根的性质可知第k个根与第k + n/2个根互为相反数
            w = w * wn;  // w * wn 得到下一个复根
        }

        return y;  // 返回最终的系数
    }

    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }

        int len1 = num1.size();
        int len2 = num2.size();

        int n = 1;
        while (n < len1 + len2) {
            n = n << 1;
        }

        vector<Complex> a(n);
        vector<Complex> b(n);

        for (int i = len1 - 1; i >= 0; i--) {
            a[i] = Complex(num1[len1 - 1 - i] - '0', 0);
        }

        for (int i = len2 - 1; i >= 0; i--) {
            b[i] = Complex(num2[len2 - 1 - i] - '0', 0);
        }

        a = FFT(a, false);
        b = FFT(b, false);

        for (int i = 0; i < n; i++) {
            a[i] = a[i] * b[i];
        }

        a = FFT(a, true);

        string ans;
        int carry = 0;
        for (int i = 0; i < n; i++) {
            int sum = round(round(a[i].re) / n) + carry;
            carry = sum / 10;
            ans += sum % 10 + '0';
        }

        if (carry > 0) {
            ans += carry % 10 + '0';
        }

        int idx = ans.size() - 1;
        while (ans[idx] == '0' && idx > 0) {
            idx--;
        }

        ans = ans.substr(0, idx + 1);
        reverse(ans.begin(), ans.end());
        return ans;
    }
}
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2k 阅读时长 ≈ 2 分钟

By Long Luo

Leetcode 441. 排列硬币 的题解，有4种解决方法，前3种比较容易想到，位运算 比较难想到。

方法一：暴力

思路和算法

模拟硬币排列过程，从 \(ans = 1\) 开始，逐行 \(ans + 1\)，当硬币不足排列当前行时退出，注意返回时需要 $ ans - 1$，因为在排列完上一行时已经 \(+1\) 了，返回时需要 \(-1\)。

1
2
3
4
5
6
7
8
9
10
// BF O(sqrtn) O(1)
public int arrangeCoins_bf(int n) {
	int ans = 1;
	while (n >= ans) {
		n -= ans;
		ans++;
	}

	return ans - 1;
}

复杂度分析

  • 时间复杂度：\(O(\sqrt{n})\)，因为总行数一定不超过 \(2(\sqrt{n}+1)\)。
  • 空间复杂度：\(O(1)\)。

方法二：二分查找

思路和算法

第 \(i\) 行必须有 \(i\) 个硬币（最后一行除外），总行数的增加所需要的硬币数是单调递增的，到第 \(i\) 行时总共使用的硬币数量为 \(total = \frac{i \times (i + 1)}{2}\)，我们的目标是寻找一个 \(i\) 使得 \(total \leq n\)，可以利用二分加速在 \(1\) 到 \(\dfrac{n + 1}{2}\) 之间查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// BS O(logn) O(1)
public int arrangeCoins_bs(int n) {
	long left = 1;
	long right = ((long) n + 1) / 2;
	while (left < right) {
		long mid = left + (right - left + 1) / 2;
		long sum = mid * (mid + 1) / 2;
		if (sum <= n) {
			left = mid;
		} else {
			right = mid - 1;
		}
	}

	return (int) left;
}

复杂度分析

  • 时间复杂度：\(O(logn)\)。
  • 空间复杂度：\(O(1)\)。
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

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

Problem 11

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)\)
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3.3k 阅读时长 ≈ 3 分钟

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)\)
阅读全文 »
0%