与えられた数字の最大の時間

与えられた数字の最大の時間

問題
4桁の配列arrを考えれば、正確に一度に各々の桁を使って作られることができる最新の24時間の時間を見つけてください.
24時間は"HH:MM"、HHと00の間、23はMMと00の間にある.最も早い24時間は59です、そして、最新は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時間の時間を見つける必要がある“一度だけ”.

ソリューションや擬似コードにジャンプする前に、問題文を何度か読んで、よく理解してください.

問題文に基づいて、我々は答えを見つけるために4桁のすべての可能な組み合わせを計算する必要があることを理解しています.これはすぐにこの問題は“動的計画”の下に該当するヒントを与える.このような“置換＆組み合わせ”の問題のこれらの種類に取り組むためにすべての異なるアプローチを学ぶことは非常に興味深いトピックです.

は、“各桁”のようなキーワードを識別しようとすると“一度だけ”を使用することができます.これは私たちの最初の手がかりです.私たちは正確に4つの数字を私たちの“hh : mm”最新の時間(最終回答)をする必要があります.

我々が考えることができる

第2の手掛かりは、各々の桁をチェックするか、すべてのHHのMM出現を持ちます:MM組合せは、我々の最終的な答えを得るために、配列と比較します.

私たちは1日(24時間の時間形式)の最新の時間、最大時間と分をしたいので、我々は最大(23時間と59分)から開始する必要がありますし、後方に後方に繰り返し、最新の時間を取得します.

それで、これらのすべてのヒントと分析で、我々のアルゴリズムまたは疑似コードを書き始めましょう.

アルゴリズムは擬似コード

は最大時間からの反復を開始します:ミニマックス時間(23 : 59)、そして、すべての4桁の組合せをすべての繰り返し

のために持ちます

は、「真」への開始時にLatestCage Hourブーリアンフラグを初期化します.

単一配列の4桁が入力配列の4つの要素と一致しない場合、私たちはLatinタイムに達しませんでした.Latinタイム時間フラグをfalseに設定します.

繰り返して、我々が最新の時間を見つけるまで続きます.4桁の組み合わせが配列の4つの要素と一致するまで.

解決策を書き始めましょう.

Loop through every hour and digit combination. If we find the exact
four array elements. That's it. That is our answer.
The Latest 24-hour Time!

解決策

    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 )

結論
この問題はダイナミックプログラミングの非常に良い例です.更なる学習のためにこのカテゴリーでより多くの例のためにチェックしてください.動的計画法は、トップダウンとボトムアップアプローチの2つの方法を有する.私は2つの違いを説明する将来の記事を見てください!

参考文献
この記事のleetcode問題
https://leetcode.com/problems/largest-time-for-given-digits/

この投稿を読んでくれてありがとう!
私は、この記事が有益で有益であることを望みます.それが好きなら、共有してください!関連コンテンツのために私に従ってください.
ハッピーラーニング!