資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學字典序最小的奇數位數數字字串
本文提供了一種建立字典序最短的 N 長度數字字串的完整方法，其中每個數字的計數必須為奇數。我們對問題陳述進行了深入的解釋，提出了一種有效的演算法策略，並使用 C++ 將其付諸實踐。複雜性分析揭示了該解決方案的效率，並且透過使用測試場景的解釋說明了該方法的準確性和有效性。
問題陳述
給定一個正整數 N，任務是生成大小為 N 的最小數字字串，該字串遵循字典序，其中字串中的每個數字的計數必須為奇數。讓我們深入研究一些示例以更好地理解——
示例 1
Let the Input taken be N = 5, Output is equal to 11111
註釋——遵循字典序的最小字串由數字 1 組成，其計數為奇數。
示例 2
Let the Input taken be N = 6, Output is equal to 111112
註釋——字典序最小的字串由數字 1 和 2 組成，兩者計數均為奇數。
方法/演算法
定義名為“`generateSmallestNumericString`”的函式，該函式將整數 N（結果字串的長度）作為引數，並返回一個字串（長度等於 N）。
在函式內部：宣告一個名為 resultString 的字串變數，該變數為空，以便稍後儲存生成的字串。
使用模運算子 (%)，檢查 N 是偶數還是奇數
如果是偶數——將 resultString 賦值為 (N − 1) 個數字 '1' 與數字 '2' 的連線。這保證了結果字串透過具有 (N−1) 個 1 和單個數字 2 來滿足每個數字的奇數計數要求，即 N−1 將給出奇數（因為 N 為偶數），而 2 的計數為 1 也是奇數，因此滿足條件。
如果 N 為奇數——將結果賦值為 N 個數字 '1'。這確保了結果字串中的所有數字都是 '1'，滿足每個數字的奇數計數要求。
最後，返回結果最小字串。
示例
現在，讓我們在不同的程式語言中實現上述方法：C、C++、Java 和 Python——
#include <stdio.h>
// Function to generate the lexicographically smallest numeric string with odd digit counts
void generateSmallestNumericString(int N, char resultString[]){
// Check if N is even using the modulo operator (%)
if (N % 2 == 0) {
// If N is even: Assign the result with N - 1 occurrences of the digit '1'
// and then concatenate it with the digit '2'.
// This ensures that there are (N-1) ones and a single digit 2 in the resulting string,
// satisfying the odd count requirement for each digit
for (int i = 0; i < N - 1; i++) {
resultString[i] = '1';
}
resultString[N - 1] = '2';
resultString[N] = '\0'; // Null-terminate the string
} else {
// If N is odd: Assign result with N occurrences of the digit '1'
// This ensures that all digits in the resulting string are '1',
// satisfying the odd count requirement for each digit
for (int i = 0; i < N; i++) {
resultString[i] = '1';
}
resultString[N] = '\0'; // Null-terminate the string
}
}
int main(){
int N = 6; // Desired size of the string
char smallestString[N + 1]; // +1 for the null terminator
// Call the function to generate the lexicographically smallest numeric string with odd digit counts
generateSmallestNumericString(N, smallestString);
// Print the result
printf("Smallest String with length N = %d is: %s\n", N, smallestString);
return 0;
}
輸出
Smallest String with length N = 6 is: 111112
#include <iostream>
#include <string>
using namespace std;
string generateSmallestNumericString(int N) {
string resultString = ""; // Variable to store the generated string
// Check if N is even using the modulo operator (%)
if (N % 2 == 0) {
// If N is even: Assign the result with N - 1 occurrences of the digit '1' and then concatenate it with the digit '2'.
// This ensures that there are (N-1) ones and a single digit 2 in the resulting string,
// satisfying the odd count requirement for each digit
resultString.append(N - 1, '1');
resultString += '2';
} else {
// If N is odd: Assign result with N occurrences of the digit '1'
// This ensures that all digits in the resulting string are '1,
// satisfying the odd count requirement for each digit
resultString.append(N, '1');
}
return resultString; // Return the generated string
}
int main() {
int N = 6; // Desired size of the string
string smallestString = generateSmallestNumericString(N);
// Call the function to generate the lexicographically smallest numeric string with odd digit counts
cout <<"Smallest String with length N= "<<N<<" is: "<<smallestString << endl;
return 0;
}
輸出
Smallest String with length N= 6 is: 111112
public class Main {
public static String generateSmallestNumericString(int N) {
StringBuilder resultString = new StringBuilder(); // Using StringBuilder for string concatenation
// Check if N is even using the modulo operator (%)
if (N % 2 == 0) {
// If N is even: Assign the result with N - 1 occurrences of the digit '1'
// and then concatenate it with the digit '2'.
// This ensures that there are (N-1) ones and a single digit 2 in the resulting string,
// satisfying the odd count requirement for each digit
resultString.append("1".repeat(Math.max(0, N - 1)));
resultString.append('2');
} else {
// If N is odd: Assign result with N occurrences of the digit '1'
// This ensures that all digits in the resulting string are '1',
// satisfying the odd count requirement for each digit
resultString.append("1".repeat(Math.max(0, N)));
}
return resultString.toString(); // Return the generated string
}
public static void main(String[] args) {
int N = 6; // Desired size of the string
String smallestString = generateSmallestNumericString(N);
// Call the function to generate the lexicographically smallest numeric string with odd digit counts
System.out.println("Smallest String with length N = " + N + " is: " + smallestString);
}
}
輸出
Smallest String with length N = 6 is: 111112
def generate_smallest_numeric_string(N):
# Variable to store the generated string
result_string = ""
# Check if N is even using the modulo operator (%)
if N % 2 == 0:
# If N is even: Assign the result with N - 1 occurrences of the digit '1'
# and then concatenate it with the digit '2'.
# This ensures that there are (N-1) ones and a single digit 2 in the resulting string,
# satisfying the odd count requirement for each digit
result_string += '1' * (N - 1)
result_string += '2'
else:
# If N is odd: Assign result with N occurrences of the digit '1'
# This ensures that all digits in the resulting string are '1',
# satisfying the odd count requirement for each digit
result_string += '1' * N
return result_string
def main():
# Desired size of the string
N = 6
# Call the function to generate the lexicographically smallest numeric string with odd digit counts
smallest_string = generate_smallest_numeric_string(N)
print(f"Smallest String with length N = {N} is: {smallest_string}")
if __name__ == "__main__":
main()
輸出
Smallest String with length N = 6 is: 111112
複雜度分析
時間複雜度——演算法需要 O(N) 時間，其中 N 是所需字串的長度。當結果字串的長度超過 N 時，迴圈停止迭代數字。
空間複雜度——由於結果字串的長度隨 N 增加而增加，因此空間複雜度也是 O(N)
使用測試用例的解釋
Test case → N=6
提供的程式碼中的“`generateSmallestNumericString`”函式接受一個整數 N 作為輸入，並輸出一個字串，該字串表示字典序最短的 N 長度數字字串，每個數字的計數為奇數。
在將 N 設定為 6 後，我們在主函式中呼叫“`generateSmallestNumericString`”方法並將 N 作為引數傳遞。變數 smallestString 將包含返回的字串
在 generateSmallestNumericString 函式中——
由於 N 為偶數，因此 (6 % 2 == 0)，因此將執行 'if' 塊。
行 `resultString = string(N − 1, '1') + '2';` 使用字串建構函式建立一個包含 (N − 1) 個數字 '1' 的字串，然後使用連線運算子 '+' 附加數字 '2'。
因此，結果字串為“111112”，其中數字 '1' 的計數為奇數 5，數字 '2' 的計數為奇數 1，滿足問題陳述的條件。
因此，對於給定的測試用例，即 N = 6，每個數字計數為奇數的字典序最小的數字字串為“111112”。
結論
在本文中，我們介紹了一種生成字典序最短的 N 字元數字字串的方法，每個字元中的數字個數為奇數。我們提供了一個詳細的解釋和一個 C++ 實現。該演算法成功地解決了該問題，其時間複雜度與 N 成線性關係。使用此方法，我們可以為任何正整數 N 生成所需的字串。
172 次瀏覽
