LeetCode 681. Next Closest Time 最近时刻 / LintCode 862. 下一个最近的时间 (C++/Java)
silentteller 人气:0题目:
给定一个"HH:MM"格式的时间,重复使用这些数字,返回下一个最近的时间。每个数字可以被重复使用任意次。
保证输入的时间都是有效的。例如,"01:34","12:09" 都是有效的,而"1:34","12:9"都不是有效的时间。
样例
样例 1:
输入: "19:34"
输出: "19:39"
解释:
从1,9,3,4中选出的下一个最近的时间是19:39,它是五分钟后。
答案不是19:33,因为它是23小时59分钟后。
样例 2:
输入: "23:59"
输出: "22:22"
解释: 可以假设所返回的时间是第二天的时间,因为它在数字上小于给定的时间。
分析:
LeetCode681需要订阅才可以查看,好在LintCode上有相同的题目。
给定一个"HH:MM"格式的时间,利用所有数字拼凑出新的时间(可以重复),使其成为下一个最近的时间,且保证时间有效。
特例是像"00:00"的最近时间就是"00:00",实际上是过了24小时。
可以将每一位的数字替换成给的时间内的四个数字(最多4个),总计最多4^4种情况,同时检验时间是否有效,小时小于24,分钟小于60。
然后计算拼出的时间和原时间的差值,求得最小的即可,注意求差时容易出现负值,要处理一下。
程序:
C++
class Solution { public: /** * @param time: the given time * @return: the next closest time */ string nextClosestTime(string &time) { // write your code here vector<int> number {time[0]-'0', time[1]-'0', time[3]-'0', time[4]-'0'} ; vector<int> currTime(4, 0); int hour = number[0]*10 + number[1]; int minute = number[2]*10 + number[3]; int times = toMinute(hour, minute); int bestTime = times; dfs(number, 0, currTime, times, bestTime); string s = to_string(bestTime/60) + ":" + to_string(bestTime%60); char buff[5]; sprintf(buff, "%02d:%02d", bestTime / 60, bestTime % 60); return string(buff); } void dfs(vector<int> &number, int deep, vector<int>& currTime, int times, int& bestTime){ if(deep == 4){ if(currTime[0]*10 + currTime[1] > 23 || currTime[2]*10 + currTime[3] > 59) return; int currMinutes = toMinute(currTime[0]*10 + currTime[1], currTime[2]*10 + currTime[3]); if(diff(times, currMinutes) < diff(times, bestTime)){ bestTime = currMinutes; } return; } for(int i:number){ currTime[deep] = i; dfs(number, deep+1, currTime, times, bestTime); } return; } int toMinute(int hour, int minute){ return hour*60 + minute; } int diff(int time1, int time2){ if(time1 == time2) return 1440; return ((1440 - time1) + time2) % 1440; } };
加载全部内容