LeetCode | Наибольшее время для заданных цифр

Наибольшее время для заданных цифр

Проблема

Учитывая массив arr из 4 цифр, найдите последнее 24-часовое время, которое может быть установлено с использованием каждой цифры ровно один раз .

24-часовое время форматируется как "ЧЧ:ММ" , где ЧЧ находится между 00 и 23 , и ММ находится между 00 и 59 . Самое раннее 24-часовое время – 00:00 , а самое позднее – 23:59 .

Возвращает самое позднее 24-часовое время в формате "ЧЧ:ММ" . Если невозможно указать допустимое время, верните пустую строку.

Пример 1:

Input: arr = [1,2,3,4]
Output: "23:41"
Explanation: The valid 24-hour times are "12:34", "12:43", "13:24", "13:42", "14:23", "14:32", "21:34", "21:43", "23:14", and "23:41". Of these times, "23:41" is the latest.

Пример 2:

Input: arr = [5,5,5,5]
Output: ""
Explanation: There are no valid 24-hour times as "55:55" is not valid.

Пример 3:

Input: arr = [0,0,0,0]
Output: "00:00"

Пример 4:

Input: arr = [0,0,1,0]
Output: "10:00"

Ограничения:

 `arr.length == 4`
 `0 <= arr[i] <= 9`

Давайте начнем

Наша главная цель – решить проблему и в то же время достичь наилучшей линейной временной сложности с минимальной пространственной сложностью. Если вы новичок в решении проблем или пытаетесь решить проблемы со структурой данных, я предлагаю вам начать с подхода грубой силы, а затем попытаться оптимизировать свое решение с учетом наилучшей сложности времени/пространства.

Анализ

Давайте начнем анализировать постановку задачи. Учитывая массив из 4 цифр, нам нужно узнать последнее 24-часовое время, которое можно установить, используя каждую цифру “только один раз”.

Прежде чем перейти к решению или псевдокоду, прочтите постановку задачи пару раз и убедитесь, что вы ее хорошо поняли.
Основываясь на постановке задачи, мы понимаем, что нам нужно вычислить все возможные комбинации из четырех цифр, чтобы найти ответ. Это сразу же даст нам понять, что эта проблема подпадает под “Динамическое программирование”. Это очень интересная тема для изучения всех различных подходов к решению подобных проблем “Перестановки и комбинации”.

Попробуйте определить ключевые слова типа “каждая цифра”, которые можно использовать “только один раз”. Это наша первая подсказка. У нас есть ровно четыре цифры, чтобы составить наш последний час “чч:мм” (окончательный ответ).
Вторая подсказка, о которой мы можем подумать, – это проверить каждую цифру или сохранить вхождения цифр во всех комбинациях чч: мм для сравнения с массивом, чтобы получить наш окончательный ответ.
Поскольку нам нужен последний час, максимальный час и минута в сутках (24-часовой формат времени), нам нужно начать с максимального значения (23 часа и 59 минут соответственно) и выполнить итерацию в обратном направлении, чтобы получить последний час.

Итак, со всеми этими подсказками и анализом давайте начнем писать наш алгоритм или псевдокод.

Алгоритм | Псевдокод

Начните итерацию с максимального часового: минутного максимального времени (23:59) и удерживайте все комбинации из 4 цифр для каждой итерации
Инициализируйте логический флаг latest_hour в начале на “true”.
Если 4 цифры одной итерации не совпадают с 4 элементами входного массива, мы не достигли latest_hour. Поэтому установите флаг latest_hour равным false.
Повторяйте и продолжайте, пока мы не найдем последний час. то есть до тех пор, пока комбинации из 4 цифр не совпадут с 4 элементами массива.

Давайте начнем писать решение.

Перебирайте каждый час и комбинацию цифр. Если мы найдем точные четыре элемента массива. Это оно. Это наш ответ. Самое позднее 24-часовое Время!

Решение (на Java)

    class Solution {
        public String largestTimeFromDigits(int[] arr) {
          for(int hour = 23; hour >= 0; hour--) {
                for(int minute = 59; minute >= 0; minute--) {
                    boolean latest_hour = true;
                    int[] count = new int[10];

                    count[hour < 10 ? 0 : hour / 10]++;
                    count[hour < 10 ? hour : hour % 10]++;
                    count[minute < 10 ? 0 : minute / 10]++;
                    count[minute < 10 ? minute : minute % 10]++;                

                   for(int item : arr) {
                        if(--count[item] < 0) {
                            latest_hour = false;
                            break;
                        }
                    }

                    if(latest_hour) 
                      return String.format("%02d:%02d", hour, minute);
                }
            }
            return "";
        }
    }

Сложность

Временная сложность => O(23 x 59 x 4) ==> O(1) Пространственная сложность => O(1)

Вывод

Эта проблема является очень хорошим примером динамического программирования. Пожалуйста, ознакомьтесь с другими примерами в этой категории для дальнейшего изучения. Динамическое программирование имеет два метода: подход сверху вниз и подход снизу вверх. Будьте в курсе будущей статьи, в которой я объясню эти два понятия и их различия!

Спасибо, что прочитали этот пост!

Я надеюсь, что эта статья будет в какой-то мере информативной и полезной. Если это так, пожалуйста, поставьте лайк и поделитесь! Следуйте за мной дальше Twitter | LinkedIn для получения соответствующего контента.

Счастливого обучения!

Оригинал: “https://dev.to/geetcloud/leetcode-sep-21-challenge-series-day-1-largest-time-for-given-digits-1glp”