网站建设费用高,织梦统计网站访问量代码,在猪八戒网站如何做兼职,济南seo网站关键词优化排名目录
100262. 求出加密整数的和
原题链接
思路分析
AC代码
3080. 执行操作标记数组中的元素
原题链接
思路分析
AC代码 100249. 替换字符串中的问号使分数最小
原题链接
思路分析
AC代码
100241. 求出所有子序列的能量和
原题链接
思路分析
AC代码 100262. 求出…目录
100262. 求出加密整数的和
原题链接
思路分析
AC代码
3080. 执行操作标记数组中的元素
原题链接
思路分析
AC代码 100249. 替换字符串中的问号使分数最小
原题链接
思路分析
AC代码
100241. 求出所有子序列的能量和
原题链接
思路分析
AC代码 100262. 求出加密整数的和
原题链接
100262. 求出加密整数的和
思路分析
直接模拟即可
O(nlogn)
AC代码
class Solution {
public:int sumOfEncryptedInt(vectorint 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 pairint,int pii;vectorlong long unmarkedSumArray(vectorint nums, vectorvectorint q) {int n q.size(), m nums.size();long long tot 0;vectorlong long ret(n);vectorbool vis(m);setpii 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 1e97;int sumOfPower(vectorint 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];}
};
