解密犯罪时间 - 华为OD统一考试(C卷)
OD统一考试(C卷)
分值: 100分
题解: Java / Python / C++
题目描述
警察在侦破一个案件时,得到了线人给出的可能犯罪时间,形如 HH:MM
表示的时刻。
根据警察和线人的约定,为了隐蔽,该事件是修改过的,解密规则为:
利用当前出现过的数字,构造下一个距离当前事件最近的时刻,则该时间为可能的犯罪的时间。每个数字都可以被无限次使用。
输入描述
形如 HH:SS
字符串,表示原始输入。
输出描述
HH:SS
字符串,表示推理处理的犯罪时间。
备注:
- 可以保证现任给定的字符串一定是合法的,例如,"01:3501:35" 和 "11:0811:08" 是合法的,"1:351:35"和"11:811:8" 是不合法的。
- 最近的时刻可能在第二天。
示例1
输入:
20:12
输出:
20:20
示例2
输入:
23:59
输出:
22:22
题解
这个问题可以分为以下几个步骤来解决:
- 记录已经出现的数字: 遍历输入的时间字符串,记录出现过的数字。这里可以使用一个长度为10的布尔数组
exists
,用于标记数字0到9是否出现过。- 计算原始时间: 将输入的时间字符串转换为分钟表示,方便后续的计算。
- 枚举所有时间: 使用两层循环枚举所有可能的小时和分钟,然后计算对应的分钟数,得到当前时间点。
- 判断当前时间点是否符合条件: 判断当前小时和分钟的每一位数字是否都在已经出现过的数字中。如果有任何一个数字未出现,说明这个时间点不符合条件,直接跳过。
- 计算时间间隔: 计算当前时间点与原始时间的时间间隔,考虑了第二天的情况。
- 找到最近的时刻: 通过比较时间间隔找到最近的时刻,更新最近时刻的小时、分钟和时间间隔。
- 格式化输出结果: 最终输出找到的最近时刻。
Java
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String stime = scanner.next();
int pos = stime.indexOf(":");
// 记录已经出现的数字
boolean[] exists = new boolean[10];
for (char c : stime.toCharArray()) {
if (Character.isDigit(c)) {
exists[c - '0'] = true;
}
}
// 小时,分钟,最近的时间间隔(分钟)
int hour = 0, minute = 0, d = Integer.MAX_VALUE;
// 原始时间
int times = Integer.parseInt(stime.substring(0, pos)) * 60 + Integer.parseInt(stime.substring(pos + 1));
// 枚举所有时间,找到下一个距离当前事件最近的时刻
// - 如果时间点中有字符未出现,则不考虑该时间点,因为该时间点已经不可能是答案了
// - 如果时间点中有字符出现:
// - 如果时间相同,则不考虑该时间点,因为该时间点已经不可能是答案了
// - 如果时间不同,则考虑该时间点,因为该时间点可能是答案了,但是要判断当天还是下一天
for (int h = 0; h < 24; h++) {
if (!exists[h % 10] || !exists[h / 10]) continue;
for (int m = 0; m < 60; m++) {
int curTimes = h * 60 + m;
// 字符未出现或时间相同
if (!exists[m % 10] || !exists[m / 10] || curTimes == times) c
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试真题题解 文章被收录于专栏
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答