从给定的四个整数显示最大军事时间[重复]

Question

这个问题在这里已有答案：

• Find maximum possible time HH:MM by permuting four given digits 22回答

我在一次面试挑战中遇到了这个问题。

问题是给定四个整数，以24小时格式显示最大可能时间HH：MM。例如，如果给出A = 1，B = 9，C = 9，D = 2则输出应为19:29。最长时间可以是23:59，最短时间可以是00:00。如果无法构建24小时时间，则返回错误。例如，给定A = 1，B = 9，C = 7，D = 9，应该返回错误，因为这些整数表示的最小时间是17:99，这是无效的。

我最初的方法是找到给定数字的所有24个整数排列，然后消除所有大于2400的整数。在此之后，消除所有最后两位数超过59的整数。也就是说，十个地方有5个，单位有9个。在此过滤之后，返回结果集中剩余的最大整数。

这种方法在这里是可行的，因为我们必须计算24个排列甚至更少的组合，因为将删除重复项。但我觉得这是一种蛮力的做法。有没有其他想法不要求我们产生所有排列？

同样作为这个问题的扩展，如果我们被要求将时间延长到分别给出总共6位数或8位数的秒或毫秒，那么我的方法将是昂贵的。让我们假设最大允许运行时间复杂度可以是O（nlogn），从而允许我们排序。另外，如何检查我上面提到的边缘情况？

谢谢。

编辑：以下是评论中建议的答案的代码。

//Input arraylist contains the four integers
public static String maxTime(ArrayList<Integer> list){
    int first = -1;
    int second = -1;
    int third = -1;
    int fourth = -1;

    for (int a : list) {
        if (a <= 2 && a > first) {
            first = a;
        }
    }
    list.remove(Integer.valueOf(first));

    for (int a : list) {
        if (first == 2 && a <= 3 && a > second) {
            second = a;
        }
    }
    if (second == -1) {
        for (int a : list) {
            if (a > second) {
                second = a;
            }
        }
    }
    list.remove(Integer.valueOf(second));

    for (int a : list) {
        if (a <= 5 && a > third) {
            third = a;
        }
    }
    list.remove(Integer.valueOf(third));

    fourth = list.get(0);

    StringBuilder sb = new StringBuilder(5);
    sb.append(first);
    sb.append(second);
    sb.append(':');
    sb.append(third);
    sb.append(fourth);

    return sb.toString();
}

Answer 1

我的解决方案

function getMaxTime(a,b,c,d) {

let nums = Array.from(arguments).sort();

function getMaxNum (num, arr) {    
  let index ;
   arr.map(function(el, i){     

        if( el <= num ) { index = i }                  
  });

  return index 
} 

function extractVal (index, arr) {
   if(index) { return arr.splice(index, 1) }
}


//first condition

  if ( getMaxNum(2, nums) <= 2 ){
     let value1 =  extractVal(getMaxNum(2, nums), nums);        

      if (value1 == 2){
       if (getMaxNum(3, nums) <= 3){

         let value2 = extractVal(getMaxNum(3, nums), nums)         
         let value3 = extractVal(getMaxNum(5, nums), nums)     
         let value4 = extractVal(getMaxNum(9, nums), nums)
         console.log(value1, value2, value3, value4)
       }else{
          console.log( 'Cannot build an time hour from 2' )
       }

    }else{
      let value2 =  extractVal(getMaxNum(9, nums), nums)
      let value3 =  extractVal(getMaxNum(5, nums), nums)   
      let value4 =  extractVal(getMaxNum(9, nums), nums)

      console.log(value1, value2, value3, value4)
    }

  }else{
    console.log( 'Cannot build an time hour' )
  }

}

getMaxTime(0,0,3,5)

Answer 2

和我的朋友一起考虑这个问题几个小时和IMO最好的解决方案是从i = 2359迭代，将i数除以单独的数字，排序并最终检查是否等于输入数字的排序数组。另外，如果i％100 == 0从i中减去41以避免分钟大于60的数字。完整的，经过测试的实现如下：

public String solution(int A, int B, int C, int D) {

    int[] inputNumbers = { A, B, C, D };
    Arrays.sort(inputNumbers);

    for (int i = 2359; i >= 0; i--) {

        if (i % 100 == 0 && i != 0) {
            i -= 41;
        }
        StringBuilder potentialTimeNumbers = new StringBuilder(i + "");

        for (int k = potentialTimeNumbers.length(); k < 4; k++) {
            potentialTimeNumbers.insert(0, "0");
        }

        int[] iNumbers = Stream.of(potentialTimeNumbers.toString().split("")).
                mapToInt(Integer::parseInt).toArray();
        Arrays.sort(iNumbers);

        if (Arrays.equals(inputNumbers, iNumbers)) {
            return potentialTimeNumbers.insert(2, ":").toString();
        }

    }
    return "NOT VALID";
}