LeetCode 681. Next Closest Time 最近时刻 / LintCode 862. 下一个最近的时间 (C++/Java)

题目：

给定一个"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[]-'', time[]-'', time[]-'', time[]-''} ;

        vector<int> currTime(, );

        int hour = number[]* + number[];

        int minute = number[]* + number[];

        int times = toMinute(hour, minute);

        int bestTime = times;

        dfs(number, , currTime, times, bestTime);

        string s = to_string(bestTime/) + ":" + to_string(bestTime%);

        char buff[];

        sprintf(buff, "%02d:%02d", bestTime / , bestTime % );

        return string(buff);

    }

    void dfs(vector<int> &number, int deep, vector<int>& currTime, int times, int& bestTime){

        if(deep == ){

            if(currTime[]* + currTime[] >  || currTime[]* + currTime[] > )

                return;

            int currMinutes = toMinute(currTime[]* + currTime[], currTime[]* + currTime[]);

            if(diff(times, currMinutes) < diff(times, bestTime)){

                bestTime = currMinutes;

            }

            return;

        }

        for(int i:number){

            currTime[deep] = i;

            dfs(number, deep+, currTime, times, bestTime);

        }

        return;

    }

    int toMinute(int hour, int minute){

        return hour* + minute;

    }

    int diff(int time1, int time2){

        if(time1 == time2)

            return ;

        return (( - time1) + time2) % ;

    }

};

Java

public class Solution {

    /**

     * @param time: the given time

     * @return: the next closest time

     */

    public String nextClosestTime(String time) {

        // write your code here

        char tTime[] = time.toCharArray();

        int[] number = new int[]{tTime[0]-'0', tTime[1]-'0', tTime[3]-'0', tTime[4]-'0'};

        int[] currTime = new int[4];

        int hour = number[0]*10 + number[1];

        int minute = number[2]*10 + number[3];

        int times = toMinute(hour, minute);

        bestTime = times;

        dfs(number, currTime, 0, times);

        String res = String.format("%02d:%02d", bestTime/60, bestTime%60);

        return res;

    }

    public void dfs(int[] number, int[] currTime, int deep, int times){

        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 = 0; i < 4; ++i){

            currTime[deep] = number[i];

            dfs(number, currTime, deep+1, times);

        }

        return;

    }

    public int toMinute(int hour, int minute){

        return hour*60 + minute;

    }

    public int diff(int time1, int time2){

        if(time1 == time2)

            return 1440;

        return ((1440 - time1) + time2) % 1440;

    }

    private int bestTime;

}

巴特西

LeetCode 681. Next Closest Time 最近时刻 / LintCode 862. 下一个最近的时间 (C++/Java)

题目：

样例

分析：

程序：

最新文章

热门文章