第 241 场力扣周赛 总结&题解

最后一题搞了半天,最后发现是数学板子题。。

找出所有子集的异或总和再求和

给你一个数组 nums ,请你求出 nums 中每个 子集异或总和 ,计算并返回这些值相加之

$n\leq 12$

数据范围太小,暴力跑就行,复杂度 $O(2^n)$。

实际上可以考虑二进制的每一位,如果这一位在某个子集的异或总和有贡献,说明该子集中有奇数个数在这一位是 $1$。

设这 $n$ 个数中,第 $i$ 位为 $1$ 的有 $a$ 个数,则有 $2^{n-a}\times \sum\limits_{i=1}^{a}[i\bmod 2=1]\binom{a}{i}=2^{n-1}$,该位的贡献为 $2^i$,则所有位对答案的贡献是$2^{n-1}\times \sum{2^i}$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int subsetXORSum(vector<int>& nums) {
int x = 0;
for (auto a : nums) x |= a;
return (1 << (nums.size() - 1)) * x;
}
};
class Solution2 { // 暴力
public:
int ans = 0;
void dfs(int x, int cur, vector<int> &nums) {
if (x == nums.size()) {
ans += cur;
return ;
}
dfs(x + 1, cur, nums);
dfs(x + 1, cur ^ nums[x], nums);
}
int subsetXORSum(vector<int>& nums) {
dfs(0, 0, nums);
return ans;
}
};

构成交替字符串需要的最小交换次数

给你一个二进制字符串 s ,现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数,如果无法完成转化,返回 -1

交替字符串 是指:相邻字符之间不存在相等情况的字符串。例如,字符串 "010""1010" 属于交替字符串,但 "0100" 不是。

任意两个字符都可以进行交换,不必相邻

$n\leq 1000$

首先判断一下 $0$ 和 $1$ 的个数来判断能否转化,然后尝试一下两种情况,取较小值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int minSwaps(string s) {
int num = 0, ans = 0;
for (auto c : s) num += c == '0';
if (s.size() & 1) {
if (num * 2 - 1 != s.size() && num * 2 + 1 != s.size()) return -1;
if (num * 2 -1 == s.size()) {
for (int i = 0; i < s.size(); i += 2) ans += s[i] != '0';
} else {
for (int i = 1; i < s.size(); i += 2) ans += s[i] != '0';
}
} else {
int ans2 = 0;
if (num * 2 != s.size()) return -1;
for (int i = 0; i < s.size(); i += 2) ans2 += s[i] != '0';
for (int i = 1; i < s.size(); i += 2) ans += s[i] != '0';
ans = min(ans, ans2);
}
return ans;
}
};

找出和为指定值的下标对

给你两个整数数组 nums1nums2 ,请你实现一个支持下述两类查询的数据结构:

  1. 累加 ,将一个正整数加到 nums2 中指定下标对应元素上。
  2. 统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目(0 <= i < nums1.length0 <= j < nums2.length)。

实现 FindSumPairs 类:

  • FindSumPairs(int[] nums1, int[] nums2) 使用整数数组nums1nums2 初始化 FindSumPairs 对象。

  • void add(int index, int val)val 加到 nums2[index] 上,即,执行 nums2[index] += val

  • int count(int tot) 返回满足nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。

$1\leq n \leq 1000,1\leq m \leq 10^5$

用哈希表暴力统计即可。

Code

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

class FindSumPairs {
public:
map<int, int> N1, N2;
vector<int> v1, v2;
FindSumPairs(vector<int> &nums1, vector<int> &nums2) {
for (auto x : nums1) {
N1[x]++;
}
for (auto x : nums2) {
N2[x]++;
}
v1.insert(v1.end(), nums1.begin(), nums1.end());
v2.insert(v2.end(), nums2.begin(), nums2.end());
}

void add(int index, int val) {
N2[v2[index]]--;
v2[index] += val;
N2[v2[index]]++;
}

int count(int tot) {
int ans = 0;
for (auto x : N1) {
if (N2.find(tot - x.first) != N2.end())
ans += N2[tot - x.first] * x.second;
}
return ans;
}
};

恰有 K 根木棍可以看到的排列数目

n 根长度互不相同的木棍,长度为从 1n 的整数。请你将这些木棍排成一排,并满足从左侧 可以看到 恰好 k 根木棍。从左侧 可以看到 木棍的前提是这个木棍的 左侧 不存在比它 更长的 木棍。

给你 nk ,返回符合题目要求的排列 数目 。由于答案可能很大,请返回对 10^9 + 7 取余 的结果。

$1\leq k\leq n\leq 1000$

假设前 $i$ 个位置能看到 $j$ 个数的方案数记为 $f_{i,j}$,现在要在插入一个新数。

首先它可能成为第 $j+1$ 个能看到的数, 则 $f_{i,j}\rightarrow f_{i+1,j+1}$。

其次它可能成为前面 $j$ 组中的一员,可以放到任意一个数的后面,有 $i-1$ 种方案。

因此 $f_{i,j}=f_{i-1,j-1}+i\times f_{i-1,j}$。

这就是个 $O(n^2)$ 的递推,$f_{i,j}$ 也就是第一类斯特林数,表示将 $1\sim i$ 划分成 $j$ 个圆排列的方案数。

Code

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
class Solution1 { // 暴力
public:
int mod = 1e9 + 7;
int F[2][1005][1005];
int rearrangeSticks(int n, int m) {
for (int i = 1; i <= n; ++i) {
F[1][1][i] = 1;
}
for (int i = 2, t = 0; i <= n; ++i, t ^= 1) {
memset(F[t], 0, sizeof F[t]);
for (int j = 1; j <= m; ++j) {
for (int k = i; k <= n; ++k) {
F[t][j][k] = (1ll * F[t ^ 1][j][k] * (k - i + 1) + F[t][j][k]) % mod;
}
long long sum = 0;
for (int k = i - 1; k < n; ++k) {
(sum += F[t ^ 1][j][k]) %= mod;
F[t][j + 1][k + 1] = (F[t][j + 1][k + 1] + sum) % mod;
}
}
}
return F[n & 1][m][n];
}
};

class Solution {
public:
int mod = 1e9 + 7;
int F[1005][1005];
int rearrangeSticks(int n, int m) {
F[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
F[i][j] = (F[i - 1][j - 1] + 1ll * (i - 1) * F[i - 1][j]) % mod;
}
}
return F[n][m];
}
};