資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究給定字串，替換‘?’得到字典序最小的具有周期K的字串
當且僅當字串每隔K個字元就重複自身時，該字串才具有K的週期。例如，字串“abcabcabc”具有3的週期，因為它每隔3個字元就重複自身。字串“abcabc?abc”不具有3的週期，因為字元‘?’每隔3個字元不重複自身。
問題陳述
給定一個包含N個小寫字元的字串“str”和一個正整數K，目標是將字串“str”中每個字元‘?’替換為一個小寫字母，使得生成的字串形成長度為K的週期。如果無法找到滿足給定條件的字串，則程式應輸出“-1”。
字串str可以包含任意數量的小寫字元，包括‘a’，‘b’，‘c’，…，‘z’。
字串str也可以包含字元‘?’。
正整數K必須大於或等於1。
如果無法找到滿足給定條件的字串，則程式應列印“-1”。
示例
輸入
“aabb????”, K = 4
輸出
aabbaabb
輸入
“xxyy????”, K = 2
輸出
-1
解決方案方法
可以透過遵循下面列出的步驟來找到修改後的字串。
生成給定字串中“？”字元的所有可能的替換組合。
對於每個組合，相應地替換“？”字元。
檢查生成的字串是否具有K的週期。如果是，則將其儲存為候選解決方案。
檢查完所有組合後，比較候選解決方案並選擇字典序最小的那個。
返回字典序最小的具有K的週期的字串，或者如果找不到有效解則返回“-1”。
樸素方法涉及生成所有可能的組合，這在計算上可能很昂貴。隨著字串長度和“？”字元數量的增加，組合的數量呈指數增長。因此，這種方法對於大型輸入字串效率不高。
更最佳化的方案是使用一種高效的演算法，該演算法避免了組合的窮舉生成，並根據某些條件直接修改字串以獲得字典序最小的具有K的週期的字串。
演算法
接受字串str和整數K作為引數。
驗證字串“str”的長度是否是K的倍數。如果不是，則返回“-1”，因為無法形成長度為K的週期。
使用變數“i”迭代範圍0到K。
建立一個名為“char_freq”的空對映，用於儲存字元的頻率計數。
遍歷字串“str”，從索引“i”開始，每次迭代增加K。
更新“char_freq”對映中遇到的每個字元的頻率計數。
如果char_freq的大小大於2，則返回“-1”。
如果char_freq的大小為1，則檢查“？”的頻率是否不為零。如果是，則將str中位置i、i+K、i+2K等處的“？”字元替換為‘a’。
否則，如果char_freq的大小為2，則找到除“？”之外的字元並將其儲存在ch中。
將str中位置i、i+K、i+2K等處的“？”字元替換為ch。
返回修改後的字串str。
示例：C++程式
程式碼片段“stringNew()”旨在以字串“str”和整數“K”作為輸入。最初，該函式驗證“str”的長度是否可以被“K”整除。如果不是，則該函式返回-1。但是，如果滿足長度條件，則該函式繼續透過迭代範圍[0, K]。對於此範圍內的每個索引“i”，該函式建立一個名為“char_freq”的對映，以跟蹤在子字串“str[i: i + K]”中找到的每個字元的頻率。然後，該函式檢查“char_freq”的大小是否超過2。如果此條件為真，則該函式返回-1。另一方面，如果條件不滿足，則該函式使用儲存在“char_freq”中最頻繁的字元替換子字串中所有“？”的出現。最後，該函式返回修改後的“str”。
示例
#include <iostream>
#include <string>
#include <map>
using namespace std;
string stringNew(string &str, int K){
// Verify whether the length of the string "str" is divisible by K.
if (str.length() % K != 0){
return "-1";
}
// Perform an iteration over the interval [0, K].
for (int i = 0; i < K; i++){
// Create a map to hold the frequency of characters in the substring str[i: i + K].
map<char, int> char_freq;
// Iterate over the string with increment of K in every iteration.
for (int j = i; j < str.length(); j += K){
char_freq[str[j]]++;
}
// If there are more than two different characters in the substring.
if (char_freq.size() > 2){
return "-1";
}
// If there is only one character in the substring.
else if (char_freq.size() == 1){
// If the character is '?', replace all occurrences of '?' in the substring with 'a'.
if (char_freq['?'] != 0){
for (int j = i; j < str.length(); j += K){
str[j] = 'a';
}
}
}
// If there are two different characters in the substring.
else{
// Find a character other than '?'.
char ch;
for (auto &x : char_freq){
if (x.first != '?'){
ch = x.first;
}
}
// Exchange all occurrences of '?' in the substring with ch.
for (int j = i; j < str.length(); j += K){
str[j] = ch;
}
}
}
// Return the modified string.
return str;
}
int main(){
string str = "aabb????";
int K = 4;
cout << "original string: "<< str << " and "<< "K = 4" <<endl;
cout <<"new string: "<< stringNew(str, K) << endl;
return 0;
}
輸出
original string: aabb???? and K = 4 new string: aabbaabb
時間和空間複雜度分析
時間複雜度：O(N)
程式碼包含巢狀迴圈。外迴圈迭代範圍[0, K]，內迴圈以K的增量迭代字串。
外迴圈的複雜度為O(K)，因為它迭代K次。
內迴圈迭代字串的一部分，具體來說是位置i、i+K、i+2K等處的字元，直到字串末尾。內迴圈迭代的次數由字串的長度N和K的值決定。
總體而言，程式碼的時間複雜度為O(K * N/K) = O(N)。
程式碼分配額外的空間來儲存每個位置“i”處子字串中字元的頻率。這是使用名為“char_freq”的對映完成的。
對映“char_freq”用於記錄在子字串中遇到的字元的頻率。由於子字串最多可以包含兩個字元（包括“？”和另一個字元），因此對映僅儲存這些不同字元的頻率。
對映“char_freq”所需的空間與子字串中存在的不同字元的數量成正比，在這種情況下最大為2。
因此，程式碼的空間複雜度可以視為O(1)，因為空間使用保持恆定並且不受輸入大小的影響。
結論
本文提供了一種樸素方法和一種高效方法來解決該問題。文章提供瞭解決方案方法、使用的演算法以及C++程式解決方案，並深入分析了其時間複雜度和空間複雜度。
287 次檢視
