資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告