【华为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;
}