681. Next Closest Time

681. Next Closest Time

Given a time represented in the format “HH:MM”, form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.

Example 1:
Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.  It is not 19:33, because this occurs 23 hours and 59 minutes later.1234

Example 2:
Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.1234

My Solutions：

这道题给了一个时间点，求最近的下一个时间点，规定了不能产生新的数字，当下个时间点超过零点时，就当第二天的时间。

为了找到下一个时间点，从分钟开始换数字，而且换的数字要是存在的数字，那么先要做的就是统计当前时间点中的数字，由于可能有重复数字的存在，用一个伪哈希表来存给的时间的数字。

下面就从低位分钟开始换数字了，如果低位分钟上的数字已经是最大的数字了，那么说明要转过一轮了，就要把低位分钟上的数字换成最小的那个数字；否则就将低位分钟上的数字换成下一个数字。换一种说法就是，去哈希表里找有没有比给定的这个数大而且合法的数字，如果有则返回带有这个合法数字的新的string；如果没有，就把这一位设为哈希表里的最小值。然后再看高位分钟上的数字，同理，如果高位分钟上的数字已经是最大的数字，或则下一个数字大于5，那么直接换成最小值；否则就将高位分钟上的数字换成下一个数字。

对于小时位上的数字也是同理。当小时高位不为2的时候，低位可以是0~9，而当高位为2时，低位需要小于等于3。对于小时高位，其必须要小于等于2。

时间复杂度: O(4*10)

空间复杂度: O(10)

public String nextClosestTime(String time) {
        char[] t = time.toCharArray(), result = new char[4];
        int[] list = new int[10]; //数字集合
        char min = '9'; //记录最小的数
        
        for (char c : t) {
            if (c == ':') continue;
            list[c - '0']++;
            if (c < min) {
                min = c;
            }
        }
        
        //分钟最低位，如果有比最低位大的数字，直接返回
        for (int i = t[4] - '0' + 1; i <= 9; i++) {
            if (list[i] != 0) {
                t[4] = (char)(i + '0');
                return new String(t);
            }
        }
        //如果没有，则把第四位设为最小值
        t[4] = min;
        
        //分钟高位，如果有比最低位大的数字且此数字<=5，直接返回
        for (int i = t[3] - '0' + 1; i <= 5; i++) {
            if (list[i] != 0) {
                t[3] = (char)(i + '0');
                return new String(t);
            }
        }
        //如果没有，则把第三位设为最小值
        t[3] = min;
        
        //检查时钟第一位是0/1 还是2。如果是0/1,stop是9，因为最多到09或19；不然stop是3，最多到23
        int stop = t[0] < '2' ? 9 : 3;
        
        for (int i = t[1] - '0' + 1; i <= stop; i++) {
            if (list[i] != 0) {
                t[1] = (char)(i + '0');
                return new String(t);
            }
        }
        t[1] = min;
        
        for (int i = t[0] - '0' + 1; i <= 2; i++) {
            if (list[i] != 0) {
                t[0] = (char)(i + '0');
                return new String(t);
            }
        }
        t[0] = min;
        
        return new String(t);
}

原题 -> closest time after + 不可重复使用数字 -> closest time before + （可重复使用数字 or 不可重复使用数字）

Follow Up 1:

如果是closest time after + 不可重复使用数字。

e.g，

19：34 ==> 19:43，情况1

16：29 ==> 19:26，情况2

23：26 ==> 22:36 next day，情况2

15：58 ==> 18:58 ，情况2

22：23 ==> 23:22，情况2

12：49 ==> 21:49，情况3

19：29 ==> 19:29

23：55 ==> 23:55

先看分钟，如果可以只靠移动分钟数改变最简单。需要满足的条件是十位数小于个位数且个位数<=5。不然的话必然需要移动时钟数。--情况1

再看时钟。如果第一个是0/1，低位数最多是9；如果第一个是2，低位数最多是3。如果分钟数两数中，有比时钟低位数大的数，且分钟数小于等于9/3, 选择分钟数里较小的数放在低位。剩下两个数小一点的数必须小于等于5。--情况2

如果不满足以上条件，但是时钟高位是1，且后面的数字里有2的，以及剩余两个数字有一个小于等于5的，时钟变成21， 剩余数字按大小排列。 --情况3

剩余情况无法变化，是24小时候的本身。

Follow Up 2:

如果是closest time before + 可重复使用数字, 比如 12：34，答案是12：33。

下面就从低位分钟开始换数字了，如果低位分钟上的数字已经是最小的数字了，那么说明要回转过一轮了，就要把低位分钟上的数字换成最大的那个数字；否则就将低位分钟上的数字换成次小的数字。换一种说法就是，去哈希表里找有没有比给定的这个数小而且合法的数字，如果有则返回带有这个合法数字的新的string；如果没有，就把这一位设为哈希表里的最大值。然后再看高位分钟上的数字，同理，如果高位分钟上的数字已经是最小的数字，或则下一个数字大于5，那么直接换成最小值；否则就将高位分钟上的数字换成下一个数字。

对于小时位上的数字也是同理。当小时高位不为2的时候，低位可以是0~9，而当高位为2时，低位需要小于等于3。对于小时高位，其必须要小于等于2。

public String nextClosestTime(String time) {
        char[] t = time.toCharArray(), result = new char[4];
        int[] list = new int[10]; //数字集合，0~9
        char max = '0'; //记录最大的数
        
        for (char c : t) {
            if (c == ':') continue;
            list[c - '0']++;
            if (c > max) {
                max = c;
            }
        }
        
        //分钟最低位，如果有比最低位小的数字，直接返回。eg，12：34变成12：33
        for (int i = t[4] - '0' - 1; i >= 0; i--) {
            if (list[i] != 0) {
                t[4] = (char)(i + '0');
                return new String(t);
            }
        }
        //如果没有，则把第四位设为最大值
        t[4] = max;
        
        //分钟高位，如果有比最低位小的数字且此数字<=5，直接返回。
        //eg, 22：21上一步变成22：22，这一步变成22：12
        for (int i = t[3] - '0' - 1; i >= 0 && i <= 5; i--) {
            if (list[i] != 0) {
                t[3] = (char)(i + '0');
                return new String(t);
            }
        }
        //如果没有，则把第三位设为最大值
        t[3] = max;
        
        //检查时钟第一位是0/1 还是2。如果是0/1,stop是9，因为时钟位最多到09或19；不然stop是3，最多到23
        int stop = t[0] < '2' ? 9 : 3;
        
         //时钟最低位，如果有比此位数小的数字，直接返回
         //eg, 21：11第一步变成21：12，第二步变成21：22，这一步变成22：22
        for (int i = t[1] - '0' - 1; i >= 0 && i <= stop; i--) {
            if (list[i] != 0) {
                t[1] = (char)(i + '0');
                return new String(t);
            }
        }
        t[1] = max;
        
        //时钟高位，如果有比此位数小的数字，直接返回
         //eg, 21：11第一步变成21：12，第二步变成21：22，第三步变成22：22，这一步变成12：22
        for (int i = t[0] - '0' + 1; i >= 0 && i <= 2; i--) {
            if (list[i] != 0) {
                t[0] = (char)(i + '0');
                return new String(t);
            }
        }
        t[0] = max;
        
        return new String(t);
}