DeepSeek LintCode 下一个最近的时间 Java实现

稚辉君.MCA.P9.JAVA

181人浏览 · 2026-02-08 08:52:16

稚辉君.MCA.P9.JAVA · 2026-02-08 08:52:16 发布

根据你的要求，我为你提供了LintCode“下一个最近的时间”问题的详细Java解答。这道题目的核心是找到一个距离当前时间“最近”的下一时间，要求新时间的每一位数字都必须来自原时间字符串中已有的数字。

### **暴力解法 (模拟)**
这是最直观的解法。将时间换算成分钟，然后从下一分钟开始循环，每次加1分钟，判断新时间是否由原始数字构成，直到找到第一个合法的结果。

```java
public class Solution {
public String nextClosestTime(String time) {
int hour = Integer.parseInt(time.substring(0, 2));
int minute = Integer.parseInt(time.substring(3));
// 循环寻找下一个合法时间
while (true) {
// 模拟时间流逝，每次增加1分钟
if (++minute == 60) {
minute = 0;
if (++hour == 24) {
hour = 0;
}
}
// 将新的时、分格式化为 HH:MM 字符串
String newTime = String.format("%02d:%02d", hour, minute);
// 检查新时间是否全部由原始时间的数字构成
boolean isValid = true;
for (int i = 0; i < newTime.length(); i++) {
char c = newTime.charAt(i);
if (time.indexOf(c) == -1) { // 如果原始字符串中不存在该字符
isValid = false;
break;
}
}
if (isValid) {
return newTime;
}
}
}
}
```

### **深度优先搜索 (DFS) 解法**
另一种方法是枚举所有由原时间数字构成的、合法的未来时间，然后找出差值最小的那一个。

```java
public class Solution {
// 用于存储所有可能的合法时间（以分钟计）
private List<Integer> candidates = new ArrayList<>();
// 存储原始时间的四个数字
private int[] digits;

public String nextClosestTime(String time) {
// 1. 提取并存储原始数字
digits = new int[]{
time.charAt(0) - '0',
time.charAt(1) - '0',
time.charAt(3) - '0',
time.charAt(4) - '0'
};
// 2. 将当前时间转换为分钟数
int originalMinute = toMinute(digits[0] * 10 + digits[1], digits[2] * 10 + digits[3]);
// 3. 通过DFS枚举所有可能的新时间组合
dfs(0, new int[4], originalMinute);
// 4. 找出与当前时间差值最小的未来时间
int closestMinute = originalMinute;
int minDiff = Integer.MAX_VALUE;
for (int cand : candidates) {
int diff = (cand - originalMinute + 24 * 60) % (24 * 60); // 处理跨天
if (diff > 0 && diff < minDiff) {
minDiff = diff;
closestMinute = cand;
}
}
// 如果没找到未来的时间，说明最近的时间是明天重复当前时间（原题要求返回自身）
if (closestMinute == originalMinute) {
return time;
}
// 将分钟数转换回“HH:MM”格式
return String.format("%02d:%02d", closestMinute / 60, closestMinute % 60);
}

// DFS递归函数
private void dfs(int index, int[] curTime, int originalMinute) {
if (index == 4) {
// 当构造出4个数字时，检查合法性
int hour = curTime[0] * 10 + curTime[1];
int minute = curTime[2] * 10 + curTime[3];
if (hour < 24 && minute < 60) {
int totalMinute = toMinute(hour, minute);
candidates.add(totalMinute);
}
return;
}
// 每一位数字都可以从原始数字集中选择
for (int digit : digits) {
curTime[index] = digit;
dfs(index + 1, curTime, originalMinute);
}
}

// 辅助函数：将小时和分钟转换为总分钟数
private int toMinute(int hour, int minute) {
return hour * 60 + minute;
}
}
```

### **算法对比**
为了帮你更好地理解，下表对比了两种主要解法的核心思路和优缺点：

### **总结与建议**

- **首选暴力解法**：对于这道题，暴力解法（模拟）通常是**最佳选择**。虽然最坏需要1440次循环，但这是一个固定的常数，在算法竞赛和面试中完全可以接受，且代码简洁、逻辑清晰。
- **理解DFS思路**：DFS解法展示了另一种解决问题的视角，即通过**枚举所有可能状态**来寻找最优解，这种思路在解决其他组合类问题时很有用。
- **边界情况**：请注意，题目要求返回“下一个最近的时间”，这隐含了时间可以**跨越到第二天**。如果给定的时间数字构成的最近时间就是其自身（如“11:11”），按照题意直接返回该时间即可。

你可以先尝试理解并实现暴力解法，因为它更直观。如果遇到问题或有特殊需求（例如需要分析所有可能的组合），可以再研究DFS解法。

如果你需要我解释代码中的某一部分，或者想了解如何测试这两种解法，我可以为你提供进一步的说明。