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

Проблема

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

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

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

Пример 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 в начале равным «истина».
Если 4 цифры одной итерации не совпадают с 4 элементами входного массива, мы не достигли last_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)

Заключение

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

использованная литература

Проблема LeetCode в этой статье:

Https://leetcode.com/problems/largest-time-for-given-digits/

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

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

Удачного обучения!

Первоначально опубликовано на https://geetcloud.blogspot.com 1 сентября 2021 г.

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