Leetcode 第 126 场双周赛题解
Leetcode 第 126 场双周赛题解
题目1：3079. 求出加密整数的和
思路
代码
/*
* @lc app=leetcode.cn id=3079 lang=cpp
*
* [3079] 求出加密整数的和
*/
// @lc code=start
class Solution
{
public:
int sumOfEncryptedInt(vector<int> &nums)
{
int sum = 0;
for (int &num : nums)
sum += encrypt(num);
return sum;
}
// 加密函数
int encrypt(int x)
{
string s = to_string(x);
int maxDigit = 0;
for (char &c : s)
maxDigit = max(maxDigit, c - '0');
int res = 0;
for (int i = 0; i < s.length(); i++)
{
res *= 10;
res += maxDigit;
}
return res;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n*m)，其中 n 是数组 nums 的长度，m 是每个元素的位数。
空间复杂度：O(1)。
题目2：3080. 执行操作标记数组中的元素
思路
由于要按照元素从小到大标记，但又不能直接对数组排序（因为有对特定 index 的标记），我们可以创建一个 ids 数组，其中 ids[i]=i，然后对该数组按照 nums[ids[i]] 从小到大排序。注意要使用稳定排序，因为相同元素值的下标需要按照下标从小到大排。也可以使用不稳定排序（如快速排序），但要对于相同元素值按照下标从小到大排序。
设 nums 的元素和为 s。对于每个询问，我们先将 s 减少 nums[index]，然后将 nums[index] 置为 0，就相当于标记了这个数（因为题目保证数组元素都是正数）。然后依照 ids 找 k 个最小的没有被标记的数，将其标记，标记的同时维护 s。
代码
/*
* @lc app=leetcode.cn id=3080 lang=cpp
*
* [3080] 执行操作标记数组中的元素
*/
// @lc code=start
class Solution
{
public:
vector<long long>
unmarkedSumArray(vector<int> &nums, vector<vector<int>> &queries)
{
int n = nums.size();
long long s = accumulate(nums.begin(), nums.end(), 0LL);
vector<int> ids(n);
iota(ids.begin(), ids.end(), 0);
// ranges::stable_sort(ids, [&](int i, int j) { return nums[i] < nums[j]; });
sort(ids.begin(), ids.end(), [&](const int i, const int j)
{ if (nums[i] != nums[j]) return nums[i] < nums[j];
else return i < j; });
vector<long long> ans;
int idx = 0;
for (vector<int> &query : queries)
{
int index = query[0], k = query[1];
s -= nums[index];
nums[index] = 0; // 标记
for (; idx < n && k; idx++)
{
index = ids[idx];
if (nums[index] > 0) // 未被标记
{
s -= nums[index];
nums[index] = 0; // 标记
k--;
}
}
ans.push_back(s);
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。
题目3：3081. 替换字符串中的问号使分数最小
思路
算法：
- 统计字母出现次数 freq，和字母组成 pair 加到一个最小堆中。
- 设问号出现了 cnt 次。循环 cnt 次，每次取出堆顶字母（它是目前出现次数最小的）加入一个字符串 tmp 中，然后把该字母的出现次数加一，重新入堆。
- 把 tmp 从小到大排序，因为题目要求字典序最小。
- 遍历 s 中的问号，按顺序填入 tmp 中的字母。
代码
/*
* @lc app=leetcode.cn id=3081 lang=cpp
*
* [3081] 替换字符串中的问号使分数最小
*/
// @lc code=start
// 贪心 + 优先队列
class Solution
{
public:
string minimizeStringValue(string s)
{
vector<int> freq(26, 0);
for (char &c : s)
if (c != '?')
freq[c - 'a']++;
priority_queue<pair<int, char>, vector<pair<int, char>>, greater<>> pq;
for (int i = 0; i < 26; i++)
pq.emplace(freq[i], i + 'a');
int cnt = count(s.begin(), s.end(), '?');
string tmp;
for (int i = 0; i < cnt; i++)
{
auto [f, ch] = pq.top();
pq.pop();
tmp.push_back(ch);
pq.emplace(f + 1, ch);
}
// 排序，因为要求字典序最小
sort(tmp.begin(), tmp.end());
for (int i = 0, j = 0; i < s.length(); i++)
if (s[i] == '?')
s[i] = tmp[j++];
return s;
}
};
// @lc code=end
复杂度分析
题目4：3082. 求出所有子序列的能量和
思路
二维 01 背包：
代码
/*
* @lc app=leetcode.cn id=3082 lang=cpp
*
* [3082] 求出所有子序列的能量和
*/
// @lc code=start
class Solution
{
private:
const int mod = 1e9 + 7;
public:
int sumOfPower(vector<int> &nums, int k)
{
int n = nums.size();
// dp[i][j][c]: 前 i 个物品，所选物品体积和是 j，选了 c 个物品的方案数
int dp[n + 1][k + 1][n + 1];
// 初始化
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= n; i++)
dp[i][0][0] = 1;
// 状态转移
for (int i = 0; i < n; i++)
{
for (int j = k; j >= 0; j--)
{
for (int c = n; c > 0; c--)
{
// 二维0/1背包
dp[i + 1][j][c] = dp[i][j][c]; // 不选
if (j >= nums[i])
{
// 选
dp[i + 1][j][c] = (dp[i + 1][j][c] + dp[i][j - nums[i]][c - 1]) % mod;
}
}
}
}
// 贡献法
int ans = 0;
long p = 1;
for (int c = n; c >= 0; c--)
{
ans = (ans + dp[n][k][c] * p % mod) % mod;
p = (p * 2) % mod;
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n2k)，其中 n 是数组 nums 的长度。
空间复杂度：O(n2k)，其中 n 是数组 nums 的长度。
