Long Luo's Life Notes

每一天都是奇迹

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

By Long Luo

Leetcode 396. 旋转函数 题解。

方法一： 暴力法

思路与算法

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

每次旋转更新最大值，时间复杂度为 \(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(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)\)，并求出最大值。

很容易使用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)\)。

阅读全文 »

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

By Long Luo

This article is the solution 4 Approaches: Recursion, Iteration, BFS and DFS of Problem 617. Merge Two Binary Trees .

Here are 4 approaches to solve this problem in Java: Recursion, Iteration, BFS and DFS.

Recursion

Method 1: New Tree

We can create a new Tree, each \(\texttt{TreeNode}\) value is sum of two nodes.

1
2
3
4
5
6
7
8
9
10
11
12
public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    }
    if (root2 == null) {
        return root1;
    }
    TreeNode merged = new TreeNode(root1.val + root2.val);
    merged.left = mergeTrees(root1.left, root2.left);
    merged.right = mergeTrees(root1.right, root2.right);
    return merged;
}

Analysis

  • Time Complexity: \(O(min(m, n))\)
  • Space Complexity: \(O(min(m, n))\)

Method 2

Traverse both the given trees in a PreOrder style.

At every step, check if the current node exists for both the trees. If one of these children happens to be null, we return the child of the other tree to be added as a child subtree to the calling parent node in the first tree.

We can add the values in the current nodes of both the trees and update the value in the current node of the first tree to reflect this sum obtained.

Then we call the \(\texttt{mergeTrees()}\) with the left children and then with the right children of the current nodes of the two trees.

At the end, the first tree will represent the required resultant merged binary tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static TreeNode mergeTrees_rec(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    }
    if (root2 == null) {
        return root1;
    }

    if (root1 != null) {
        root1.val += root2.val;
        root1.left = mergeTrees_rec(root1.left, root2.left);
        root1.right = mergeTrees_rec(root1.right, root2.right);
    }

    return root1;
}

Analysis

  • Time Complexity: \(O(min(m, n))\)
  • Space Complexity: \(O(min(m, n))\)
阅读全文 »

发表于 更新于 分类于 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)\)。
阅读全文 »
0%