Показать максимальное военное время с заданных четырех целых чисел

Question

Я столкнулся с этим вопросом в одном из заданий интервью.

Вопрос состоял в том, что с учетом четырех целых чисел отображалось максимально возможное время в 24-часовом формате ЧЧ: ММ. Например, если вы даете 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) и, таким образом, позволяет сортировать. Кроме того, как проверить случаи краев, о которых я упоминал выше?

Спасибо.

EDIT: Ниже приведен код ответа, предложенный в комментариях.

//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

С моим другом мы думать об этой проблеме несколько часов и ИМО лучшим решением является итерация от я = 2359, разделите я отсчитать отдельные цифры, сортировать и, наконец, проверять, равен ли он сортированному массиву входных номеров. Кроме того, если я% 100 == 0 вычитают 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"; 
}