【華為OD】解鎖犯罪時間
題目描述
警察在偵破一個案件時，得到了線人給出的可能犯罪時間，形如"HH:MM"表示的時刻。根據警察和線人的約定，為了隱蔽，該時間是修改過的，解密規則為：利用當前出現過的數字，構造下一個距離當前時間最近的時刻，則該時間為可能的犯罪時間。每個出現數字都可以被無限次使用。
輸入描述
形如 HH:MM 的字符串，表示原始輸入
輸出描述
形如 HH:MM 的字符串，表示推理出來的犯罪時間
補充說明
- 可以保證線人給定的字符串一定是合法的。例如，"01:35"和"11:08"是合法的，"1:35"和"11:8"是不合法的
- 最近的時刻有可能在第二天
示例
輸入： 18:52
輸出： 18:55
解題思路
這道題的核心是要找到比給定時間大的最小時間，且新時間只能使用原時間中出現過的數字。
我們可以采用兩種不同的解法：
解法一：暴力枚舉法
思路分析
從給定時間開始，每次增加1分鐘，檢查新時間是否只使用了原時間中的數字。這種方法簡單直觀，但在最壞情況下可能需要遍歷較多時間。
Java實現
import java.util.*;public class Solution1 {public static String findNextTime(String time) {// 提取原時間中的所有數字Set<Character> availableDigits = new HashSet<>();for (char c : time.toCharArray()) {if (c != ':') {availableDigits.add(c);}}// 解析當前時間String[] parts = time.split(":");int hour = Integer.parseInt(parts[0]);int minute = Integer.parseInt(parts[1]);// 從下一分鐘開始尋找minute++;while (true) {// 處理時間進位if (minute >= 60) {minute = 0;hour++;if (hour >= 24) {hour = 0;}}// 格式化時間字符串String newTime = String.format("%02d:%02d", hour, minute);// 檢查新時間是否只使用了可用數字if (isValidTime(newTime, availableDigits)) {return newTime;}minute++;}}// 檢查時間字符串是否只使用了可用數字private static boolean isValidTime(String time, Set<Character> availableDigits) {for (char c : time.toCharArray()) {if (c != ':' && !availableDigits.contains(c)) {return false;}}return true;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String input = scanner.nextLine();System.out.println(findNextTime(input));scanner.close();}
}
Python實現
def find_next_time(time):# 提取原時間中的所有數字available_digits = set(c for c in time if c != ':')# 解析當前時間hour, minute = map(int, time.split(':'))# 從下一分鐘開始尋找minute += 1while True:# 處理時間進位if minute >= 60:minute = 0hour += 1if hour >= 24:hour = 0# 格式化時間字符串new_time = f"{hour:02d}:{minute:02d}"# 檢查新時間是否只使用了可用數字if is_valid_time(new_time, available_digits):return new_timeminute += 1def is_valid_time(time, available_digits):"""檢查時間字符串是否只使用了可用數字"""return all(c == ':' or c in available_digits for c in time)# 主程序
if __name__ == "__main__":input_time = input().strip()print(find_next_time(input_time))
C++實現
#include <iostream>
#include <string>
#include <set>
#include <iomanip>
#include <sstream>
using namespace std;class Solution1 {
public:// 檢查時間字符串是否只使用了可用數字bool isValidTime(const string& time, const set<char>& availableDigits) {for (char c : time) {if (c != ':' && availableDigits.find(c) == availableDigits.end()) {return false;}}return true;}string findNextTime(const string& time) {// 提取原時間中的所有數字set<char> availableDigits;for (char c : time) {if (c != ':') {availableDigits.insert(c);}}// 解析當前時間int hour = stoi(time.substr(0, 2));int minute = stoi(time.substr(3, 2));// 從下一分鐘開始尋找minute++;while (true) {// 處理時間進位if (minute >= 60) {minute = 0;hour++;if (hour >= 24) {hour = 0;}}// 格式化時間字符串stringstream ss;ss << setfill('0') << setw(2) << hour << ":" << setfill('0') << setw(2) << minute;string newTime = ss.str();// 檢查新時間是否只使用了可用數字if (isValidTime(newTime, availableDigits)) {return newTime;}minute++;}}
};int main() {string input;cin >> input;Solution1 solution;cout << solution.findNextTime(input) << endl;return 0;
}
解法二：智能構造法
思路分析
這種方法更加高效，通過分析時間的結構，智能地構造下一個有效時間：
- 首先嘗試增加分鐘的個位數
- 如果不行，嘗試增加分鐘的十位數，個位數用最小可用數字
- 如果還不行，嘗試增加小時，分鐘用最小可用數字組合
- 最后考慮跨天的情況
Java實現
import java.util.*;public class Solution2 {public static String findNextTime(String time) {// 提取并排序可用數字List<Character> digits = new ArrayList<>();for (char c : time.toCharArray()) {if (c != ':') {digits.add(c);}}Collections.sort(digits);// 解析當前時間String[] parts = time.split(":");int hour = Integer.parseInt(parts[0]);int minute = Integer.parseInt(parts[1]);// 嘗試構造下一個有效時間String result = tryConstructNext(hour, minute, digits);return result;}private static String tryConstructNext(int hour, int minute, List<Character> digits) {// 1. 嘗試增加分鐘個位String result = tryIncrementMinuteUnit(hour, minute, digits);if (result != null) return result;// 2. 嘗試增加分鐘十位result = tryIncrementMinuteTen(hour, minute, digits);if (result != null) return result;// 3. 嘗試增加小時result = tryIncrementHour(hour, digits);if (result != null) return result;// 4. 跨天處理return constructEarliestTime(digits);}// 嘗試增加分鐘個位數private static String tryIncrementMinuteUnit(int hour, int minute, List<Character> digits) {int minuteUnit = minute % 10;int minuteTen = minute / 10;for (char d : digits) {int newUnit = d - '0';if (newUnit > minuteUnit && minuteTen * 10 + newUnit < 60) {return String.format("%02d:%d%d", hour, minuteTen, newUnit);}}return null;}// 嘗試增加分鐘十位數private static String tryIncrementMinuteTen(int hour, int minute, List<Character> digits) {int minuteTen = minute / 10;for (char d : digits) {int newTen = d - '0';if (newTen > minuteTen && newTen < 6) {int minUnit = digits.get(0) - '0';return String.format("%02d:%d%d", hour, newTen, minUnit);}}return null;}// 嘗試增加小時private static String tryIncrementHour(int hour, List<Character> digits) {// 嘗試增加小時個位int hourUnit = hour % 10;int hourTen = hour / 10;for (char d : digits) {int newUnit = d - '0';if (newUnit > hourUnit && hourTen * 10 + newUnit < 24) {return String.format("%d%d:%s", hourTen, newUnit, getMinMinute(digits));}}// 嘗試增加小時十位for (char d : digits) {int newTen = d - '0';if (newTen > hourTen && newTen < 3) {int minUnit = digits.get(0) - '0';if (newTen * 10 + minUnit < 24) {return String.format("%d%d:%s", newTen, minUnit, getMinMinute(digits));}}}return null;}// 構造最早的有效時間（用于跨天）private static String constructEarliestTime(List<Character> digits) {return String.format("%s:%s", getMinHour(digits), getMinMinute(digits));}// 獲取最小有效小時private static String getMinHour(List<Character> digits) {char min = digits.get(0);for (char d : digits) {if (d <= '2') {return String.format("%c%c", d, min);}}return String.format("%c%c", min, min);}// 獲取最小有效分鐘private static String getMinMinute(List<Character> digits) {char min = digits.get(0);for (char d : digits) {if (d <= '5') {return String.format("%c%c", d, min);}}return String.format("%c%c", min, min);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String input = scanner.nextLine();System.out.println(findNextTime(input));scanner.close();}
}
Python實現
def find_next_time(time):# 提取并排序可用數字digits = sorted([c for c in time if c != ':'])# 解析當前時間hour, minute = map(int, time.split(':'))# 嘗試構造下一個有效時間return try_construct_next(hour, minute, digits)def try_construct_next(hour, minute, digits):# 1. 嘗試增加分鐘個位result = try_increment_minute_unit(hour, minute, digits)if result:return result# 2. 嘗試增加分鐘十位result = try_increment_minute_ten(hour, minute, digits)if result:return result# 3. 嘗試增加小時result = try_increment_hour(hour, digits)if result:return result# 4. 跨天處理return construct_earliest_time(digits)def try_increment_minute_unit(hour, minute, digits):"""嘗試增加分鐘個位數"""minute_unit = minute % 10minute_ten = minute // 10for d in digits:new_unit = int(d)if new_unit > minute_unit and minute_ten * 10 + new_unit < 60:return f"{hour:02d}:{minute_ten}{new_unit}"return Nonedef try_increment_minute_ten(hour, minute, digits):"""嘗試增加分鐘十位數"""minute_ten = minute // 10for d in digits:new_ten = int(d)if new_ten > minute_ten and new_ten < 6:min_unit = int(digits[0])return f"{hour:02d}:{new_ten}{min_unit}"return Nonedef try_increment_hour(hour, digits):"""嘗試增加小時"""# 嘗試增加小時個位hour_unit = hour % 10hour_ten = hour // 10for d in digits:new_unit = int(d)if new_unit > hour_unit and hour_ten * 10 + new_unit < 24:return f"{hour_ten}{new_unit}:{get_min_minute(digits)}"# 嘗試增加小時十位for d in digits:new_ten = int(d)if new_ten > hour_ten and new_ten < 3:min_unit = int(digits[0])if new_ten * 10 + min_unit < 24:return f"{new_ten}{min_unit}:{get_min_minute(digits)}"return Nonedef construct_earliest_time(digits):"""構造最早的有效時間（用于跨天）"""return f"{get_min_hour(digits)}:{get_min_minute(digits)}"def get_min_hour(digits):"""獲取最小有效小時"""min_digit = digits[0]for d in digits:if int(d) <= 2:return f"{d}{min_digit}"return f"{min_digit}{min_digit}"def get_min_minute(digits):"""獲取最小有效分鐘"""min_digit = digits[0]for d in digits:if int(d) <= 5:return f"{d}{min_digit}"return f"{min_digit}{min_digit}"# 主程序
if __name__ == "__main__":input_time = input().strip()print(find_next_time(input_time))
C++實現
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <sstream>
using namespace std;class Solution2 {
private:// 獲取最小有效分鐘string getMinMinute(const vector<char>& digits) {char minDigit = digits[0];for (char d : digits) {if (d <= '5') {return string(1, d) + string(1, minDigit);}}return string(1, minDigit) + string(1, minDigit);}// 獲取最小有效小時string getMinHour(const vector<char>& digits) {char minDigit = digits[0];for (char d : digits) {if (d <= '2') {return string(1, d) + string(1, minDigit);}}return string(1, minDigit) + string(1, minDigit);}// 構造最早的有效時間string constructEarliestTime(const vector<char>& digits) {return getMinHour(digits) + ":" + getMinMinute(digits);}// 嘗試增加分鐘個位數string tryIncrementMinuteUnit(int hour, int minute, const vector<char>& digits) {int minuteUnit = minute % 10;int minuteTen = minute / 10;for (char d : digits) {int newUnit = d - '0';if (newUnit > minuteUnit && minuteTen * 10 + newUnit < 60) {stringstream ss;ss << setfill('0') << setw(2) << hour << ":" << minuteTen << newUnit;return ss.str();}}return "";}// 嘗試增加分鐘十位數string tryIncrementMinuteTen(int hour, int minute, const vector<char>& digits) {int minuteTen = minute / 10;for (char d : digits) {int newTen = d - '0';if (newTen > minuteTen && newTen < 6) {int minUnit = digits[0] - '0';stringstream ss;ss << setfill('0') << setw(2) << hour << ":" << newTen << minUnit;return ss.str();}}return "";}// 嘗試增加小時string tryIncrementHour(int hour, const vector<char>& digits) {// 嘗試增加小時個位int hourUnit = hour % 10;int hourTen = hour / 10;for (char d : digits) {int newUnit = d - '0';if (newUnit > hourUnit && hourTen * 10 + newUnit < 24) {return to_string(hourTen) + string(1, d) + ":" + getMinMinute(digits);}}// 嘗試增加小時十位for (char d : digits) {int newTen = d - '0';if (newTen > hourTen && newTen < 3) {int minUnit = digits[0] - '0';if (newTen * 10 + minUnit < 24) {return string(1, d) + to_string(minUnit) + ":" + getMinMinute(digits);}}}return "";}// 嘗試構造下一個有效時間string tryConstructNext(int hour, int minute, const vector<char>& digits) {// 1. 嘗試增加分鐘個位string result = tryIncrementMinuteUnit(hour, minute, digits);if (!result.empty()) return result;// 2. 嘗試增加分鐘十位result = tryIncrementMinuteTen(hour, minute, digits);if (!result.empty()) return result;// 3. 嘗試增加小時result = tryIncrementHour(hour, digits);if (!result.empty()) return result;// 4. 跨天處理return constructEarliestTime(digits);}public:string findNextTime(const string& time) {// 提取并排序可用數字vector<char> digits;for (char c : time) {if (c != ':') {digits.push_back(c);}}sort(digits.begin(), digits.end());// 解析當前時間int hour = stoi(time.substr(0, 2));int minute = stoi(time.substr(3, 2));// 嘗試構造下一個有效時間return tryConstructNext(hour, minute, digits);}
};int main() {string input;cin >> input;Solution2 solution;cout << solution.findNextTime(input) << endl;return 0;
}
總結
兩種解法各有優劣：
暴力枚舉法：
- 優點：邏輯簡單，易于理解和實現
- 缺點：在最壞情況下可能需要遍歷很多時間點，效率較低
智能構造法：
- 優點：效率高，直接構造目標時間，時間復雜度更優
- 缺點：實現復雜，需要考慮多種情況
對于這道題，由于時間范圍有限（24小時），兩種方法都能很好地解決問題。在實際應用中，可以根據具體需求選擇合適的解法。
)
)
