有LeetCode算法/华为OD考试扣扣交流群可加 948025485 可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1336了解算法冲刺训练
文章目录
题目描述与示例题目描述输入描述输出描述补充说明示例输入输出
解题思路为什么可以枚举所有时间如何获得下一个时刻如何判断是否仅用了出现过的字符
代码PythonJavaC++时空复杂度
华为OD算法/大厂面试高频题算法练习冲刺训练
题目描述与示例
题目描述
警察在侦破一个案件时，得到了线人给出的可能犯罪时间，形如“HH:MM” 表示的时刻。根据警察和线人的约定，为了隐蔽，该时间是修改过的，解密规则为：利用当前出现过的数字，构造下一个距离当前时间最近的时刻，则该时间为可能的犯罪时间。每个出现数字都可以被无限次使用。
输入描述
形如HH:MM的字符串，表示原始输入
输出描述
形如HH:MM的字符串，表示推理出来的犯罪时间
补充说明
可以保证线人给定的字符串一定是合法的。例如，“01:35”和“11:08”是合法的，“1:35”和“11:8”是不合法的最近的时刻有可能在第二天
示例
输入
18:52
输出
18:55
解题思路
为什么可以枚举所有时间
一天有24小时，一小时有60分钟，所有时刻的个数一共为24*60 = 1440。
枚举所有的时刻最多只需要O(N)的时间复杂度，其中N = 1440，是可以接受的。
因此我们可以枚举从给定时刻HH:MM开始的所有时刻，直到发现一个时刻用到了HH:MM中的所有数字，那么该时刻一定是距离HH:MM最近的下一个时刻。
如何获得下一个时刻
假设已知当前时刻为HH:MM，我们可以通过以下过程来枚举下一个时刻。
若MM != 59，那么下一个时刻为HH:MM+1若MM == 59，则还需要讨论HH。
若HH != 23，则下一个时刻为HH+1:00若HH == 23，即当前时刻为23:59，则下一个时刻为00:00
因此，我们很容易构造出函数get_next_time()，以获得下一个时刻。
为了方便后续过程，传入和传出的参数可以设计为一个长度为4的列表lst。
其中lst[0]和lst[1]能够构成HH，lst[2]和lst[3]能够构成MM。
由于最终要转化为一个类似的列表进行返回，可以使用求余和整除操作，来获得各位的结果。
def get_next_time(lst):
HH = int(lst[0] + lst[1])
MM = int(lst[2] + lst[3])
if MM < 59:
new_HH = HH
new_MM = MM + 1
else:
new_MM = 0
if HH < 23:
new_HH = HH + 1
else:
new_HH = 0
# 构建新数组
ans = ["0"] * 4
ans[0] = str(new_HH // 10)
ans[1] = str(new_HH % 10)
ans[2] = str(new_MM // 10)
ans[3] = str(new_MM % 10)
return ans
本函数涉及到较多的int和str类型的相互转化过程，较为基础但需要细心。
如何判断是否仅用了出现过的字符
在拿到最初的时刻HH:MM时，我们就可以先把这个时刻中出现的所有数字型字符储存在一个哈希集合nums_used_set中，即
s = input()
lst = [s[0], s[1], s[3], s[4]]
nums_used_set = set(lst)
然后我们在循环中持续地获得下一个时刻对应的lst，当lst中的所有字符都出现在了nums_used_set中，可以说明当前lst所代表的时刻，就是距离最初HH:MM最近的下一个时刻了。即
while True:
lst = get_next_time(lst)
if all(ch in nums_used_set for ch in lst):
print(f"{lst[0]}{lst[1]}:{lst[2]}{lst[3]}")
break
代码
Python
# 题目：【模拟】2023C-解密犯罪时间
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：模拟
# 代码看不懂的地方，请直接在群上提问
# 根据长度为4的数字型字符数组lst
# 获得下一个时刻的函数
def get_next_time(lst):
# HH和MM均为int型变量
HH = int(lst[0] + lst[1])
MM = int(lst[2] + lst[3])
if MM < 59:
new_HH = HH
new_MM = MM + 1
else:
new_MM = 0
if HH < 23:
new_HH = HH + 1
else:
new_HH = 0
# 构建新数组
ans = ["0"] * 4
ans[0] = str(new_HH // 10)
ans[1] = str(new_HH % 10)
ans[2] = str(new_MM // 10)
ans[3] = str(new_MM % 10)
return ans
# 输入原始字符串，长度为5
s = input()
# 分别获得四个数字型字符，表示初始时刻
# s[0]和s[1]表示HH，s[3]和s[4]表示MM
lst = [s[0], s[1], s[3], s[4]]
# 获得这些数字所对应的哈希集合
nums_used_set = set(lst)
# 持续循环
while True:
# 获得下一个时刻对应的列表lst
lst = get_next_time(lst)
# 若lst中所有字符均在哈希集合中出现过，说明当前lst对应下一个时刻
if all(ch in nums_used_set for ch in lst):
# 输出时刻字符串，并退出循环
print(f"{lst[0]}{lst[1]}:{lst[2]}{lst[3]}")
break
Java
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
// 根据长度为4的数字型字符数组lst，获得下一个时刻的函数
public static char[] getNextTime(char[] lst) {
int HH = Integer.parseInt("" + lst[0] + lst[1]);
int MM = Integer.parseInt("" + lst[2] + lst[3]);
int new_HH, new_MM;
if (MM < 59) {
new_HH = HH;
new_MM = MM + 1;
} else {
new_MM = 0;
if (HH < 23) {
new_HH = HH + 1;
} else {
new_HH = 0;
}
}
// 构建新数组
char[] ans = new char[4];
ans[0] = (char) (new_HH / 10 + '0');
ans[1] = (char) (new_HH % 10 + '0');
ans[2] = (char) (new_MM / 10 + '0');
ans[3] = (char) (new_MM % 10 + '0');
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
char[] s = input.toCharArray();
char[] lst = {s[0], s[1], s[3], s[4]};
Set
for (char ch : lst) {
numsUsedSet.add(ch);
}
// 持续循环
while (true) {
// 获得下一个时刻对应的数组lst
lst = getNextTime(lst);
// 若lst中所有字符均在哈希集合中出现过，说明当前lst对应下一个时刻
boolean allIn = true;
for (char ch : lst) {
if (!numsUsedSet.contains(ch)) {
allIn = false;
break;
}
}
if (allIn) {
// 输出时刻字符串，并退出循环
System.out.println(lst[0] + "" + lst[1] + ":" + lst[2] + "" + lst[3]);
break;
}
}
}
}
C++
#include
#include
#include
using namespace std;
// 根据长度为4的数字型字符数组lst，获得下一个时刻的函数
vector
int HH = stoi(string(1, lst[0]) + string(1, lst[1]));
int MM = stoi(string(1, lst[2]) + string(1, lst[3]));
int new_HH, new_MM;
if (MM < 59) {
new_HH = HH;
new_MM = MM + 1;
} else {
new_MM = 0;
if (HH < 23) {
new_HH = HH + 1;
} else {
new_HH = 0;
}
}
// 构建新数组
vector
ans[0] = static_cast
ans[1] = static_cast
ans[2] = static_cast
ans[3] = static_cast
return ans;
}
int main() {
string s;
cin >> s;
vector
unordered_set
// 持续循环
while (true) {
// 获得下一个时刻对应的数组lst
lst = getNextTime(lst);
// 若lst中所有字符均在哈希集合中出现过，说明当前lst对应下一个时刻
bool allIn = true;
for (char ch : lst) {
if (numsUsedSet.find(ch) == numsUsedSet.end()) {
allIn = false;
break;
}
}
if (allIn) {
// 输出时刻字符串，并退出循环
cout << lst[0] << lst[1] << ":" << lst[2] << lst[3] << endl;
break;
}
}
return 0;
}
时空复杂度
时间复杂度：O(N)。循环所需时间复杂度，其中N最大为1440
空间复杂度：O(1)。仅需常数级别的空间复杂度，哈希集合最大长度不会超过4
华为OD算法/大厂面试高频题算法练习冲刺训练
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务300+同学成功上岸！ 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！ 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 & OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
相关阅读
您阅读本篇文章共花了：
发表评论