資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在給定約束條件下，查詢刪除字串“S”的N個字元後N次操作後的值
使用字串的規範是什麼？
為了解決一個涉及給定字串S的特定挑戰。字串S只包含小寫英文字母，並且在刪除字元時必須遵循某些約束。
給定的約束條件為：
字串S中包含小寫英文字母。
只有當字元在字串中出現多次時才能刪除。
只能刪除連續出現的字元。可以使用以下步驟從字串S中刪除字元：
在迭代字串S時，找到所有出現多次的字元。透過再次迭代字串S來查詢每個字元的所有連續出現。
如果連續出現的次數大於或等於迭代次數，則刪除字元的第一個N個出現。
繼續執行步驟2和3，直到所有迭代完成。
最後，透過返回最終字串S，可以發現刪除N個字元後N次操作後的字串值。
語法
本主題是一個編碼問題，它涉及透過對給定字串執行特定數量的操作來操作給定字串。在每次操作中，刪除字串中最頻繁的字元，並更新每個剩餘字元的頻率。執行N次操作後，透過將每個剩餘字元的頻率平方並求和來計算字串的最終值。問題的目標是編寫一個程式，該程式以字串和數字N作為輸入，並根據給定的約束條件輸出執行N次操作後的字串的最終值。
以下是查詢在給定約束條件下刪除字串S的N個字元後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;
}
輸出
Value of string after 3 operations: 3
結論
總之，我們可以使用直接的方法來獲取在上述限制下從字串“S”中刪除N個字元後N次操作後的值。首先，讓我們初始化一個頻率陣列來跟蹤字串中每個字元的出現次數。刪除N個字元後，我們可以重複從頻率陣列中刪除計數最多的字元的過程。此過程可以重複總共N次。
藉助這種方法，我們可以快速確定N次操作後字串“S”的值，這些操作包括刪除N個字元。由於方法中包含排序步驟，因此此解決方案的時間複雜度為O(N logN)，這對於大多數實際應用來說是可以接受的。
190 次瀏覽
