以24小时格式最大化数字.

Question

在Glassdoor评论中遇到了这个问题,并认为它很有趣.

给定一个由4位数组成的整数,我们需要以24小时格式最大化它.例如,4372应该返回23:47形式的字符串,这是可以从给定整数获得的最大24小时值.假设给定的整数总是包含4位数.

这是我写的一个不完整的方法试图解决它:

private static String maximize24Hour(int digits) {
    if (digits == 0)
        return "00:00";
    if (digits < 0)
        return null;

    ArrayList<Integer> list = new ArrayList<>();
    do {
        list.add(digits % 10);
        digits /= 10;
    } while (digits != 0);

    // Extra processing needs to be done here. Haven't figured it out. 

    StringBuilder buf = new StringBuilder();
    for (Integer d : list) {
        buf.append(d);
    }

    String result = buf.toString();
    String hours = result.substring(0, 2);
    String minutes = result.substring(2, result.length()); 

    if (Integer.parseInt(result) > 2359 
            || Integer.parseInt(hours) > 23 
            || Integer.parseInt(minutes) > 59
            || result.length() != 4)
        return null;

    return hours.concat(":").concat(minutes);
}

我是否正确接近它？如果这只是任何数字,那将是微不足道的.但它要求它是24小时格式,这是我觉得棘手.

我有兴趣看看是否有人有这个挑战的解决方案/想法.

Answer 1

1. 将整数分成4位数.
2. 如果你没有0,1或2,则没有答案.
3. 在时间的第一个位置放置<= 2的最大数字.
4. 如果第一个数字是2,那么在第二个位置放置<= 3的最大剩余数字.(如果没有,则没有答案.)如果第一个数字是1或0,则将最大的剩余数字放在第二个位置.
5. 将剩余的最大数字<= 5放在第三位.
6. 将剩下的唯一数字放在第四位.

我认为您不需要在任何时候回溯,因为步骤3,4和5中的界限严格增加.你当然不需要考虑所有可能的数字排列,因为我们知道某些地方是有界限的.