Long Luo's Life Notes

每一天都是奇迹

By Long Luo

Leetcode 559. N叉树的最大深度 题解。

方法一:递归

思路与算法:

类似树的深度问题,都可以使用递归实现:

  1. 确定递归的参数和返回值:参数就是传入树的根节点,返回值就是树的深度;
  2. 确定终止条件:如果为空节点的话,就返回0,表示高度为0;
  3. 确定单层递归的逻辑:如果是二叉树,那么先求它的左子树的深度,再求的右子树的深度,最后取左右深度最大的数值,最后再+1(加1是因为算上当前中间节点)就是目前节点为根节点的树的深度。

具体到N叉树,代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
// Recursion time: O(n) space: O(n)
public int maxDepth(Node root) {
if (root == null) {
return 0;
}

int ans = 0;
for (Node child : root.children) {
ans = Math.max(ans, maxDepth(child));
}

return ans + 1;
}

复杂度分析

  • 时间复杂度:O(n)O(n),其中nnNN叉树节点的个数。每个节点在递归中只被遍历一次。

  • 空间复杂度:O(height)O(\textit{height}),其中height\textit{height}表示NN叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于NN叉树的高度。

方法二:DFS迭代

二叉树的遍历,其实也是DFS的一种方式,我们可以参考二叉树的遍历,使用迭代的方式进行遍历,最后更新NN叉树的最大深度。

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
// DFS time: O(n) space: O(n)
class Pair {
Node node;
int depth;

Pair(Node node, int depth) {
this.node = node;
this.depth = depth;
}
}

public int maxDepth_dfs(Node root) {
if (root == null) {
return 0;
}

int ans = 0;
Stack<Pair> stack = new Stack<>();
stack.push(new Pair(root, 1));
while (!stack.empty()) {
Pair top = stack.pop();
Node node = top.node;
int depth = top.depth;
for (Node childNode : node.children) {
stack.push(new Pair(childNode, depth + 1));
}

ans = Math.max(ans, depth);
}

return ans;
}

复杂度分析

  • 时间复杂度:O(n)O(n),其中nnNN叉树节点的个数。

  • 空间复杂度:O(n)O(n),每个节点都需要入栈出栈一次。

阅读全文 »

By Long Luo

Leetcode 594. 最长和谐子序列 题目如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
594. 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在,给你一个整数数组nums,请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列,它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1:
输入:nums = [1,3,2,2,5,2,3,7]
输出:5
解释:最长的和谐子序列是 [3,2,2,2,3]

示例 2:
输入:nums = [1,2,3,4]
输出:2

示例 3:
输入:nums = [1,1,1,1]
输出:0

提示:
1 <= nums.length <= 2 * 10^4
-10^9 <= nums[i] <= 10^9

方法一:暴力枚举

考虑 nums\textit{nums} 中的两个数 xxyy ,其下标分别为 iijj ,那么满足数组的和谐子序列只有下列 22 种情况:

  1. xyx+1x \leq y \leq x + 1 ,且 yx=1|y - x| = 1
  2. x1yxx - 1 \leq y \leq x ,且 yx=1|y - x| = 1

首先想到的方法是 22 个循环,分别统计上述情况的最大值并更新,即为答案。

代码如下所示:

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
// BF time: O(n^2) space: O(1)
public int findLHS(int[] nums) {
int len = nums.length;
int ans = 0;
for (int i = 0; i < len; i++) {
int minDiff = 0;
int maxDiff = 0;
int cntMin = 0;
int cntMax = 0;
for (int j = 0; j < len; j++) {
if (nums[j] >= nums[i] && nums[j] <= nums[i] + 1) {
minDiff += nums[j] - nums[i];
cntMin++;
}

if (nums[j] >= nums[i] - 1 && nums[j] <= nums[i]) {
maxDiff += nums[j] - nums[i];
cntMax++;
}
}

cntMin = minDiff >= 1 ? cntMin : 0;
cntMax = maxDiff >= 1 ? cntMax : 0;
ans = Math.max(ans, Math.max(cntMin, cntMax));
}

return ans;
}

复杂度分析

  • 时间复杂度:O(N2)O(N^2),其中 NN 是数组 nums\textit{nums} 的长度。
  • 空间复杂度:O(1)O(1),需要常数个空间保存中间变量。

方法二:排序 + 双指针

思路与算法:

方法一中因为需要对 22 种情况都进行处理,所以代码非常繁琐且耗时,如果先进行排序,从最小值开始计算。

虽然题干说不能修改数字顺序,所以最开始我并没有想到排序,但实际上我们分析可以看出和排序无关,因为最大最小之差为 11,所以实际结果是和数字顺序无关的。

所以我们可以将数组按照从小到大进行排序,然后依次找到相邻两个连续相同元素的子序列,检查该这两个子序列的元素的之差是否为 11

利用滑动窗口的做法,left\textit{left} 指向第一个连续相同元素的子序列的第一个元素,right\textit{right} 指向相邻的第二个连续相同元素的子序列的末尾元素,如果满足二者的元素之差为 11,则当前的和谐子序列的长度即为两个子序列的长度之和,等于 rightleft+1\textit{right} - \textit{left} + 1

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findLHS(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
int left = 0;
int ans = 0;
for (int right = 0; right < len; right++) {
while (nums[right] - nums[left] > 1) {
left++;
}

if (nums[right] - nums[left] == 1) {
ans = Math.max(ans, right - left + 1);
}
}

return ans;
}

复杂度分析

  • 时间复杂度:O(NlogN)O(N\log N),其中 NN 是数组 nums\textit{nums} 的长度。因为需要对数组进行排序,花费的时间复杂度为 O(NlogN)O(N\log N),然后利用双指针遍历数组花费的时间为 O(2N)O(2N),总的时间复杂度 T(N)=O(NlogN)+O(2N)=O(NlogN)T(N) = O(N\log N) + O(2N) = O(N\log N)

  • 空间复杂度:O(1)O(1),需要常数个空间保存中间变量。

阅读全文 »

By Long Luo

Leetcode 318. 最大单词长度乘积 题目如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
318. 最大单词长度乘积

给定一个字符串数组words,找到length(word[i]) * length(word[j]) 的最大值,并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回0。

示例 1:
输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。

示例 2:
输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4
解释: 这两个单词为 "ab", "cd"。

示例 3:
输入: ["a","aa","aaa","aaaa"]
输出: 0
解释: 不存在这样的两个单词。

提示:
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母

方法一:暴力 + 状态压缩

思路与算法:

之前做过类似的题目,而且题目中有明显的提示 words[i]words[i] 仅包含小写字母,那么先统计出每个单词中的字母数量。

之后两层for遍历字符串,枚举两个字符串 words[i]words[i]words[j]words[j],然后暴力检验 words[i]words[i]words[j]words[j] 是否有公共字母,并更新最大值。

比较简单,代码如下所示:

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
public static int maxProduct(String[] words) {
if (words == null || words.length <= 1) {
return 0;
}

int len = words.length;
boolean[][] cnt = new boolean[len][26];
for (int i = 0; i < len; i++) {
String word = words[i];
for (char ch : word.toCharArray()) {
cnt[i][ch - 'a'] = true;
}
}

int ans = 0;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
boolean flag = true;
for (int k = 0; k < 26; k++) {
if (cnt[i][k] && cnt[j][k]) {
flag = false;
break;
}
}

if (flag) {
ans = Math.max(ans, words[i].length() * words[j].length());
}
}
}

return ans;
}

复杂度分析:

  • 时间复杂度:O(L+n2×26)O(L + n^2 \times 26),其中其中 LL 是数组 words\textit{words} 中的全部单词长度之和, nn 是数组 words\textit{words} 的长度。

  • 空间复杂度:O(26×n)O(26 \times n),其中 nn 是数组 words\textit{words} 的长度。

方法二:位运算

方法一中判断两个单词是否有公共字母需要进行 2626 次比较,如果可以将其时间复杂度降低到 O(1)O(1),可以将总时间复杂度降低到 O(n2)O(n^2)

可以使用位运算预处理每个单词,通过位运算操作判断两个单词是否有公共字母。

由于单词只包含小写字母,共有 2626 个小写字母,而 intint3232 位,因此可以使用位掩码的最低 2626 位分别表示每个字母是否在这个单词中出现。将 a\textit{a}z\textit{z} 分别记为第 00 个字母到第 2525 个字母,则位掩码的从低到高的第 ii 位是 11 当且仅当第 ii 个字母在这个单词中,其中 0i250 \le i \le 25

用数组 masks\textit{masks} 记录每个单词的位掩码表示。计算数组 masks\textit{masks} 之后,判断第 ii 个单词和第 jj 个单词是否有公共字母可以通过判断 masks[i] & masks[j]\textit{masks}[i]~\&~\textit{masks}[j] 是否等于 00 实现,当且仅当 masks[i] & masks[j]=0\textit{masks}[i]~\&~\textit{masks}[j] = 0 时第 ii 个单词和第 jj 个单词没有公共字母,此时使用这两个单词的长度乘积更新最大单词长度乘积。

阅读全文 »

By Long Luo

Leetcode 299. 猜数字游戏

方法一:HashMap --> Array

思路与算法:

首先,Bulls\textit{Bulls} 最好计算,遍历,如果相同,那么 Bulls+1Bulls+1。但是 Cows\textit{Cows} 如何计算呢?

  1. 首先想到的是使用 HashMap\texttt{HashMap} 来记录数字及其出现次数,因为可能会出现多个数字,所以出现位置是没有办法记录的;
  2. 遇到 Cows\textit{Cows},则 22HashMapHashMap 都减去相应数字;
  3. 最后遍历 090 \to 9,如果 22HashMap\texttt{HashMap} 都大于 00 ,那么把较小数相加即得到 Cows\textit{Cows}

代码如下所示:

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
public String getHint(String secret, String guess) {
int len = secret.length();
int bulls = 0;
int cows = 0;
Map<Integer, Integer> secretMap = new HashMap<>();
Map<Integer, Integer> guessMap = new HashMap<>();
for (int i = 0; i < len; i++) {
int secVal = secret.charAt(i) - '0';
int guessVal = guess.charAt(i) - '0';
secretMap.put(secVal, secretMap.getOrDefault(secVal, 0) + 1);
guessMap.put(guessVal, guessMap.getOrDefault(guessVal, 0) + 1);
if (secVal == guessVal) {
bulls++;
secretMap.put(secVal, secretMap.getOrDefault(secVal, 0) - 1);
guessMap.put(guessVal, guessMap.getOrDefault(guessVal, 0) - 1);
}
}

for (int i = 0; i <= 9; i++) {
int secFreq = secretMap.getOrDefault(i, 0);
int guessFreq = guessMap.getOrDefault(i, 0);
if (secFreq > 0 && guessFreq > 0) {
cows += Math.min(secFreq, guessFreq);
}
}

return bulls + "A" + cows + "B";
}

上述代码其实可以优化,因为 map\textit{map} 中的 key\textit{key} 只有 090 \to 9,所以我们可以用数组取代 map\textit{map} 以节省空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String getHint(String secret, String guess) {
int len = secret.length();
int bulls = 0;
int cows = 0;
int[] secNums = new int[10];
int[] gusNums = new int[10];
for (int i = 0; i < len; i++) {
int secVal = secret.charAt(i) - '0';
int guessVal = guess.charAt(i) - '0';
secNums[secVal]++;
gusNums[guessVal]++;
if (secVal == guessVal) {
bulls++;
secNums[secVal]--;
gusNums[guessVal]--;
}
}

for (int i = 0; i <= 9; i++) {
cows += Math.min(secNums[i], gusNums[i]);
}

return bulls + "A" + cows + "B";
}

复杂度分析

  • 时间复杂度:O(N)O(N),其中 NN 是字符串的长度。
  • 空间复杂度:O(C)O(C),需要常数个空间统计字符出现次数,由于我们统计的是数字字符,C=10C=10
阅读全文 »

By Long Luo

Leetcode 598. 范围求和 II

方法一: 模拟

思路与算法:

首先按照题意,对矩阵进行操作,最后遍历矩阵看最大的数有几个即可。

而最大的值显然是 M[0][0]M[0][0]

代码如下所示:

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
public int maxCount(int m, int n, int[][] ops) {
if (ops == null || ops.length == 0 || ops[0].length == 0) {
return m * n;
}

int ans = 0;
int[][] mat = new int[m][n];
for (int[] op : ops) {
int row = op[0];
int col = op[1];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
mat[i][j]++;
}
}
}

int maxVal = mat[0][0];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (maxVal == mat[i][j]) {
ans++;
}
}
}

return ans;
}

复杂度分析

  • 时间复杂度:O(km2n2)O(km^2n^2),其中 kk 是数组 ops\textit{ops} 的长度。
  • 空间复杂度:O(mn)O(mn),需要创建一个新的二维数组。

方法二: 找到所有操作的交集

思路与算法:

方法一显然会超时,而且因为我们只需要找到最大值的个数,而有满足要求的次数恰好等于操作次数的位置。

我们只需要找到所有操作中的最小值。

代码如下所示:

阅读全文 »
0%