- 正确答案：给定一个由4个数字组成的数组，要求从中选出4个数字（每个数字只能用一次）组成一个合法的24小时制时间，格式为 HH:MM，且要使得这个时间尽可能大。如果无法组成合法时间，返回空字符串。例如输入 [1,2,3,4]，输出应为 "23:41"。 - 解答思路： 1. 题目限制明确：时间必须是有效的24小时制时间，即小时部分在 00 到 23 之间，分钟部分在 00 到 59 之间。 2. 输入只有4个数字，我们需要从这4个数字中进行全排列，枚举所有可能的四位数时间组合。 3. 对每一个排列，判断其是否构成有效时间： - 前两位作为小时 H1H2，需满足 0 <= H1H2 <= 23 - 后两位作为分钟 M1M2，需满足 0 <= M1M2 <= 59 4. 在所有有效的时间中，选择最大的那个时间作为结果。 5. 由于目标是“最大时间”，我们可以将所有有效时间转换为总分钟数（如 HH*60 + MM），然后取最大值，最后再转回 HH:MM 格式。 - 深度知识讲解：考察点包括： 1. **全排列生成**：需要掌握如何对一个数组的所有元素进行全排列。可以使用递归回溯或标准库函数（如 Python 的 itertools.permutations）。在面试中“手撕”代码通常要求自己实现排列生成逻辑。 2. **剪枝优化意识**：虽然本题数据规模小（仅4个数字，最多24种排列），但可以思考是否提前剪枝。然而由于目标是“最大时间”，不能轻易跳过某些分支，因此暴力枚举更稳妥。 3. **时间有效性判断**：关键在于理解时间的约束条件： - 小时范围 [00, 23] - 分钟范围 [00, 59] - 特别注意：第一位小时数字 H1 只能是 0、1 或 2；若 H1 == 2，则 H2 最大只能是 3。 4. **字符串与整数转换**：需要将数字组合成整数用于比较，并格式化为带前导零的字符串输出。 5. **边界处理**：当无合法时间时返回空字符串。底层数据结构和算法： - 使用数组或列表存储输入数字。 - 使用回溯法生成全排列（深度优先搜索 + 状态重置）。 - 使用整型变量表示时间（便于比较大小）。 - 时间复杂度：O(1)，因为固定4个数字，最多4! = 24种排列，属于常数级别。 - 空间复杂度：O(1)，递归栈深度最多4层。 - 扩展知识：此类问题属于“受限组合优化”问题，在实际应用中常见于： - 排班系统中的时间构造 - 日志分析中从碎片信息恢复时间戳 - 密码学或CTF竞赛中的时间推断题进阶变体可能包括： - 给定更多数字，选4个组成最大时间（此时需考虑选择+排列） - 构造最近的未来时间（相对于当前时间） - 允许重复使用数字（则策略变为贪心） - 伪代码（基于回溯生成全排列）： ``` function largestTimeFromDigits(A): best = -1 used = [false, false, false, false] current = array of size 4 function backtrack(depth): if depth == 4: hour = current[0]*10 + current[1] minute = current[2]*10 + current[3] if hour < 24 and minute < 60: totalMinutes = hour * 60 + minute if totalMinutes > best: best = totalMinutes else: for i from 0 to 3: if not used[i]: used[i] = true current[depth] = A[i] backtrack(depth + 1) used[i] = false call backtrack(0) if best == -1: return "" else: hour = best // 60 minute = best % 60 return format as "%02d:%02d" % (hour, minute) ``` - 实际可运行的Python风格代码（适合面试书写）： def largestTimeFromDigits(A): import itertools max_time = -1 # 生成所有可能的排列 for perm in itertools.permutations(A): hour = perm[0] * 10 + perm[1] minute = perm[2] * 10 + perm[3] if hour < 24 and minute < 60: total_minutes = hour * 60 + minute if total_minutes > max_time: max_time = total_minutes if max_time == -1: return "" else: hour_str = str(max_time // 60).zfill(2) min_str = str(max_time % 60).zfill(2) return f"{hour_str}:{min_str}" 注意：zfill(2) 是为了保证两位数格式，也可以用 %02d 或 .format() - 如果不允许使用 itertools，手动实现回溯版本： def largestTimeFromDigits(A): max_time = [-1] # 使用列表以便内部函数修改 path = [] used = [False] * 4 def backtrack(): if len(path) == 4: hour = path[0]*10 + path[1] minute = path[2]*10 + path[3] if hour < 24 and minute < 60: total = hour * 60 + minute if total > max_time[0]: max_time[0] = total return for i in range(4): if not used[i]: used[i] = True path.append(A[i]) backtrack() path.pop() used[i] = False backtrack() if max_time[0] == -1: return "" h, m = divmod(max_time[0], 60) return f"{h:02d}:{m:02d}" 上述代码清晰表达了回溯过程，适合在白板上书写。 - 关键细节提醒： - 不要忘记前导零格式化（如 05:09） - 注意 hour 和 minute 的合法性检查顺序 - 初始化 max_time 为 -1 表示无效 - 回溯时状态恢复必须完整（used 和 path）总结：该题虽属简单难度，但综合考察了排列生成、约束判断、格式化输出等基本功，是典型的校园招聘算法面试题。重点在于代码鲁棒性和边界处理。

字节秋招字节测试开发一面面经

全站热榜

创作者周榜