Long Luo's Life Notes

每一天都是奇迹

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

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]\) 仅包含小写字母，那么先统计出每个单词中的字母数量。

之后两层for遍历字符串，枚举两个字符串 \(words[i]\) 和 \(words[j]\)，然后暴力检验 \(words[i]\) 和 \(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 + n^2 \times 26)\)，其中其中 \(L\) 是数组 \(\textit{words}\) 中的全部单词长度之和， \(n\) 是数组 \(\textit{words}\) 的长度。

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

方法二：位运算

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

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

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

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

阅读全文 »

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

By Long Luo

Leetcode 299. 猜数字游戏 。

方法一：HashMap –> Array

思路与算法：

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

  1. 首先想到的是使用 \(\texttt{HashMap}\) 来记录数字及其出现次数，因为可能会出现多个数字，所以出现位置是没有办法记录的；
  2. 遇到 \(\textit{Cows}\)，则 \(2\) 个 \(HashMap\) 都减去相应数字；
  3. 最后遍历 \(0 \to 9\)，如果 \(2\) 个 \(\texttt{HashMap}\) 都大于 \(0\) ，那么把较小数相加即得到 \(\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";
}

上述代码其实可以优化，因为 \(\textit{map}\) 中的 \(\textit{key}\) 只有 \(0 \to 9\)，所以我们可以用数组取代 \(\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)\)，其中 \(N\) 是字符串的长度。
  • 空间复杂度：\(O(C)\)，需要常数个空间统计字符出现次数，由于我们统计的是数字字符，\(C=10\)。
阅读全文 »

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

By Long Luo

Leetcode 598. 范围求和 II。

方法一： 模拟

思路与算法：

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

而最大的值显然是 \(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(km^2n^2)\)，其中 \(k\) 是数组 \(\textit{ops}\) 的长度。
  • 空间复杂度：\(O(mn)\)，需要创建一个新的二维数组。

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

思路与算法：

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

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

代码如下所示：

阅读全文 »

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

By Long Luo

Leetcode 268. 丢失的数字 的题解，English version is 4 Approaches: Sorting, Hash, XOR, Math 。

方法一：暴力 + 排序

思路与算法

这是一道简单题。首先想到的方法是先进行排序，然后遍历数组，找到值不同的那个数字，如果都相同，那么结果就是 \(len\)。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
public int missingNumber(int[] nums) {
	int len = nums.length;
	Arrays.sort(nums);
	for (int i = 0; i < len; i++) {
		if (i != nums[i]) {
			return i;
		}
	}

	return len;
}

复杂度分析：

  • 时间复杂度：\(O(n \log n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。排序的时间复杂度是 \(O(n \log n)\)，遍历数组寻找丢失的数字的时间复杂度是 \(O(n)\)，因此总时间复杂度是 \(O(n \log n)\)。
  • 空间复杂度：\(O(\log n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。空间复杂度主要取决于排序的递归调用栈空间。

方法二：HashSet

可以使用一个 \(\texttt{HashSet}\) 来记录数组中出现的数，将时间复杂度降低为 \(O(n)\)。

首先遍历数组 \(\textit{nums}\)，记录数组中的每个元素，然后检查从 \(0\) 到 \(n\) 的每个整数是否在哈希集合中，不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是 \(O(1)\)，因此总时间复杂度是 \(O(n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int missingNumber_set(int[] nums) {
	int len = nums.length;
	Set<Integer> set = new HashSet<>();
	for (int i = 0; i < len; i++) {
		set.add(nums[i]);
	}

	for (int i = 0; i <= len; i++) {
		if (set.add(i)) {
			return i;
		}
	}

	return len;
}

复杂度分析：

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

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

By Long Luo

Leetcode 1218. 最长定差子序列 题目如下：

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
1218. 最长定差子序列

给你一个整数数组arr和一个整数difference，请你找出并返回arr中最长等差子序列的长度，该子序列中相邻元素之间的差等于difference。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从arr派生出来的序列。

示例 1：
输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是[1,2,3,4]。

示例 2：
输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是[7,5,3,1]。

提示：
1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4
 
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

方法一：暴力

思路与算法：

首先想到的是暴力法，在第二个循环中寻找构成等差数列的数字并更新长度，找到最大长度。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int longestSubsequence(int[] arr, int difference) {
    int len = arr.length;
    int ans = 1;
    for (int i = 0; i < len; i++) {
        int value = arr[i];
        int cnt = 1;
        for (int j = i + 1; j < len; j++) {
            if (arr[j] == value + difference) {
                cnt++;
                value = arr[j];
            }
        }

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

    return ans;
}

复杂度分析：

  • 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
  • 空间复杂度：\(O(1)\)。
阅读全文 »
0%