数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在给定的 HH:MM 格式时间内最大化缺失值
我们将得到一个长度为五的字符串，它表示 HH:MM 格式的时间。字符串中可能包含一些‘?’，我们必须用任何数字替换它们，使得结果是有效的时间，并且是可能的最大值。此外，给定的字符串数字将是有效的，并且‘:’将出现在字符串的精确位置。我们将使用两种方法：第一种是暴力方法，另一种是有效的方法。
示例
输入 1
Given string: 12:5? Output: 12:59
解释
我们只有一个位置需要填充，我们可以获得的最大时间是 12:59。
输入 2
Given string: ?0:?9 Output: 20:59
解释
这里有两个空位，首先，我们将关注小时部分，我们有三个选择 0、1 和 2 来填充。对于分钟部分，我们有 0 到 5 的选择，为了最大化，我们可以填充 5。
方法
我们已经看到了示例，现在让我们看看我们可以面临的不同类型的案例：
字符串有两个部分：小时部分和分钟部分。
小时部分的范围是 0 到 23，分钟部分的范围是 0 到 59。
小时部分有以下几种情况：
‘x?’，其中 x 可以是 0、1 和 2。对于 0，我们可以使用 0 作为最佳值；对于 1，我们可以选择 9 作为最佳值；对于 2，我们可以使用 3 作为最佳值。
‘?x’，其中 x 的范围是 0 到 9。如果 x 的范围是 0 到 3，那么我们可以用 2 替换它，否则 1 将是最佳值。
‘??’，因为我们必须最大化，所以我们将用 23 替换它。
分钟部分有以下几种情况：
‘x?’，其中 x 的范围是 0 到 5。9 将是我们替换 ‘?’ 的最佳选择。
‘?x’，其中 x 的范围是 0 到 9。5 将是我们替换 ‘?’ 的最佳选择。
‘??’，因为我们必须最大化，所以我们将用 59 替换它。
让我们看看实现上述步骤的代码：
示例
#include <iostream>
using namespace std;
// function to replace hours
string replaceHours(string s){
if(s[0] == '?' && s[1] == '?'){
//Both hour characters are '?'
// replace with the maximum hour we can achieve
s[0] = '2';
s[1] = '3';
}
else if(s[0] == '?'){
// if the second number of hours is in the range 0 to 3
// replace by 2
if(s[1] < 4){
s[0] = '2';
}
else{
s[0] = '1'; // otherwise replace by one
}
}
else if(s[1] == '?'){
// if the first character is '2' we can go only upto 3
if(s[0] == '2'){
s[1] = '3';
}
else{
s[1] = '9'; // else we can go for 9
}
}
return s;
}
// function to replace minutes
string replaceMinutes(string s){
if(s[3] == '?' && s[4] == '?'){
// both minutes characters are '?'
// replace with maximum minutes we can acheive
s[3] = '5';
s[4] = '9';
}
else if(s[3] == '?'){
// we can maximum get 5 here
s[3] = '5';
}
else if(s[4] == '?'){
// we can get maximum 9 here
s[4] = '9';
}
return s;
}
int main(){
string str = "2?:3?"; // given string
// calling the function for updation of the minutes
str = replaceMinutes(str);
// calling to the function for updation of the hours
str = replaceHours(str);
// printing the final answer
cout<<"The maximum time we can get by replacing ? is: "<< str<<endl;
return 0;
}
输出
The maximum time we can get by replacing ? is: 23:39
时间和空间复杂度
上述代码的时间复杂度是 O(1) 或常数，因为我们没有使用任何循环或递归调用，只是检查 if-else 条件。
上述代码的空间复杂度是 O(1)，因为我们没有使用任何额外的空间。此外，对于函数，我们传递字符串，但其大小始终为常数 5。
注意：为了使代码更美观或更易读，可以使用 switch 语句，它们不会影响时间或空间复杂度，并且会使代码更易于阅读。
此外，回溯和重新检查是一种解决方案，但这将检查每种情况，并且在这里实现效率不高。
结论
在本教程中，我们得到一个表示 24 小时制时间的字符串。字符串中有一些 ‘?’，我们必须用它们替换以获得有效最大时间，并且保证字符串中给定的字符始终导致有效时间。我们使用了 if-else 条件和两个函数来用适当的情况替换 ‘?’。上述代码的时间和空间复杂度为常数，因为我们没有使用任何循环或递归函数。
93 次浏览
