# # Leetcode 第275场周赛题解

## # Problem A - 检查是否每一行每一列都包含全部整数 (opens new window)

### # 方法一：模拟

• 时间复杂度$\mathcal{O}(N^2)$
• 空间复杂度$\mathcal{O}(N)$

class Solution:
def checkValid(self, matrix: List[List[int]]) -> bool:
n = len(matrix)
return all(len(set(row)) == n for row in matrix) and all(len(set(col)) == n for col in zip(*matrix))

1
2
3
4

## # Problem B - 最少交换次数来组合所有的 1 II (opens new window)

### # 方法一：滑动窗口

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(1)$

class Solution {
public:
int minSwaps(vector<int>& nums) {
int n = nums.size();
int total_ones = 0;
for (int num : nums)
total_ones += num;

int current_ones = 0;
for (int i = 0; i < total_ones; ++i)
current_ones += nums[i];
int max_ones_in_a_seg = current_ones;
for (int i = 1; i < n; ++i) {
current_ones += nums[(i - 1 + total_ones) % n] - nums[i - 1];
max_ones_in_a_seg = max(max_ones_in_a_seg, current_ones);
}

}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

## # Problem C - 统计追加字母可以获得的单词数 (opens new window)

### # 方法一：枚举删除的字母

• 时间复杂度$\mathcal{O}((N+M)|\sum|)$
• 空间复杂度$\mathcal{O}(N)$

class Solution {
public:
int wordCount(vector<string>& startWords, vector<string>& targetWords) {
unordered_set<int> has;
for (auto &word : startWords) {
int num = 0;
for (char ch : word)
num ^= 1 << (ch - 'a');
has.insert(num);
}

int ans = 0;
for (auto &word : targetWords) {
int num = 0;
for (char ch : word)
num ^= 1 << (ch - 'a');
for (char ch : word)
if (has.count(num ^ (1 << (ch - 'a')))) {
ans++;
break;
}
}

return ans;
}
};

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

## # Problem D - 全部开花的最早一天 (opens new window)

### # 方法一：贪心

• 先种一，再种二：总时间为 $\max(a+b, a+c+d)$
• 先种二，再种一：总时间为 $\max(c+d,c+a+b)$。因为 $c+a+b>c+a+d>c+d$，所以结果就为 $c+a+b$

• 时间复杂度$\mathcal{O}(N\log N)$
• 空间复杂度$\mathcal{O}(N)$

class Solution {
public:
int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
int n = plantTime.size();
vector<int> order(n);
for (int i = 0; i < n; ++i)
order[i] = i;
sort(order.begin(), order.end(), [&](int i, int j){
return growTime[i] > growTime[j];
});

int ans = 0, day = 0;
for (int i : order) {
day += plantTime[i];
ans = max(ans, day + growTime[i]);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19