C++で指定された桁の最大時間

4桁の配列があるとすると、24時間制で作成できる最大の時間を見つける必要があります。 24時間の最小時間は00:00で、最大時間は23:59であることがわかっています。 00:00から、深夜から時間が経過すると時間が長くなります。答えは長さ5の文字列として返す必要があります。返される有効な時間がない場合は、空の文字列を返します。

したがって、入力が[1,2,3,4]の場合、出力は「23:41」になります

これを解決するには、次の手順に従います-

• 関数isValid（）を定義します。これには、文字列aが必要です。
• a [0]> '2'の場合、-
  • falseを返す
• a[0]が'2'およびa[1]>'3'と同じである場合、-
  • falseを返す
• a [3]> '5'の場合、-
  • falseを返す
• trueを返す
• 関数dfs（）を定義します。これには、配列A、res、cur、
が必要です。
• curのサイズが5と同じ場合、-
  • isValid（cur）およびcur> resの場合、-
    • res：=cur
  • 戻る
• iを初期化する場合：=0、i <4の場合、更新（iを1増やす）、実行-
  • A [i]が-1に等しくない場合、-
    • tmp：=A [i]
    • cur：=cur + A [i]+ASCIIの「0」
    • curのサイズが2と同じ場合、-
      • cur：=curは'：'と連結します
    • A [i]：=-1
    • dfs（A、res、cur）
    • A [i]：=tmp
    • curから最後の要素を削除する
    • curのサイズが2と同じ場合、-
      • curから最後の要素を削除する
• メインの方法から次のようにします-
• res：=空の文字列、tmp：=空の文字列
• dfs（A、res、tmp）
• return res

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   void dfs(vector<int>& A, string& res, string& cur) {
      if (cur.size() == 5) {
         if (isValid(cur) && cur > res)
            res = cur;
            return;
         }
         for (int i = 0; i < 4; ++i) {
            if (A[i] != -1) {
               int tmp = A[i];
               cur += A[i] + '0';
            if (cur.size() == 2)
               cur += ':';
               A[i] = -1;
               dfs(A, res, cur);
               A[i] = tmp;
               cur.pop_back();
               if (cur.size() == 2)
                  cur.pop_back();
            }
         }
   }
   bool isValid(const string a) {
      if (a[0] > '2')
         return false;
         if (a[0] == '2' && a[1] > '3')
            return false;
         if (a[3] > '5')
            return false;
         return true;
   }
   string largestTimeFromDigits(vector<int>& A) {
      string res = "", tmp = "";
      dfs(A, res, tmp);
      return res;
   }
};
main(){
Solution ob;
vector<int> v = {1,2,3,4};
cout << (ob.largestTimeFromDigits(v));
}

入力

{1,2,3,4}

出力

23:41