嘉兴网站开发学校,怎样推广app别人才愿意下载,免费素材网站无版权,赣县网站建设题目列表
3079. 求出加密整数的和
3080. 执行操作标记数组中的元素
3081. 替换字符串中的问号使分数最小
3082. 求出所有子序列的能量和
一、求出加密整数的和 按照题目要求#xff0c;直接模拟即可#xff0c;代码如下
class Solution {
public:int sumOfEncryptedInt…题目列表
3079. 求出加密整数的和
3080. 执行操作标记数组中的元素
3081. 替换字符串中的问号使分数最小
3082. 求出所有子序列的能量和
一、求出加密整数的和 按照题目要求直接模拟即可代码如下
class Solution {
public:int sumOfEncryptedInt(vectorint nums) {int nnums.size(),res0;for(auto x:nums){int s 0, mx 0;while(x){mxmax(mx,x%10);ss*101;x/10;}resmx*s;}return res;}
};
二、执行操作标记数组中的元素 题目不难依旧还是只需要模拟但是代码量不少要细心思路如下
对于每次查询的操作1只要判断垓下标是否被标记然后处理即可
对于每次查询的操作2要把没有标记过的最小的k个数字标记如果数字相同则下标小的先标记很显然要排序(两个维度的排序---首先比较数值其次比较下标)这里讲一个技巧我们没必要将数值和下标打包在一起(即用pair)排序我们可以直接对下标进行排序具体看代码
如何表示一个数是否被标记可以额外开一个数组也可以直接在原数组上修改将标记过的数记为-1
代码如下
class Solution {
public:vectorlong long unmarkedSumArray(vectorint nums, vectorvectorint queries) {int n nums.size(), m queries.size();vectorlong long ans(m);vectorintidx(n);long long s 0;for(int i0;in;i) {idx[i]i;snums[i];}sort(idx.begin(),idx.end(),[](int x,int y){return nums[x]!nums[y]?nums[x]nums[y]:xy;});for(int i0,j0;im;i){const auto v queries[i];int index v[0], k v[1];if(nums[index]0){s - nums[index];nums[index] -1;}while(kjn){if(nums[idx[j]]0){j;continue;}s - nums[idx[j]];nums[idx[j]]-1;j,k--;}ans[i]s;}return ans;}
};
三、替换字符串中的问号使分数最小 这题是思维题
首先我们要明白字母出现的顺序并不会影响它们对总分数的贡献(因为字母对分数的贡献仅仅只和该字母出现的次数有关字母与其他字母之间是相互独立的)也就是说我们只要考虑每个 ? 填哪个字母即可根据cost的定义我们优先考虑之前出现次数少的字母对 ? 进行填充当出现次数一样少时我们优先考虑字典序小的字母然后对选出的字母进行排序最后按照 ? 的位置进行替换即可。
代码如下
class Solution {
public:string minimizeStringValue(string s) {int n s.size();string tmp;int cnt[26] { 0 },c 0;for(const auto e:s){if(e!?) cnt[e-a];else c;}auto cmp[](const pairint,int x,const pairint,int y)-bool{return x.first!y.first ? x.first y.first : x.second y.second;};priority_queuepairint,int,vectorpairint,int,decltype(cmp) pq(cmp); //小堆for(int i0;i26;i)pq.push({cnt[i],i});while(c--){auto [x,ch] pq.top();pq.pop();pq.push({x1,ch});tmp ach;}sort(tmp.begin(),tmp.end());for(int i0,j0;in;i){if(s[i]?)s[i]tmp[j];}return s;}
};
四、求出所有子序列的能量和
这题找子序列中的子序列看着很绕其实就是找和为k的子序列能出现在多少个子序列中即和为k的子序列做出的贡献拿示例一举例和为3的子序列有[1,2]和[3]其中[1,2]在2个子序列中出现[3]在4个子序列中出现所以答案为246。很显然每个和为3的子序列的贡献为2^(n-L)其中n为整个数组的长度L为子序列的长度。
故答案的表达式为 sum(2^(n-L) * num_K_L) 1Lnnum_K_L表示长为L和为K的子序列个数
如何求长为L和为K的子序列的个数
这是一个背包问题限制条件有两个1、长为L 2、和为K
设f[i][L][c]表示前i个数中长为L和为c的子序列的个数
1、如果当前的数不在和为c的子序列中则f[i][L][c]f[i-1][L][c]
2、如果当前的数在和为c的子序列中则f[i][L][c]f[i-1][L-1][c-nums[i]]
所以f[i][L][c]f[i-1][L][c]f[i-1][L-1][c-nums[i-1]]
初始化f[i][0][0]1因为长为0和为0的子序列只能是空只有一个
代码如下
class Solution {
public:int sumOfPower(vectorint nums, int k) {int nnums.size();const int MOD 1e97;int f[n1][n1][k1];memset(f,0,sizeof(f));//f[i][L][j] f[i-1][L][j] f[i-1][L-1][j-nums[i]]for(int i0;in;i)f[i][0][0]1;for(int i0;in;i){for(int j1;jk;j){for(int L1;Li1;L){f[i1][L][j] (f[i][L][j] (jnums[i]?f[i][L-1][j-nums[i]]:0))%MOD;}}}long long ans 0, pow2 1;for(int in;i0;i--){ans (ans f[n][i][k]*pow2)%MOD;pow2 pow2*2%MOD;}return ans%MOD;}
};// 优化空间
class Solution {
public:int sumOfPower(vectorint nums, int k) {int nnums.size();const int MOD 1e97;int f[n1][k1];memset(f,0,sizeof(f));f[0][0]1;for(int i0;in;i){for(int jk;jnums[i];j--){for(int L1i;L0;L--){f[L][j] (f[L][j] f[L-1][j-nums[i]])%MOD;}}}long long ans 0, pow2 1;for(int in;i0;i--){ans (ans f[i][k]*pow2)%MOD;pow2 pow2*2%MOD;}return ans%MOD;}
};
当然我们也可以根据题目直接定义状态f[i][j]表示前i个数为数组的元素和为k的能量值
1、如果nums[i]不在子序列和为k的序列中那么它有选和不选两种可能f[i1][j]f[i][j]*2
2、如果nums[i]在子序列和为k的序列中那么它只能被选f[i1][j]f[i][j-nums[i]]
举个例子[1,2,3]要求和为3假设遍历到 i 2 如果nums[i]3不在我们想要的子序列中那么它可以选也可以不选即f[i][j] * 2如果nums[i]3在我们想要的子序列中那么它只能被选即f[i][j-nums[i]]
所以状态转移方程为 f[i1][j]f[i][j] * 2 f[i][j-nums[i]]
代码如下
class Solution {
public:int sumOfPower(vectorint nums, int k) {const int MOD1e97;int nnums.size();vectorvectorlong longf(n1,vectorlong long(k1));f[0][0]1;for(int i0;in;i){for(int j0;jk;j){f[i1][j](f[i][j]*2(jnums[i]?f[i][j-nums[i]]:0))%MOD;}}return f[n][k];}
};//优化空间
class Solution {
public:int sumOfPower(vectorint nums, int k) {const int MOD1e97;int nnums.size();vectorlong longf(k1);f[0]1;for(int i0;in;i){for(int jk;j0;j--){f[j](f[j]*2(jnums[i]?f[j-nums[i]]:0))%MOD;}}return f[k];}
};
