题目列表
3079. 求出加密整数的和
3080. 执行操作标记数组中的元素
3081. 替换字符串中的问号使分数最小
3082. 求出所有子序列的能量和
一、求出加密整数的和
按照题目要求,直接模拟即可,代码如下
class Solution {
public:
int sumOfEncryptedInt(vector<int>& nums) {
int n=nums.size(),res=0;
for(auto x:nums){
int s = 0, mx = 0;
while(x){
mx=max(mx,x%10);
s=s*10+1;
x/=10;
}
res+=mx*s;
}
return res;
}
};
二、执行操作标记数组中的元素
题目不难,依旧还是只需要模拟,但是代码量不少,要细心,思路如下:
对于每次查询的操作1:只要判断垓下标是否被标记,然后处理即可
对于每次查询的操作2:要把没有标记过的最小的k个数字标记,如果数字相同则下标小的先标记,很显然要排序(两个维度的排序---首先比较数值,其次比较下标),这里讲一个技巧:我们没必要将数值和下标打包在一起(即用pair)排序,我们可以直接对下标进行排序,具体看代码
如何表示一个数是否被标记?可以额外开一个数组,也可以直接在原数组上修改,将标记过的数记为-1
代码如下
class Solution {
public:
vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size(), m = queries.size();
vector<long long> ans(m);
vector<int>idx(n);
long long s = 0;
for(int i=0;i<n;i++) {
idx[i]=i;
s+=nums[i];
}
sort(idx.begin(),idx.end(),[&](int x,int y){
return nums[x]!=nums[y]?nums[x]<nums[y]:x<y;
});
for(int i=0,j=0;i<m;i++){
const auto& v = queries[i];
int index = v[0], k = v[1];
if(nums[index]>=0){
s -= nums[index];
nums[index] = -1;
}
while(k&&j<n){
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 pair<int,int>& x,const pair<int,int>& y)->bool{
return x.first!=y.first ? x.first > y.first : x.second > y.second;
};
priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)> pq(cmp); //小堆
for(int i=0;i<26;i++)
pq.push({cnt[i],i});
while(c--){
auto [x,ch] = pq.top();
pq.pop();
pq.push({x+1,ch});
tmp += 'a'+ch;
}
sort(tmp.begin(),tmp.end());
for(int i=0,j=0;i<n;i++){
if(s[i]=='?')
s[i]=tmp[j++];
}
return s;
}
};
四、求出所有子序列的能量和
这题找子序列中的子序列,看着很绕,其实就是找和为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的子序列只能是空,只有一个
代码如下
class Solution {
public:
int sumOfPower(vector<int>& nums, int k) {
int n=nums.size();
const int MOD = 1e9+7;
int f[n+1][n+1][k+1];
memset(f,0,sizeof(f));
//f[i][L][j] = f[i-1][L][j] + f[i-1][L-1][j-nums[i]]
for(int i=0;i<=n;i++)
f[i][0][0]=1;
for(int i=0;i<n;i++){
for(int j=1;j<=k;j++){
for(int L=1;L<=i+1;L++){
f[i+1][L][j] = (f[i][L][j] + (j>=nums[i]?f[i][L-1][j-nums[i]]:0))%MOD;
}
}
}
long long ans = 0, pow2 = 1;
for(int i=n;i>0;i--){
ans = (ans + f[n][i][k]*pow2)%MOD;
pow2 = pow2*2%MOD;
}
return ans%MOD;
}
};
// 优化空间
class Solution {
public:
int sumOfPower(vector<int>& nums, int k) {
int n=nums.size();
const int MOD = 1e9+7;
int f[n+1][k+1];
memset(f,0,sizeof(f));
f[0][0]=1;
for(int i=0;i<n;i++){
for(int j=k;j>=nums[i];j--){
for(int L=1+i;L>0;L--){
f[L][j] = (f[L][j] + f[L-1][j-nums[i]])%MOD;
}
}
}
long long ans = 0, pow2 = 1;
for(int i=n;i>0;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[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]]
代码如下
class Solution {
public:
int sumOfPower(vector<int>& nums, int k) {
const int MOD=1e9+7;
int n=nums.size();
vector<vector<long long>>f(n+1,vector<long long>(k+1));
f[0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=k;j++){
f[i+1][j]=(f[i][j]*2+(j>=nums[i]?f[i][j-nums[i]]:0))%MOD;
}
}
return f[n][k];
}
};
//优化空间
class Solution {
public:
int sumOfPower(vector<int>& nums, int k) {
const int MOD=1e9+7;
int n=nums.size();
vector<long long>f(k+1);
f[0]=1;
for(int i=0;i<n;i++){
for(int j=k;j>=0;j--){
f[j]=(f[j]*2+(j>=nums[i]?f[j-nums[i]]:0))%MOD;
}
}
return f[k];
}
};