0%

By Long Luo

This article is the solution of Problem 617. Merge Two Binary Trees.

Here are 4 approaches to solve this problem in Java.

Recursion

Method 1: New Tree

We can create a new Tree, each TreeNode\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))O(min(m, n))
  • Space Complexity: O(min(m,n))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 mergeTrees()\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))O(min(m, n))
  • Space Complexity: O(min(m,n))O(min(m, n))
阅读全文 »

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)O(V + E),其中nn为字符串长度。

  • 空间复杂度:O(V)O(V)。哈希表和字符串均需要存储nn个元素。

LeetCode 热题 HOT 100

参考资料

  1. Topological Sorting
  2. 拓扑排序

By Long Luo

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

快速傅里叶变换(FFT)

快速傅里叶变换 (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;
}
}
阅读全文 »

By Long Luo

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

方法一:暴力

思路和算法

模拟硬币排列过程,从ans=1ans = 1开始,逐行ans+1ans + 1,当硬币不足排列当前行时退出,注意返回时需要ans1 ans - 1,因为在排列完上一行时已经+1+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(n)O(\sqrt{n}),因为总行数一定不超过2(n+1)2(\sqrt{n}+1)
  • 空间复杂度O(1)O(1)

方法二:二分查找

思路和算法

ii行必须有ii个硬币(最后一行除外),总行数的增加所需要的硬币数是单调递增的,到第ii行时总共使用的硬币数量为total=i×(i+1)2total = \frac{i \times (i + 1)}{2},我们的目标是寻找一个ii使得totalntotal \leq n,可以利用二分加速在11n+12\frac{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(logn)
  • 空间复杂度O(1)O(1)
阅读全文 »

By Long Luo

This article is the solution 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 ii, jj, the heights of the vertical lines are h[i]h[i], h[j]h[j], and the area in this state is S(i,j)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])×(ji)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×(n1)/2C(n, 2)= n \times (n - 1) / 2, we have to enumerate all these states to get the max area.

The time complexity is O(n2)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(n2)O(n^2)
  • Space Complexity: O(1)O(1)
阅读全文 »

By Long Luo

This article is the solution of Problem 1721. Swapping Nodes in a Linked List.


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

If we just swap the values of two nodes, it’s very easy. All we need to do is to find these two nodes.

ArrayList(Swapping Values)

We can use an 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)O(n)
  • Space Complexity: O(n)O(n)
阅读全文 »

By Long Luo

This article is the solution of Problem 31. Next Permutation.

Two Pointers

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.

Take a example, [3,2,1][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][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, 15(2)4321 5 (2) 4 3 2, the 22 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, 15(2)4(3)21 5 (2) 4 (3) 2, after swap: 15(3)4(2)21 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][1,5,3,2,2,4], which is what is required.

阅读全文 »

By Long Luo

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

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

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

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

FFT可以做什么?

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

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

多项式乘法

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

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

大数乘法

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

不妨设十进制数字 num=123456789num=123456789 ,很容易知道:

123456789=1×108+2×107+3×106+4×105+5×104+6×103+7×102+8×101+9×100123456789 = 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=10x = 10,则可以转化为:

1×x8+2×x7+3×x6+4×x5+5×x4+6×x3+7×x2+8×x1+9×x01 \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=10x=10 情况下的多项式乘法!

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

阅读全文 »

By Long Luo

This article is the solution 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 N/2N/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)O(n)
  • Space Complexity: O(1)O(1)
阅读全文 »

By Long Luo

这篇文章是 Leetcode 1385. 两个数组间的距离值力扣社区题解

方法一:模拟

对于arr1arr1数组中的每一个元素xx,枚举数组arr2arr2中的每一个元素yy,检查是否对于每一个yy都有xy>d|x - y| > d,如果是,就将答案增加11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// BF time: O(m * n) space: O(1)
public static int findTheDistanceValue_bf(int[] arr1, int[] arr2, int d) {
int ans = 0;
for (int x : arr1) {
boolean flag = true;
for (int y : arr2) {
if (Math.abs(x - y) <= d) {
flag = false;
}
}

ans += flag ? 1 : 0;
}

return ans;
}

复杂度分析

  • 时间复杂度:O(m×n)O(m×n),其中arr1arr1中元素个数为mmarr2arr2中元素个数为nn

  • 空间复杂度:O(1)O(1)

方法二: 二分搜索

在方法一中,要知道是否每一个yy是不是满足xy>d|x - y| > d,我们枚举了所有yy

实际上因为d>=0d >= 0,假如arr2存在某个yy满足xdyx+dx - d \le y \le x + d,那么arr1中的数xx就不满足要求。

先对arr2进行排序,之后枚举arr1每个元素xx,利用二分搜索来判断xx是否满足要求。

阅读全文 »