谷歌（Google）技术面试——在线评估问题（二）

谷歌（Google）面试过程的第一步，你可能会收到一个在线评估链接。 评估有效期为 7 天，包含两个编码问题，需要在一小时内完成。 以下是一些供你练习的在线评估问题。

在本章结尾处，还提供了有关 Google 面试不同阶段的更多详细信息。

最近时刻

给定一个形如 “HH:MM” 表示的时刻 time ，利用当前出现过的数字构造下一个距离当前时间最近的时刻。每个出现数字都可以被无限次使用。

可以认为给定的字符串一定是合法的。例如， “01:34” 和 “12:09” 是合法的，“1:34” 和 “12:9” 是不合法的。

示例 1:

输入: “19:34”
输出: “19:39”
解释: 利用数字 1, 9, 3, 4 构造出来的最近时刻是 19:39，是 5 分钟之后。
结果不是 19:33 因为这个时刻是 23 小时 59 分钟之后。

示例 2:

输入: “23:59”
输出: “22:22”
解释: 利用数字 2, 3, 5, 9 构造出来的最近时刻是 22:22。
答案一定是第二天的某一时刻，所以选择可构造的最小时刻。

提示：

• time.length == 5
• time 为有效时间，
• 格式为 “HH:MM”.
• 0 <= HH < 24 0 <= MM < 60

思路一

我们可以按照以下步骤解决这个问题：

1. 将给定的时间转换为分钟数，方便后续计算。
2. 从给定的时间开始，不断增加时间，直到找到一个满足条件的时间为止：
   a. 从当前时间中提取出所有数字，并将它们放入一个集合中。
   b. 从当前时间开始依次增加时间，直到找到一个满足条件的时间：
   i. 对于小时部分和分钟部分，分别从0到9遍历，如果当前数字不在集合中，则跳过。
   ii. 如果找到一个满足条件的时间，即小时和分钟都在集合中，并且时间不等于给定时间，则返回这个时间。
3. 如果上述步骤中没有找到满足条件的时间，则说明需要跳到下一天的最小时间，即00:00。

示例代码：

def nextClosestTime(time):
    # 将给定的时间转换为分钟数
    minutes = int(time[:2]) * 60 + int(time[3:])
    
    # 从给定的时间开始，不断增加时间，直到找到一个满足条件的时间为止
    while True:
        # 从当前时间中提取出所有数字，并将它们放入一个集合中
        digits = set()
        for char in time:
            if char != ':':
                digits.add(int(char))
        
        # 从当前时间开始依次增加时间，直到找到一个满足条件的时间
        minutes = (minutes + 1) % (24 * 60)
        next_time = '{:02d}:{:02d}'.format(minutes // 60, minutes % 60)
        if all(int(char) in digits for char in next_time):
            return next_time

# 示例 1
time1 = "19:34"
print(nextClosestTime(time1)) # 输出: "19:39"

# 示例 2
time2 = "23:59"
print(nextClosestTime(time2)) # 输出: "22:22"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

这个函数首先将给定的时间转换为分钟数，然后从给定的时间开始，不断增加时间，直到找到一个满足条件的时间。在增加时间的过程中，对于每一个时间，都提取出其中的数字，并将它们放入一个集合中。然后依次增加时间，直到找到一个满足条件的时间。如果找到了满足条件的时间，则返回该时间；否则返回下一天的最小时间"00:00"。

思路二

另一种解题思路是将时间表示成两个部分：小时和分钟，并且利用循环的方式逐个增加小时和分钟来寻找最接近的时间。具体步骤如下：

1. 将给定的时间转换成小时和分钟，方便后续计算。
2. 从给定时间的下一分钟开始，逐个增加分钟和小时，直到找到满足条件的时间。
3. 如果没有找到满足条件的时间，则返回第二天的最小时间"00:00"。

代码示例：

def nextClosestTime(time):
    # 将给定的时间转换为小时和分钟
    hours, minutes = map(int, time.split(":"))
    current_time = hours * 60 + minutes
    
    # 获取时间中的所有数字，并将其放入集合中
    digits = set(int(char) for char in time if char != ':')
    
    # 从给定时间的下一分钟开始，逐个增加分钟和小时，直到找到满足条件的时间
    while True:
        current_time = (current_time + 1) % (24 * 60)
        next_hours, next_minutes = divmod(current_time, 60)
        if all(digit in digits for digit in divmod(next_hours, 10) + divmod(next_minutes, 10)):
            return '{:02d}:{:02d}'.format(next_hours, next_minutes)

# 示例 1
time1 = "19:34"
print(nextClosestTime(time1)) # 输出: "19:39"

# 示例 2
time2 = "23:59"
print(nextClosestTime(time2)) # 输出: "22:22"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这个函数首先将给定的时间转换为小时和分钟，并计算出当前时间的总分钟数。然后从下一分钟开始循环增加分钟和小时，直到找到满足条件的时间为止。在循环的每一步中，判断小时和分钟的每一位数字是否在给定的时间中出现过，如果全部符合则返回该时间。如果循环结束后仍未找到满足条件的时间，则返回第二天的最小时间"00:00"。

谷歌（Google）技术面试系列

• 谷歌（Google）技术面试概述
• 谷歌（Google）历年编程真题——数组和字符串（螺旋矩阵）
• 谷歌（Google）历年编程真题——数组和字符串（加一）
• 谷歌（Google）技术面试——在线评估问题（一）
• 谷歌（Google）技术面试——在线评估问题（二）
• 谷歌（Google）技术面试——在线评估问题（三）
• 谷歌（Google）技术面试——在线评估问题（四）
• 谷歌（Google）技术面试——全部面试流程