数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学替换字符后可获得的最晚时间
“替换字符后可获得的最晚时间”子任务应用于输入字符串，其中字符串表示为12小时制时间，当最大数量的字符被“?”替换时。
在12小时制时间“HH:MM”中，HH属于集合{00, 01, …, 10, 11}，MM也属于集合{00, 01, …, 59}。最早的时间是00:00，最晚的时间是11:59。问题陈述
在这个问题陈述中，目标是将字符串s中的所有“?”字符替换为数字，以形成格式为“HH:MM”的最新有效时间。
示例场景1
Input: s="03:??"
Output: 03:59
将?替换为5和9以获得最晚有效时间03:59。
示例场景2
Input: s="0?:3?"
Output: 09:39
将?替换为9和9以获得最晚有效时间09:39。
示例场景3
Input: s="1?:22"
Output: 11:22
将?替换为1以获得最晚有效时间11:22。
时间复杂度
“替换字符后可获得的最晚时间”的时间复杂度为O(1)。
要使用各种编程语言解决此问题，请使用以下方法。
- 贪心算法
- 暴力法
贪心算法
示例
以下是贪心算法，它涉及将时间字符串中的每个“?”替换为仍然构成有效12小时制时间的最大可能数字。这确保我们获得最晚的可能时间。
#include <iostream>
#include <string>
using namespace std;
string latestTime(string s) {
if (s[0] == '?') s[0] = (s[1] <= '1' || s[1] == '?') ? '1' : '0';
if (s[1] == '?') s[1] = (s[0] == '1') ? '1' : '9';
if (s[3] == '?') s[3] = '5';
if (s[4] == '?') s[4] = '9';
return s;
}
int main() {
string s = "1?:?0";
cout << "Latest time = " << latestTime(s) << endl;
return 0;
}
输出
Latest time = 11:50
public class LatestTime {
public static String latestTime(String s) {
char[] time = s.toCharArray();
if (time[0] == '?') time[0] = (time[1] <= '1' || time[1] == '?') ? '1' : '0';
if (time[1] == '?') time[1] = (time[0] == '1') ? '1' : '9';
if (time[3] == '?') time[3] = '5';
if (time[4] == '?') time[4] = '9';
return new String(time);
}
public static void main(String[] args) {
String s = "1?:?0";
System.out.println("Latest time = " + latestTime(s));
}
}
输出
Latest time = 11:50
def latest_time(s):
time = list(s)
if time[0] == '?':
time[0] = '1' if time[1] <= '1' or time[1] == '?' else '0'
if time[1] == '?':
time[1] = '1' if time[0] == '1' else '9'
if time[3] == '?':
time[3] = '5'
if time[4] == '?':
time[4] = '9'
return ''.join(time)
s = "1?:?0"
print(f"Latest time = {latest_time(s)}")
输出
Latest time = 11:50
暴力法
示例
暴力法用于生成所有可能的12小时制有效时间，并检查哪个时间与包含“?”字符的给定模式匹配。
#include <iostream>
#include <string>
using namespace std;
bool isValidTime(const string& time) {
int hours = stoi(time.substr(0, 2));
int minutes = stoi(time.substr(3, 2));
return hours >= 0 && hours <= 11 && minutes >= 0 && minutes <= 59;
}
string latestTime(string s) {
for (int h = 11; h >= 0; --h) {
for (int m = 59; m >= 0; --m) {
string hh = (h < 10 ? "0" : "") + to_string(h);
string mm = (m < 10 ? "0" : "") + to_string(m);
string candidate = hh + ":" + mm;
bool match = true;
for (int i = 0; i < 5; ++i) {
if (s[i] != '?' && s[i] != candidate[i]) {
match = false;
break;
}
}
if (match) return candidate;
}
}
return "";
}
int main() {
string s = "1?:?0";
cout << "Latest time = " << latestTime(s) << endl;
return 0;
}
输出
Latest time = 11:50
public class LatestTime {
public static boolean isValidTime(String time) {
int hours = Integer.parseInt(time.substring(0, 2));
int minutes = Integer.parseInt(time.substring(3, 5));
return hours >= 0 && hours <= 11 && minutes >= 0 && minutes <= 59;
}
public static String latestTime(String s) {
for (int h = 11; h >= 0; --h) {
for (int m = 59; m >= 0; --m) {
String hh = (h < 10 ? "0" : "") + h;
String mm = (m < 10 ? "0" : "") + m;
String candidate = hh + ":" + mm;
boolean match = true;
for (int i = 0; i < 5; ++i) {
if (s.charAt(i) != '?' && s.charAt(i) != candidate.charAt(i)) {
match = false;
break;
}
}
if (match) return candidate;
}
}
return "";
}
public static void main(String[] args) {
String s = "1?:?0";
System.out.println("Latest time = " + latestTime(s));
}
}
输出
Latest time = 11:50
import re
def is_valid_time(time):
hours, minutes = map(int, time.split(':'))
return 0 <= hours <= 11 and 0 <= minutes <= 59
def latest_time(s):
for hours in range(11, -1, -1):
for minutes in range(59, -1, -1):
hh = f"{hours:02d}"
mm = f"{minutes:02d}"
candidate = f"{hh}:{mm}"
match = True
for i in range(5):
if s[i] != '?' and s[i] != candidate[i]:
match = False
break
if match:
return candidate
return ""
s = "1?:?0"
print(f"Latest time: {latest_time(s)}")
输出
Latest time = 11:50
更新于：2024年7月23日
53 次浏览
广告