数据结构
网络
关系数据库管理系统 (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 次浏览
