找到在給定約束條件下，透過N次操作從字串'S'中刪除N個字元後的值-C++-PHP中文網

找到在給定約束條件下，透過N次操作從字串'S'中刪除N個字元後的值

王林

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

轉載

1354 人瀏覽過

找到在給定約束條件下，透過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;
}

登入後複製