LeetCode第126场双周赛个人题解
目录
100262. 求出加密整数的和
原题链接
思路分析
AC代码
3080. 执行操作标记数组中的元素
原题链接
思路分析
AC代码
100249. 替换字符串中的问号使分数最小
原题链接
思路分析
AC代码
100241. 求出所有子序列的能量和
原题链接
思路分析
AC代码
100262. 求出加密整数的和
原题链接
100262. 求出加密整数的和
思路分析
直接模拟即可
O(nlogn)
AC代码
class Solution {
public:int sumOfEncryptedInt(vector<int>& nums) {for(auto& x : nums){string s = to_string(x);char ma = *max_element(s.begin(), s.end());for(auto& ch : s) ch = ma;x = stoi(s);}return accumulate(nums.begin(), nums.end(), 0);}
};3080. 执行操作标记数组中的元素
原题链接
3080. 执行操作标记数组中的元素
思路分析
还是模拟题
把所有元素放set内，然后遍历操作，如果访问过就执行操作二，否则先执行操作一再执行操作二
O(nlogn)（因为最多删n次）
AC代码
class Solution {
public:typedef pair<int,int> pii;vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& q) {int n = q.size(), m = nums.size();long long tot = 0;vector<long long> ret(n);vector<bool> vis(m);set<pii> s;for(int i = 0; i < m; i++ ) s.insert(make_pair(nums[i], i)), tot += nums[i];for(int j = 0; j < n; j++){int i = q[j][0], k = q[j][1];if(!vis[i]) s.erase(s.find(make_pair(nums[i], i))), tot -= nums[i], vis[i] = 1;for(; k > 0 && s.size(); k--) vis[s.begin()->second] = 1, tot -= s.begin()->first, s.erase(s.begin());ret[j] = tot;}return ret;}
};100249. 替换字符串中的问号使分数最小
原题链接
100249. 替换字符串中的问号使分数最小
思路分析
贪心
我们考虑最终状态的分数来自于26个字母的贡献，不同字母之间互不影响
那么最终状态其实就是有26个桶，桶内元素个数分别为cnt[i]，然后满足Σcnt[i] = len(s)
然后对于每个桶的贡献为(cnt[i] - 1) * cnt[i] / 2
要使得所有桶的贡献和最小，我们就可以贪心地来做
先把不是问号地字符放到桶中，然后顺序遍历问号，将其赋值为当前桶内数目最少的字符，然后更新桶
但这只是获取了最终的各个桶内字符的个数，然后我们将原有的字符从桶中拿去，然后遍历问号位置，按字符序从桶内取出字符即可
O(nU)，U为字符集大小
AC代码
class Solution {
public:string minimizeStringValue(string s) {int cnt[26]{0};string ret = s;for(auto x : ret) if(x != '?') cnt[x - 'a']++;for(auto& ch : s)if(ch == '?'){int i = min_element(cnt, cnt + 26) - cnt;ch = i + 'a', cnt[ch - 'a']++;}for(auto x : ret) if(x != '?') cnt[x - 'a']--;for(auto& ch : ret){if(ch == '?'){int i = 0;for(; !cnt[i]; i++);ch = i + 'a', cnt[i]--;}}return ret;}
};100241. 求出所有子序列的能量和
原题链接
100241. 求出所有子序列的能量和
思路分析
很明显的01背包
先考虑和为k的子序列数目，显然就是01背包板子问题
但是这道题相当于是求子序列的和为k的子序列的和的和
那么我们这样考虑，对于那些和为k的子序列可以被多少序列包含？
显然有2 ^ (n - len)个序列包含了这个和为k的子序列
那么我们只需要在01背包的板子的转移方程稍加修改即可
定义f[i][j]为前i个元素中，和为j的所有子序列的能量和
那么递推的时候还是选或不选的思路
选或不选，有f[i][j] = f[i - 1][j] * 2，即nums[i]可以加入前面和为j的子序列也可以不加入
然后我们注意，nums[i]也可以和前面和为j - nums[i]的子序列组合形成一个新的和为j的序列
所以当j > nums[i]的时候，有f[i][j] += f[i - 1][j - nums[i]]
O(nk)
AC代码
class Solution {
public:
static constexpr int mod = 1e9+7;int sumOfPower(vector<int>& nums, int k) {long long f[105]{0};f[0] = 1;for(auto x : nums)for(int j = k; j >= 0; j--)if(j >= x) f[j] = (f[j] * 2 + f[j - x]) % mod;else f[j] = (f[j] << 1) % mod;\return f[k];}
};