devbox
爱喝兽奶帝天荒
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode---126双周赛_leetcode 126

作者：爱喝兽奶帝天荒 | 2024-07-21 04:09:59

赞

踩

leetcode 126

题目列表

3079. 求出加密整数的和

3080. 执行操作标记数组中的元素

3081. 替换字符串中的问号使分数最小

3082. 求出所有子序列的能量和

一、求出加密整数的和

按照题目要求，直接模拟即可，代码如下

  1. class Solution {
  2. public:
  3.     int sumOfEncryptedInt(vector<int>& nums) {
  4.         int n=nums.size(),res=0;
  5.         for(auto x:nums){
  6.             int s = 0, mx = 0;
  7.             while(x){
  8.                 mx=max(mx,x%10);
  9.                 s=s*10+1;
  10.                 x/=10;
  11.             }
  12.             res+=mx*s;
  13.         }
  14.         return res;
  15.     }
  16. };

二、执行操作标记数组中的元素

题目不难，依旧还是只需要模拟，但是代码量不少，要细心，思路如下：

对于每次查询的操作1：只要判断垓下标是否被标记，然后处理即可

对于每次查询的操作2：要把没有标记过的最小的k个数字标记，如果数字相同则下标小的先标记，很显然要排序(两个维度的排序---首先比较数值，其次比较下标)，这里讲一个技巧：我们没必要将数值和下标打包在一起(即用pair)排序，我们可以直接对下标进行排序，具体看代码

如何表示一个数是否被标记？可以额外开一个数组，也可以直接在原数组上修改，将标记过的数记为-1

代码如下

  1. class Solution {
  2. public:
  3.     vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {
  4.         int n = nums.size(), m = queries.size();
  5.         vector<long long> ans(m);
  6.         vector<int>idx(n);
  7.         long long s = 0;
  8.         for(int i=0;i<n;i++) {
  9.             idx[i]=i;
  10.             s+=nums[i];
  11.         }
  12.         sort(idx.begin(),idx.end(),[&](int x,int y){
  13.             return nums[x]!=nums[y]?nums[x]<nums[y]:x<y;
  14.         });
  15.         
  16.         for(int i=0,j=0;i<m;i++){
  17.             const auto& v = queries[i];
  18.             int index = v[0], k = v[1];
  19.             if(nums[index]>=0){
  20.                 s -= nums[index];
  21.                 nums[index] = -1;
  22.             }
  23.             while(k&&j<n){
  24.                 if(nums[idx[j]]<0){
  25.                     j++;
  26.                     continue;
  27.                 }
  28.                 s -= nums[idx[j]];
  29.                 nums[idx[j]]=-1;
  30.                 j++,k--;
  31.             }
  32.             ans[i]=s;
  33.         }
  34.         return ans;
  35.     }
  36. };

三、替换字符串中的问号使分数最小

这题是思维题：

首先我们要明白字母出现的顺序并不会影响它们对总分数的贡献(因为字母对分数的贡献仅仅只和该字母出现的次数有关，字母与其他字母之间是相互独立的)，也就是说我们只要考虑每个 '?' 填哪个字母即可，根据cost的定义，我们优先考虑之前出现次数少的字母对 '?' 进行填充，当出现次数一样少时，我们优先考虑字典序小的字母，然后对选出的字母进行排序，最后按照 '?' 的位置进行替换即可。

代码如下

  1. class Solution {
  2. public:
  3.     string minimizeStringValue(string s) {
  4.         int n = s.size();
  5.         string tmp;
  6.         int cnt[26] = { 0 },c = 0;
  7.         for(const auto& e:s){
  8.             if(e!='?') cnt[e-'a']++;
  9.             else c++;
  10.         }
  11.     
  12.         auto cmp=[](const pair<int,int>& x,const pair<int,int>& y)->bool{
  13.             return x.first!=y.first ? x.first > y.first : x.second > y.second;
  14.         };
  15.         priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)> pq(cmp); //小堆
  16.         for(int i=0;i<26;i++)
  17.             pq.push({cnt[i],i});
  18.         
  19.         while(c--){
  20.             auto [x,ch] = pq.top();
  21.             pq.pop();
  22.             pq.push({x+1,ch});
  23.             tmp += 'a'+ch;
  24.         }
  25.         sort(tmp.begin(),tmp.end());
  26.         for(int i=0,j=0;i<n;i++){
  27.             if(s[i]=='?')
  28.                 s[i]=tmp[j++];
  29.         }
  30.         return s;
  31.     }
  32. };

四、求出所有子序列的能量和

这题找子序列中的子序列，看着很绕，其实就是找和为k的子序列能出现在多少个子序列中，即和为k的子序列做出的贡献，拿示例一举例：和为3的子序列有[1,2]和[3]，其中[1,2]在2个子序列中出现，[3]在4个子序列中出现，所以答案为2+4=6。很显然每个和为3的子序列的贡献为2^(n-L)，其中n为整个数组的长度，L为子序列的长度。

故答案的表达式为 sum(2^(n-L) * num_K_L) 1<=L<=n，num_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的子序列只能是空，只有一个

代码如下

  1. class Solution {
  2. public:
  3.     int sumOfPower(vector<int>& nums, int k) {
  4.         int n=nums.size();
  5.         const int MOD = 1e9+7;
  6.         int f[n+1][n+1][k+1];
  7.         memset(f,0,sizeof(f));
  8.         //f[i][L][j] = f[i-1][L][j] + f[i-1][L-1][j-nums[i]]
  9.         for(int i=0;i<=n;i++)
  10.             f[i][0][0]=1;
  11.         for(int i=0;i<n;i++){
  12.             for(int j=1;j<=k;j++){
  13.                 for(int L=1;L<=i+1;L++){
  14.                     f[i+1][L][j] = (f[i][L][j] + (j>=nums[i]?f[i][L-1][j-nums[i]]:0))%MOD;
  15.                 }
  16.             }
  17.         }
  18.  
  19.         long long ans = 0, pow2 = 1;
  20.         for(int i=n;i>0;i--){
  21.             ans = (ans + f[n][i][k]*pow2)%MOD;
  22.             pow2 = pow2*2%MOD;
  23.         }
  24.         return ans%MOD;
  25.     }
  26. };
  27.  
  28. // 优化空间
  29. class Solution {
  30. public:
  31.     int sumOfPower(vector<int>& nums, int k) {
  32.         int n=nums.size();
  33.         const int MOD = 1e9+7;
  34.         int f[n+1][k+1];
  35.         memset(f,0,sizeof(f));
  36.         f[0][0]=1;
  37.         for(int i=0;i<n;i++){
  38.             for(int j=k;j>=nums[i];j--){
  39.                 for(int L=1+i;L>0;L--){
  40.                     f[L][j] = (f[L][j] + f[L-1][j-nums[i]])%MOD;
  41.                 }
  42.             }
  43.         }
  44.  
  45.         long long ans = 0, pow2 = 1;
  46.         for(int i=n;i>0;i--){
  47.             ans = (ans + f[i][k]*pow2)%MOD;
  48.             pow2 = pow2*2%MOD;
  49.         }
  50.         return ans%MOD;
  51.     }
  52. };

当然我们也可以根据题目直接定义状态：f[i][j]表示前i个数为数组的，元素和为k的能量值

1、如果nums[i]不在子序列和为k的序列中，那么它有选和不选两种可能，f[i+1][j]=f[i][j]*2

2、如果nums[i]在子序列和为k的序列中，那么它只能被选，f[i+1][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[i+1][j]=f[i][j] * 2+ f[i][j-nums[i]]

代码如下

  1. class Solution {
  2. public:
  3.     int sumOfPower(vector<int>& nums, int k) {
  4.         const int MOD=1e9+7;
  5.         int n=nums.size();
  6.         vector<vector<long long>>f(n+1,vector<long long>(k+1));
  7.         f[0][0]=1;
  8.         for(int i=0;i<n;i++){
  9.             for(int j=0;j<=k;j++){
  10.                 f[i+1][j]=(f[i][j]*2+(j>=nums[i]?f[i][j-nums[i]]:0))%MOD;
  11.             }
  12.         }
  13.         return f[n][k];
  14.     }
  15. };
  16.  
  17. //优化空间
  18. class Solution {
  19. public:
  20.     int sumOfPower(vector<int>& nums, int k) {
  21.         const int MOD=1e9+7;
  22.         int n=nums.size();
  23.         vector<long long>f(k+1);
  24.         f[0]=1;
  25.         for(int i=0;i<n;i++){
  26.             for(int j=k;j>=0;j--){
  27.                 f[j]=(f[j]*2+(j>=nums[i]?f[j-nums[i]]:0))%MOD;
  28.             }
  29.         }
  30.         return f[k];
  31.     }
  32. };
声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号