leetcode第241场周赛
总览
- A题: 枚举子集
- 参考: 位运算操作
- B题: 分类讨论
- 参考: 分类讨论, 【分类讨论】力扣335-路径交叉
- C题: 设计，哈希表
- 参考: 设计-功能系统
- D题: 动态规划, 组合数学
- 参考1: 组合数学3-特殊计数序列,指数型母函数
- 参考2: 单串线性DP-多维状态,在阶段的基础上附加维度
A 题
一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
注意：在本题中，元素 相同 的不同子集应 多次 计数。
数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。
提示： 1 <= nums.length <= 12 1 <= nums[i] <= 20
示例 1：
输入：nums = [1,3]
输出：6
解释：[1,3] 共有 4 个子集：
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6示例 2：
输入：nums = [5,1,6]
输出：28
解释：[5,1,6] 共有 8 个子集：
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 = 4 。
- [5,6] 的异或总和为 5 XOR 6 = 3 。
- [1,6] 的异或总和为 1 XOR 6 = 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28示例 3：
输入：nums = [3,4,5,6,7,8]
输出：480
解释：每个子集的全部异或总和值之和为 480 。
算法: 枚举子集
首先我们枚举 n 个元素的所有 个子集，然后枚举所有 n 个元素，判断枚举到的元素是否在当前子集中，如果在当前子集中，则更新当前子集的异或和。
其中枚举子集这个需求可以通过位运算的方式实现，代码如下:
for(i = 0; i <= (1 << n) - 1; ++i)
{
...
} 总时间复杂度
代码
class Solution {
public:
int subsetXORSum(vector<int>& nums) {
int n = nums.size();
int ans = 0;
for(int i = 0; i <= (1 << n) - 1; ++i)
{
int sum = 0;
for(int j = 0; j < n; ++j)
if(i >> j & 1)
sum ^= nums[j];
ans += sum;
}
return ans;
}
}; B 题
给你一个二进制字符串 s ，现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数，如果无法完成转化，返回 -1 。
交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100" 不是。
任意两个字符都可以进行交换，不必相邻 。
示例 1：
输入：s = "111000"
输出：1
解释：交换位置 1 和 4："111000" -> "101010" ，字符串变为交替字符串。示例 2：
输入：s = "010"
输出：0
解释：字符串已经是交替字符串了，不需要交换。示例 3：
输入：s = "1110"
输出：-1
提示： 1 <= s.length <= 1000 s[i] 的值为 '0' 或 '1'
算法: 分类讨论
首先判断输入字符串能否变成交替字符串: 枚举所有字母，记录 0 的个数 n0, 1 的个数 n1。如果 abs(n1 - n0) > 1 则不可能转换为交替字符串，返回 -1。
下面就要看当原字符串可以转换成交替字符串的时候，具体如何转换。按照 n 的奇偶性讨论
(1) 如果 n 为奇数
n 为奇数则有两种情况
第一种是 n1 = n0 + 1, 此时统计类似于 "10101" 的形式的目标串与原串中有多少个字符不一样，记为 diff。
第二种是 n0 = n1 + 1, 此时统计类似于 "01011" 的形式的目标串与原串中有多少个字符不一样，记为 diff。
最终 diff / 2 就是答案。
(2) 如果 n 为偶数
统计类似于 "101010" 的形式的目标串与原串中有多少个字符不一样，记为 diff1。
统计类似于 "010101" 的形式的目标串与原串中有多少个字符不一样，记为 diff2。
最终 min(diff1, diff2) / 2 是答案。
代码
class Solution {
public:
int minSwaps(string s) {
int n = s.size();
int n0 = 0, n1 = 0;
for(const char& ch: s)
{
if(ch == '0')
++n0;
else
++n1;
}
if(abs(n1 - n0) > 1)
return -1;
if(n & 1)
{
int diff = 0;
if(n1 > n0)
{
// 10101 形式
for(int i = 0; i < n; ++i)
{
if(i & 1)
diff += s[i] != '0';
else
diff += s[i] != '1';
}
}
else
{
// 01010 形式
for(int i = 0; i < n; ++i)
{
if(i & 1)
diff += s[i] != '1';
else
diff += s[i] != '0';
}
}
return diff / 2;
}
else
{
int diff1 = 0; // 101010 形式
int diff2 = 0; // 010101 形式
for(int i = 0; i < n; ++i)
{
if(i & 1)
{
diff1 += s[i] != '0';
diff2 += s[i] != '1';
}
else
{
diff1 += s[i] != '1';
diff2 += s[i] != '0';
}
}
return min(diff1, diff2) / 2;
}
}
}; C 题
给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：
累加 ，将一个正整数加到 nums2 中指定下标对应元素上。
计数 ，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目（0 <= i < nums1.length 且 0 <= j < nums2.length）。
实现 FindSumPairs 类：
- FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1 和 nums2 初始化 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 <= nums1.length <= 1000 1 <= nums2.length <= 1e5 1 <= nums1[i] <= 109 1 <= nums2[i] <= 105 0 <= index < nums2.length 1 <= val <= 105 1 <= tot <= 109 最多调用 add 和 count 函数各 1000 次
算法: 基于哈希表的设计
FindSumPairs 内部数据结构设计
unordered_map<int, int> mapping1; unordered_map<int, int> mapping2; vector<int> nums2;
其中 nums2 即为构造时传入的 nums2。
mapping1 为 nums2 中各个数字出现的次数
mapping1 为 nums1 中各个数字出现的次数
add(index, val) 接口要将 nums2[index] 的元素加 val，而做这个操作的时候，内部数据结构也要进行相应的修改。首先将 mapping2 中 nums2[index] 的次数减 1，然后将 nums2[index] 增加 val。然后将新的 nums2[index] 在 mapping2 中加 1，时间复杂度
对于 count(tot) 接口，枚举 nums1 中的所有元素 x，x 的个数为 mapping1[x]，问 nums1 中有多少个 tot - x，也就是 mapping2[tot - x]，mapping2[tot - x] * mapping1[x] 就是当前枚举的 nums1 中的元素 x 对答案的贡献。将 nums1 中所有元素的贡献加起来就是结果。时间复杂度
注意由于 nums1 长度为 1e3，nums2 长度为 1e5，枚举元素必须是枚举短的，也就是 nums1 的元素，查询长的，也就是 mapping2
代码
class FindSumPairs {
public:
FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
this -> nums2 = nums2;
for(int x: nums1)
++mapping1[x];
for(int x: nums2)
++mapping2[x];
}
void add(int index, int val) {
--mapping2[nums2[index]];
nums2[index] += val;
++mapping2[nums2[index]];
}
int count(int tot) {
int ans = 0;
for(auto item: mapping1)
{
int x = item.first, nx = item.second;
int y = tot - x;
if(mapping2.count(y) == 0)
continue;
int ny = mapping2[y];
ans += nx * ny;
}
return ans;
}
private:
unordered_map<int, int> mapping1;
unordered_map<int, int> mapping2;
vector<int> nums2;
}; D 题
有 n 根长度互不相同的木棍，长度为从 1 到 n 的整数。请你将这些木棍排成一排，并满足从左侧 可以看到 恰好 k 根木棍。从左侧 可以看到 木棍的前提是这个木棍的 左侧 不存在比它 更长的 木棍。
例如，如果木棍排列为 [1,3,2,5,4] ，那么从左侧可以看到的就是长度分别为 1、3 、5 的木棍。
给你 n 和 k ，返回符合题目要求的排列 数目 。由于答案可能很大，请返回对 109 + 7 取余 的结果。
提示： 1 <= n <= 1000 1 <= k <= n
示例 1：
输入：n = 3, k = 2
输出：3
解释：[1,3,2], [2,3,1] 和 [2,1,3] 是仅有的能满足恰好 2 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。示例 2：
输入：n = 5, k = 5
输出：1
解释：[1,2,3,4,5] 是唯一一种能满足全部 5 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。示例 3：
输入：n = 20, k = 11
输出：647427950
解释：总共有 647427950 (mod 109 + 7) 种能满足恰好有 11 根木棍可以看到的排列。
算法1: 动态规划 (超时)
定义 dp[i][k] := 一共有 i 根棍子，重排列后从左侧可以恰好看见 k 根的方案数。
对于 n 根根子，要求 dp[n][K], 我们考虑最长的那根棍子所在的位置，加入它在位置 p，则 [p+1..n-1] 这些棍子怎么排对结果都没有影响，可以随便排，同时 [0..p-1] 这些棍子需要排成恰好可以看见 K - 1 根棍子的情形。问题变成了 dp[p][K - 1]
dp[n][K] = comb(n - 1, p) * fab(n - 1 - p) * dp[p][K - 1]
基于这个思路我们可以写出基础动态规划算法
状态定义
dp[i][k] := 有 i 根根子，能看见 k 个的方案数
初始化
dp[0][1..] = 0
dp[0][0] = 1
dp[1][1] = 1
答案 dp[n][K]
状态转移
dp[i][k] = sum(Comb(i - 1, p) * fab(i - 1 - p) * dp[j][k - 1])
p 为最高棍子左侧的棍子数
i - 1 - p 为最高棍子右侧的棍子数
0 <= p <= i - 1 可以将 comb(0~n, 0~n) 和 fab(0~n-1) 的结果预处理出来。状态转移时 comb(i - 1, p) 和 fab(i - 1 - p) 这两步查询可以用了。
预处理的时间复杂度为
由于转移时间复杂度时间复杂度 ，所以总时间复杂度
代码(超时)
using ll = long long;
const int MOD = 1e9 + 7;
class Solution {
public:
int rearrangeSticks(int n, int K) {
fac = vector<int>(n, 1);
fac[0] = 1;
for(int i = 1; i < n; ++i)
fac[i] = (fac[i - 1] * (ll)i) % MOD;
comb = vector<vector<int>>(n + 1, vector<int>(n + 1, 0));
for(int i = 0; i <= n; ++i)
comb[i][0] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= min(i, n); ++j)
comb[i][j] = (comb[i - 1][j] + (ll)comb[i - 1][j - 1]) % MOD;
dp = vector<vector<int>>(n + 1, vector<int>(K + 1, -1));
dp[0][0] = 1;
for(int i = 1; i <= n; ++i)
{
dp[i][0] = 0;
dp[i][1] = fac[i - 1];
}
return solve(n, K);
}
private:
vector<vector<int>> dp;
vector<vector<int>> comb;
vector<int> fac;
int solve(int n, int K)
{
if(dp[n][K] != -1)
return dp[n][K];
if(K > n)
return dp[n][K] = 0;
// 1 <= K <= n
dp[n][K] = 0;
for(int p = K - 1; p <= n - 1; ++p)
{
// p: 最高棍子左侧的棍子数
// n - 1 - p: 最高棍子右侧的棍子数
dp[n][K] = ((ll)dp[n][K] + ((comb[n - 1][p] * (ll)fac[n - 1 - p]) % MOD) * (ll)solve(p, K - 1)) % MOD;
}
return dp[n][K];
}
}; 算法2: 动态规划(改变状态转移方式)
考虑 dp[i][k] 的转移时，不是向算法 1 那样考虑最高的那根棍子在重排后放置在哪个位置，而是考虑最后一根棍子重排后可不可见。
如果可见: 则最后一根棍子放的是最高的拿一根，问题变成了 dp[i - 1][k - 1]
如果不可见: 则记最后一根棍子放的是 x，则剩下的 i - 1 根棍子重排后需要见到 k 根，而无论怎么排，x 都对最终可以看到几根无影响，因此对于 i - 1 种 x 的选择，问题都会变成 dp[i - 1][k]
根据以上思路，改变转移方式后的动态规划算法如下
状态定义 dp[i][k] := 有 i 根根子，能看见 k 个的方案数 初始化 dp[0][1..] = 0 dp[0][0] = 1 dp[1][1] = 1 答案 dp[n][K] 状态转移 dp[i][k] = dp[i - 1][k - 1] + (i - 1) * dp[i - 1][k]
总时间复杂度
代码
class Solution {
public:
int rearrangeSticks(int n, int K) {
using ll = long long;
const int MOD = 1e9 + 7;
vector<vector<int>> dp(n + 1, vector<int>(K + 1, 0));
dp[0][0] = 1;
for(int i = 1; i <= n; ++i)
for(int k = 1; k <= K; ++k)
dp[i][k] = (((i - 1) * (ll)dp[i - 1][k]) % MOD + (ll)dp[i - 1][k - 1]) % MOD;
return dp[n][K];
}
}; 算法3: 第一类斯特林数
第一类斯特林数问题描述
n 个人排成一个环，分成 m 个环，环内元素的顺序要保持原有顺序，有多少种方法。
等价问题：圆周上有 n 个点，能画出多少个不同的圈(一个点也算是圈)
递推公式
记答案为
考虑从 n-1 到 n，新增的第 n 个元素有两种方案:
- n 自己是一个圈，其余 n - 1 形成 m - 1 个圈
- n 加入一个已有的圈，因为有序，有 n - 1 个位置可以插入，其余 n - 1 形成 m 个圈
因此可以写出递推公式
可以看出本题的 DP 转移方程与第一类斯特林数是一样的。
查看3道真题和解析