解密犯罪时间 - 华为OD统一考试(C卷)

news/发布时间2024/6/16 4:21:57

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

警察在侦破一个案件时，得到了线人给出的可能犯罪时间，形如 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) continue;// 计算时间间隔int curD = (curTimes > times) ? curTimes - times : 24 * 60 - (times - curTimes);if (curD < d) {   // 找到更近的时刻hour = h;minute = m;d = curD;}}}System.out.printf("%02d:%02d%n", hour, minute);}
}

Python

def find_nearest_time(stime):# 初始化存在性数组exists = [False] * 10# 找到时间中的冒号位置pos = stime.find(":")# 遍历时间字符串，标记存在的数字for c in stime:if c.isdigit():exists[int(c)] = True# 初始化小时、分钟和最小时间间隔hour, minute, d = 0, 0, float('inf')# 计算原始时间times = int(stime[:pos]) * 60 + int(stime[pos + 1:])# 枚举所有时间，找到下一个距离当前事件最近的时刻for h in range(24):if not exists[h % 10] or not exists[h // 10]:continuefor m in range(60):cur_times = h * 60 + m# 如果分钟或小时的某一位不存在，或者时间相同，则跳过if not exists[m % 10] or not exists[m // 10] or cur_times == times:continue# 计算时间间隔cur_d = cur_times - times if cur_times > times else 24 * 60 - (times - cur_times)# 找到更近的时刻if cur_d < d:hour, minute, d = h, m, cur_d# 格式化输出结果result = "{:02d}:{:02d}".format(hour, minute)print(result)# 从标准输入读取时间字符串
stime = input().strip()# 调用函数找到最近的时间
find_nearest_time(stime)

C++

#include <bits/stdc++.h>using namespace std;int main() {string stime;cin >> stime;int pos = stime.find(":");bool exists[10];for (char c : stime) {if (isdigit(c)) exists[c - '0'] = true;}// 小时，分钟，最近的时间间隔（分钟）int hour = 0, minute = 0, d = INT_MAX;// 原始时间int times = stoi(stime.substr(0, pos)) * 60 + stoi(stime.substr(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 cur_times = h * 60 + m;// 字符未出现或时间相同if (!exists[m % 10] || !exists[m / 10] || cur_times == times) continue;// 计算时间间隔int cur_d = (cur_times > times) ? cur_times - times : 24 * 60 - (times + cur_times);if (cur_d < d) {   // 找到更近的时刻hour   = h;minute = m;d      = cur_d;}}}cout << (hour < 10 ? "0" : "") << hour << ":" << (minute < 10 ? "0" : "") << minute << endl;return 0;
}