मान लीजिए हमारे पास 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से3तक लूप चलाएं:- यदि
A[i] != -1, तो:tmp := A[i]cur := cur + A[i] + '0' का ASCII- यदि
curका आकार 2 के समान है, तो:cur := cur + ':'
A[i] := -1dfs(A, res, cur)A[i] := tmpcurसे अंतिम वर्ण हटाएं- यदि
curका आकार 2 के समान है, तो:curसे अंतिम वर्ण हटाएं
- यदि
- मुख्य विधि से निम्नलिखित करें:
res := खाली स्ट्रिंग, tmp := खाली स्ट्रिंगdfs(A, res, tmp)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; } }; int main(){ Solution ob; vector<int> v = {1,2,3,4}; cout << (ob.largestTimeFromDigits(v)); }इनपुट
{1,2,3,4}आउटपुट
23:41
- यदि