找到在给定约束条件下，通过N次操作从字符串'S'中删除N个字符后的值-C++-PHP中文网

找到在给定约束条件下，通过N次操作从字符串'S'中删除N个字符后的值

王林

发布： 2023-08-26 22:29:18

转载

1353 人浏览过

找到在给定约束条件下，通过N次操作从字符串S中删除N个字符后的值

字符串的使用规范是什么？

解决涉及给定字符串S的特定挑战。字符串S仅包含小写英文字母，并且在删除字符时必须遵循一定的约束。

给定的约束是 -

字符串S中有小写英文字母
只有在字符串中出现多次的字符才能删除。
只能删除连续出现的字符。以下步骤可用于从字符串 S 中删除字符 -
在迭代字符串 S 时查找所有出现多次的字符。通过对每个字符再次迭代字符串 S 来查找所有连续出现的字符。
如果字符连续出现的次数大于或等于迭代次数，则删除前 N 个出现的字符。
继续执行步骤 2 和 3，直到完成所有迭代。

最后，通过返回最终的字符串S，可以发现经过N次操作去除N个字符后的字符串的值。

语法

本主题是一个编码问题，涉及通过对给定字符串执行一定数量的操作来操纵该字符串。在每次操作中，删除字符串中最常见的字符，并更新每个剩余字符的频率。执行N次操作后，通过对剩余每个字符的频率进行平方并求和来计算字符串的最终值。该问题的目标是编写一个程序，以字符串和数字 N 作为输入，并根据给定的约束执行 N 次操作后输出字符串的最终值。

下面是函数的语法，该函数在 N 次操作后找到值，以在给定的约束下删除字符串 S 的 N 个字符 -

int findvalueafterNoperations(int n, string s) {
   int len = s.length();
   int freq[26] = {0};
   for (int i = 0; i < len; i++) {
      freq[s[i] - 'a']++;
   }
   sort(freq, freq + 26, greater<int>());
   for (int i = 0; i < n; i++) {
      freq[0]--; 
      sort(freq, freq + 26, greater<int>()); 
   }
   int value = 0;
   for (int i = 0; i < 26; i++) {
      value += freq[i] * freq[i];
   }
   return value;
}

登录后复制

该函数接受两个参数 -

n - 表示要执行的操作数的整数。
s - 表示输入字符串的字符串。

该函数首先使用数组计算输入字符串中每个字符的频率。然后将此频率数组按降序排序并执行 N 次操作，其中每次操作中减少最常见字符的频率并再次对频率数组进行排序。

最后，函数通过对排序频率数组中每个字符的频率平方求和来计算字符串的值，并将其作为整数返回。

算法

经过N次字符去除过程后，算法在以下限制下计算字符串的值。输入由数字 N 和字符串 S 组成。

第 1 步 - 使用数组确定输入字符串中每个字符的频率。
步骤 2 - 降序排列此频率数组。
第3步 - 执行N次操作，每次操作都会降低频率数组中出现频率最高的字符的频率。
第 4 步 - 重新排列频率数组。
第 5 步 - 将排序后的频率数组中每个字符的频率平方相加，以确定字符串的值。
第 6 步 - 经过 N 次运算后，字符串的值是其平方和。

该技术之所以有效，是因为问题要求从输入字符串 S 中删除 N 个字符，这就像执行 N 次操作，其中每次操作都会删除字符串中最常见的字符一次。由于任务的限制，我们无法真正从字符串中删除字符，因此我们必须通过在每次操作中降低频率数组中最常见字符的频率来模拟此操作。

遵循的方法

方法 1

使用代码初始化样本字符串S和各种操作N。在循环执行每个操作后，大于下一个字符的初始字符将被删除。如果没有删除，则最后一个字符将被删除。所有操作结束后，它会打印字符串的最终值。

这里，代码假设 N 小于或等于字符串 S 的长度。如果 N 长于 S，则代码将无法按预期运行。

示例 1

#include <iostream>
#include <string>
using namespace std;
int main(){
   string S = "abcdefg";
   int N = 3;
   for (int l = 1; l <= N; l++) {
      int p=0;
      while(p<S.length()- 1) {
         if(S[p]>S[p+1]) {
            S.erase(p, 1);
            break;
         }
         p++;
      }
      if(p==S.length()- 1) {
         S.erase(p, 1);
      }
   }
   cout<< S << endl;
   return 0 ;
}

登录后复制

输出

a b c d

登录后复制

方法2

在此代码中，首先使用数组确定输入字符串中每个字符的频率。接下来我们执行 N 次操作，每次操作中最常见字符的频率递减，并再次对频率数组进行排序。接下来，我们按降序对这个频率数组进行排序。

字符串的值最终通过将排序后的频率数组中每个字符的频率平方相加来确定。

示例 2

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(){
   // Given values
   int n = 3; 
   string s = "abcabc"; 
   int len = s.length();
   int freq[26] = {0};
   for (int i = 0; i < len; i++) {
      freq[s[i] - 'a']++;
   }
   sort(freq, freq + 26, greater<int>());
   for (int i = 0; i < n; i++) {
      freq[0]--; 
      sort(freq, freq + 26, greater<int>()); 
   }
   int value = 0;
   for (int i = 0; i < 26; i++) {
      value += freq[i] * freq[i];
   }
   cout << "Value of string after " << n << " operations: " << value << endl;
   return 0;
}

登录后复制