双周赛 40
将句子排序
给定一个句子,包含多个单词,每个单词后面有一个从 \(1\) 开始的位置索引,现在要求还原原来的句子
举例
-
sentence4 a3 is2 This1
可以被还原成This is a sentence
-
Myself2 Me1 I4 and3
可以被还原成Me Myself and I
题解
分割字符串,把字符串和索引合成一个 pair<string, int>
,放在容器 vector
里面进行排序,最后合成答案即可
class Solution {
public:
string sortSentence(string s) {
vector<pair<string, int>> vec;
string temp = "";
for (int i = 0; i < s.length(); ++i) {
if (isdigit(s[i])) {
vec.push_back({temp, s[i] - '0'});
temp = "";
}
else temp += s[i];
}
sort(vec.begin(), vec.end(), [&](pair<string, int> x, pair<string, int> y) {
return x.second < y.second;
});
string ans = "";
for (int i = 0; i < vec.size(); ++i) {
ans += vec[i].first;
if (i != vec.size() - 1) ans += ' ';
}
return ans;
}
};
增长的内存泄露
给定两个内存碎片 memory1, memory2
,现在第 i
秒有一个程序需要占据 i
内存,占用内存的规则如下
- 如果两个碎片内存一样,优先占用第一个
- 否则占用剩余内存多的那一个
返回三个参数,分别是 程序退出的时间, memory1
和 memory2
的值
例如,memory1 = 2, memory2 = 2
,内存分配如下
- 第
1
秒,memory1
被占用1
内存,memory1 = 1, memory2 = 2
- 第
2
秒,memory2
被占用2
内存,memory1 = 1, memory2 = 0
- 第
3
秒,没有内存可用,程序意外退出
数据保证,0 <= memory1, memory2 <= 2^31 - 1
题解
直接循环模拟,根据 \(1 + 2 + .. + n = \frac{n(n + 1)}{2}\),时间复杂度大概在 \(O(\sqrt{memory_{1} + memory_{2}})\) 时间范围
class Solution {
public:
vector<int> memLeak(int memory1, int memory2) {
int cnt = 1;
while (memory1 >= cnt || memory2 >= cnt) {
if (memory1 == memory2) memory1 -= cnt;
else if (memory1 > memory2) memory1 -= cnt;
else memory2 -= cnt;
cnt++;
}
vector<int> ans = {cnt, memory1, memory2};
return ans;
}
};
旋转盒子
给定 \(m\times n\) 的字符矩阵 box
,其中
-
#
表示石头 -
*
表示障碍物 -
.
表示空位
将 box
顺时针旋转 \(90^{\circ}\),石头可能会受重力下降,返回最终 \(box\) 的形态
例如
# . * .
# # * .
旋转 \(90^{\circ}\)
# #
# .
* *
. .
根据重力,最终情况如下
# .
# #
* *
. .
题解
找到旋转前坐标和旋转后坐标的映射关系
设旋转前的坐标为 \((i,\ j)\),则旋转后的坐标为 \((j,\ m - i - 1)\),根据这个映射关系得到旋转后的矩阵
模拟石头下落,记得从底层往上层循环,因为下面的石头落下去之后,上面的石头可以继续下落,否则会出现 石头腾空现象
class Solution {
public:
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
int m = box.size(), n = box[0].size();
vector<vector<char>> vec(n, vector<char>(m, 0));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
vec[j][m - i - 1] = box[i][j];
for (int i = n - 1; i >=0 ; --i) {
for (int j = 0; j < m; ++j) {
if (vec[i][j] == '#') {
int k = i + 1;
while (k < n && vec[k][j] == '.') k++;
if (k != i + 1) {
vec[i][j] = '.';
vec[k - 1][j] = '#';
}
}
}
}
return vec;
}
};
向下取整数对和
给定长为 \(n\) 的数组 \(A\)
计算所有下标对 \(0\leq i,\ j\leq n - 1\),下取整 \(\left \lfloor \frac{A_{i}}{A_{j}}\right \rfloor\) 的和
数据规定
\(1\leq n\leq 10^5\)
\(1\leq A_{i}\leq 10^5\)
题解
处理思路很奇妙
我们用 \(val\left[i\right]\) 表示数组 \(A\) 中位于区间 \(\left[1,\ i\right]\) 的数字出现的次数,这个可以用前缀和处理
对于数 \(A_i\),区间 \(\left[A_i,\ 2A_i\right)\) 中的数字对答案的贡献为 \(1\cdot (val\left[2A_i - 1\right] - val\left[A_i - 1\right])\),区间 \(\left[2A_i,\ 3A_i\right)\)中的数字对答案的贡献为 \(2\cdot (val\left[3A_i - 1\right] - val\left[2A_i - 1\right])\),以此类推
我们可以用一个类似于筛法一样的操作计算答案
我们在最外层枚举数字 \(i\),内层枚举 \(j\times i\),这样随着 \(i\) 的增大,设最大值为 \(u\),那么总的计算量为
\[\sum_{i = 1}^{u}\frac{u}{i} = u(\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + .. + \frac{1}{u}) = ulnu \]因此总的时间复杂度为 \(ulogu\),其中 \(u\) 为数组最大值
#define LL long long
const int MOD = 1e9 + 7;
class Solution {
public:
int sumOfFlooredPairs(vector<int>& nums) {
int upper = *max_element(nums.begin(), nums.end());
vector<LL> cnt(upper + 1, 0);
vector<LL> val(upper + 1, 0);
for (auto &i: nums) cnt[i]++;
for (int i = 1; i <= upper; ++i) val[i] = cnt[i] + val[i - 1];
LL ans = 0;
for (int i = 1; i <= upper; ++i) {
if (cnt[i]) {
for (int j = 1; j * i <= upper; ++j) {
ans += j * cnt[i] * (val[min((j + 1) * i - 1, upper)] - val[j * i - 1]), ans %= MOD;
}
}
}
return ans;
}
};
单周赛 241
找出所有子集的异或总和再求和
给定一个长为 \(n\) 的数组 \(A\),计算出 \(A\) 的所有子集异或和的和
- 例如,数组
[2, 5, 6]
的异或总和为2 ^ 5 ^ 6 = 1
数据规定
\(1\leq n\leq 12\)
\(1\leq A_{i}\leq 20\)
题解
注意到数据规模,可以二进制枚举子集,然后计算异或和,最后求和,时间复杂度 \(O(n\cdot 2^n)\)
class Solution {
public:
int subsetXORSum(vector<int>& nums) {
int n = nums.size();
int N = 1 << n;
int ans = 0;
for (int i = 0; i < N; ++i) {
int temp = 0;
for (int j = 0; j < n; ++j) {
if (i & (1 << j)) temp ^= nums[j];
}
ans += temp;
}
return ans;
}
};
构成交替字符串需要的最小交换次数
给定一个 \(01\) 串 \(s\),现在需要把它变成 \(01\) 交替的形式,计算最小的交换数,如果无法构成该形式,返回 \(-1\)
- 例如,\(110\) 变成 \(101\),最小交换次数为 \(1\)
- 例如,\(101\) 已经是 \(01\) 交替的形式,最小交换次数为 \(0\)
- 例如,\(1110\) 无法构成 \(01\) 交替的形式,因此返回 \(-1\)
数据规定
\(1\leq s.length\leq 1000\)
题解
为了方便起见,设 \(s\) 的长度为 \(n\)
我们先判断一下什么情况无法构成 \(01\) 交替串,设 \(1\) 的个数为 \(cnt\),那么 \(0\) 的个数为 \(n - cnt\)
如果 \(cnt\) 与 \(n - cnt\) 相差超过 \(1\),那么无法构成交替串
例如 \(n = 8,\ cnt = 3,\ n - cnt = 5\),顶多构成如下形式
01010100
其次考虑最小交换次数,分两种情况考虑
- 首位为 \(1\)
- 首位为 \(2\)
我们用 101010..
和 010101..
分别与 \(s\) 做异或,我们可以求得 海明距离,海明距离的物理意义在于,将 \(A\) 串转化为 \(B\) 串所需要修改的次数
设两次异或的结果分别为 \(cnt1,\ cnt2\),如果这两个值为偶数,那么说明 可以有交换发生
我们选择 \(cnt_{1},\ cnt_{2}\) 中最小的偶数,返回其 \(\frac{1}{2}\) 即可
class Solution {
public:
int minSwaps(string s) {
int n = s.length();
int cnt1 = 0, cnt2 = 0, cnt = 0;
for (int i = 0; i < n; ++i) if (s[i] == '1') cnt++;
if (abs(cnt - (n - cnt)) > 1) return -1;
// xor 10101..0101
for (int i = 0; i < n; ++i) {
if (i % 2) cnt1 += (s[i] - '0') ^ 0;
else cnt1 += (s[i] - '0') ^ 1;
}
// xor 0101..0101
for (int i = 0; i < n; ++i) {
if (i % 2) cnt2 += (s[i] - '0') ^ 1;
else cnt2 += (s[i] - '0') ^ 0;
}
if (cnt1 % 2 && cnt2 % 2) return -1;
else if (cnt1 % 2 && !(cnt2 % 2)) return cnt2 / 2;
else if (!(cnt1 % 2) && cnt2 % 2) return cnt1 / 2;
else return min(cnt1 / 2, cnt2 / 2);
}
};
后记
这题带点思维含量,要想清楚贪心的性质才能开始做
找出和为指定值的下标对
给定两个数组 \(N_{1},\ N_{2}\),长度分别为 \(n_{1},\ n_{2}\),设计一个数据结构,支持下面两个操作
-
累加,给定
id, val
,使得N[id] += val
-
计数,给定
tot
,计算下标对的数量,满足N[i] + N[j] = tot
数据规定
\(1\leq n_{1}\leq 10^3\)
\(1\leq n_{2}\leq 10^5\)
最多调用计数和累加各 \(1000\) 次
题解
计数操作是经典问题,可以使用哈希表解决
具体来讲,求解 \(N_{1}\left[i\right] + N_{2}\left[j\right] = tot\),可以将其中一个数组的元素放入哈希表,然后遍历另一个数组查询哈希表
如果把 \(N_{1}\) 中的元素压入哈希表,遍历 \(N_{2}\) 查询,复杂度是 \(O(1000\cdot n_{2})\),会导致超时
因此考虑把 \(N_{2}\) 中的元素压入哈希表,遍历 \(N_{1}\) 查询,复杂度是 \(O(1000\cdot n_{1})\)
考虑到修改操作,我们还要额外对哈希表进行增加和删除
总的时间复杂度为 \(O(1000\cdot n_{2})\)
恰有 \(K\) 根木棍可以看到的排列数目
给定 \(n\) 根长度各不相同的木棍,长度为 \(1\) 到 \(n\) 的整数
现在把 \(n\) 根木棍排成一排,并满足 从左侧恰好可以看到 \(k\) 根木棍,从左侧可以看到木棍的前提是,更左侧不存在更长的木棍,例如
- 木棍排列为
[1, 3, 2, 5, 4]
,从左侧可以看到1, 3, 5
三根木棍
现在给定 \(n,\ k\),计算所有符合条件的排列个数,答案对 \(10^9 + 7\) 取余
数据规定
\(1\leq k\leq n\leq 1000\)
题解
注意到这个数据范围,考虑动态规划求解
定义 \(dp_{i,\ j}\) 表示用 \(i\) 根木棍,恰好可以看到 \(j\) 根的排列数目,考虑最后一个木棍
- 若其可以被看到,那么其长度一定为 \(i\),因为他是最高的,所以前 \(i - 1\) 根木棍只能看到 \(j - 1\) 个
- 若其不可以被看到,设其长度为 \(x\),则前 \(i - 1\) 根木棍的长度一定为 \(1,\ 2,\ ..,\ x - 1,\ x + 1,\ ..,\ i - 1\),那么前 \(i - 1\) 个木棍仍然可以看到 \(j\) 个,因为相对长度不变
所以有如下状态转移方程
\[dp\left[i\right]\left[j\right] = dp\left[i - 1\right]\left[j - 1\right] + (i - 1)\cdot dp\left[i - 1\right]\left[j\right] \]初始状态 \(dp\left[1\right]\left[1\right] = 1\),只有 \(1\) 这一个排列方式
int dp[1007][1007];
const int MOD = 1e9 + 7;
class Solution {
public:
int rearrangeSticks(int n, int k) {
dp[1][1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
dp[i][j] = (dp[i - 1][j - 1] + 1LL * (i - 1) * dp[i - 1][j] % MOD) % MOD;
}
}
return dp[n][k];
}
};
后记
本题状态转移方程其实是第一类斯特林数