C++ में दिए गए अंकों के लिए सबसे बड़ा समय

मान लीजिए कि हमारे पास 4 अंकों की एक सरणी है, हमें 24 घंटे का सबसे बड़ा समय निकालना होगा जो बनाया जा सकता है। हम जानते हैं कि 24 घंटे का सबसे छोटा समय 00:00 है, और सबसे बड़ा समय 23:59 है। 00:00 से शुरू होकर, यदि मध्यरात्रि के बाद से अधिक समय बीत चुका है, तो समय बड़ा होता है। हमें उत्तर को लंबाई 5 की एक स्ट्रिंग के रूप में वापस करना होगा। यदि वापस करने के लिए कोई वैध समय नहीं है, तो एक खाली स्ट्रिंग लौटाएं।

इसलिए, अगर इनपुट [1,2,3,4] जैसा है, तो आउटपुट "23:41" होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें isValid(), यह एक स्ट्रिंग लेगा,
• यदि a[0]> '2', तो −
  • झूठी वापसी
• यदि a[0] '2' और a[1]> '3' के समान है, तो −
  • झूठी वापसी
• यदि a[3]> '5', तो −
  • झूठी वापसी
• सही लौटें
• एक फ़ंक्शन dfs() को परिभाषित करें, यह एक सरणी A, res, cur,
लेगा
• यदि वक्र का आकार 5 के समान है, तो −
  • अगर isValid(cur) and cur>res, तो −
    • res :=cur
  • वापसी
• इनिशियलाइज़ i :=0 के लिए, जब i <4, अपडेट करें (i को 1 से बढ़ाएँ), −
  करें
  • यदि A[i] -1 के बराबर नहीं है, तो −
    • tmp:=ए[i]
    • cur :=cur + A[i] + ASCII का '0'
    • यदि वक्र का आकार 2 के समान है, तो −
      • cur:=वक्र ':' के साथ संयोजित होता है
    • ए[i] :=-1
    • dfs(A, res, cur)
    • ए[i] :=tmp
    • cur से अंतिम तत्व हटाएं
    • यदि वक्र का आकार 2 के समान है, तो −
      • cur से अंतिम तत्व हटाएं
• मुख्य विधि से निम्न कार्य करें -
• res:=खाली स्ट्रिंग, tmp:=खाली स्ट्रिंग
• dfs(ए, रेस, टीएमपी)
• रिटर्न रेस

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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