LeetCode 275场周赛
2133. 检查是否每一行每一列都包含全部整数
1. 思路
- 直接看数据范围，
1 <= n <= 100，直接暴力就可以。 - 同时注意满足条件的行列
1~n的数字只出现一次 ，所以Java使用boolean[][]数组即可。
2. 代码
2.1 Java
class Solution {
public boolean checkValid(int[][] matrix) {
int n = matrix.length;
boolean[][] rows = new boolean[n+1][n+1];
// 判断每行的数字是否只出现一次
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
if (rows[i][matrix[i][j]]) return false;
rows[i][matrix[i][j]] = true;
}
}
boolean[][] cols = new boolean[n+1][n+1];
// 判断每列的数字是否只出现一次
for (int j = 0; j < n; j ++) {
for (int i = 0; i < n; i ++) {
if (cols[j][matrix[i][j]]) return false;
cols[j][matrix[i][j]] = true;
}
}
return true;
}
}
2.2 python
class Solution:
def checkValid(self, matrix: List[List[int]]) -> bool:
n = len(matrix)
rows = [[False] * (n + 1) for _ in range(n + 1)]
cols = [[False] * (n + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(n):
if rows[i][matrix[i][j]]:
return False
rows[i][matrix[i][j]] = True
for j in range(n):
for i in range(n):
if cols[j][matrix[i][j]]:
return False
cols[j][matrix[i][j]] = True
return True
2134. 最少交换次数来组合所有的 1 II
1. 思路
- 数据范围
10^5，那么只能一次遍历了。 - 那么，数组中1的个数已经确定不变
- 所以通过一个定长的滑动窗口来寻找滑窗中出现最多次的1
- 在滑窗中计算1的过程，可以使用前缀和
tips:因为题目中提到了环形数组，所以简单处理，复制一份数组在后面就行。
2. 代码
2.1 Java
class Solution {
public int minSwaps(int[] nums) {
int n = nums.length;
int[] sum = new int[2*n+1];
for (int i = 0; i < 2 * n; i ++) {
sum[i+1] = sum[i] + (nums[i % n] == 1 ? 1 : 0);
}
int cnt = sum[n];
int ans = cnt;
for (int i = cnt; i <= 2 * n; i ++) {
ans = Math.min(ans, cnt - (sum[i] - sum[i-cnt]));
}
return ans;
}
}
2.2 python
class Solution:
def minSwaps(self, nums: List[int]) -> int:
# 环形数组解决方法
nums += nums
n = len(nums)
pres = [0]
# 计算前缀和
for i in range(n):
pres.append(pres[-1] + (1 if nums[i] == 1 else 0))
# 数组中1的总个数为
cnt = pres[n // 2]
ans = cnt
# 计算滑窗中最多的1的个数
for i in range(cnt, n):
ans = min(ans, cnt - (pres[i] - pres[i-cnt]))
return ans
2135. 统计追加字母可以获得的单词数
1. 思路
很多的条件都藏在提示里面，一定要看提示啊！！！一定要看提示啊！！！一定要看提示啊！！！
- 提示中最后两点点很重要，每个单词中字母都是小写且每个字母至多出现一次。
- 这就表示可以使用2进制数字表示每个单词。
- 转换操作在这里包含了两步，第一步追加，第二步重排。还是注意审题，审题，审题。
- 将
startWords中的单词通过状态压缩，存入set集合中。这样在后面搜索的时候，时间复杂度为O(1)。 - 遍历
targetWords时，进行同样操作。然后每次只删除一个字母，查找是否再set中。
2. 代码
2.1 Java
class Solution {
public int wordCount(String[] startWords, String[] targetWords) {
Set<Integer> swSet = new HashSet<>();
int n = targetWords.length, m = startWords.length;
// 状态压缩，存储set中
for (String s : startWords) {
int t = 0;
for (char c : s.toCharArray()) {
t += 1 << c - 'a';
}
swSet.add(t);
}
int ans = 0;
for (String s : targetWords) {
int t = 0;
for (char c : s.toCharArray()) {
t += 1 << c - 'a';
}
for (char c : s.toCharArray()) {
if (swSet.contains(t - (1 << c - 'a'))) {
ans ++;
break;
}
}
}
return ans;
}
}
2.2 python
class Solution:
def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
sw_set = set()
n = len(startWords)
m = len(targetWords)
for i in range(n):
t = 0
for s in startWords[i]:
t += 1 << ord(s) - ord('a')
sw_set.add(t)
ans = 0
for i in range(m):
target = targetWords[i]
t = 0
for s in target:
t += 1 << ord(s) - ord('a')
for s in target:
if t - (1 << ord(s) - ord('a')) in sw_set:
ans += 1
break
return ans
# 另一种优雅的lambda表达式实现（来自LC评论区）
class Solution:
def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
compress = lambda x: sum(1 << (ord(c) - ord('a')) for c in x)
exist = set(map(compress, startWords))
res = 0
for s in targetWords:
mask = compress(s)
for ch in s:
i = ord(ch) - ord('a')
if mask - (1 << i) in exist:
res += 1
break
return res