Thời gian lớn nhất cho các chữ số đã cho trong C ++

Giả sử chúng ta có một mảng gồm 4 chữ số, chúng ta phải tìm khoảng thời gian 24 giờ lớn nhất có thể được thực hiện. Chúng ta biết rằng thời gian 24 giờ nhỏ nhất là 00:00 và thời gian lớn nhất là 23:59. Bắt đầu từ 00:00, thời gian sẽ lớn hơn nếu thời gian trôi qua nhiều hơn kể từ nửa đêm. Chúng ta phải trả về câu trả lời dưới dạng một chuỗi có độ dài 5. Nếu không có thời gian hợp lệ để trả về, thì hãy trả về một chuỗi trống.

Vì vậy, nếu đầu vào là [1,2,3,4], thì đầu ra sẽ là "23:41"

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm isValid (), hàm này sẽ nhận chuỗi a,
• nếu a [0]> '2', thì -
  • trả về false
• nếu [0] giống với '2' và [1]> '3', thì -
  • trả về false
• nếu a [3]> '5', thì -
  • trả về false
• trả về true
• Xác định một hàm dfs (), hàm này sẽ nhận một mảng A, res, cur,
• nếu kích thước của cur bằng 5, thì -
  • nếu isValid (cur) và cur> res, thì -
    • res:=cur
  • trở lại
• để khởi tạo i:=0, khi i <4, cập nhật (tăng i lên 1), thực hiện -
  • nếu A [i] không bằng -1, thì -
    • tmp:=A [i]
    • cur:=cur + A [i] + ASCII của '0'
    • nếu kích thước của cur bằng 2, thì -
      • cur:=cur nối với ':'
    • A [i]:=-1
    • dfs (A, res, cur)
    • A [i]:=tmp
    • xóa phần tử cuối cùng khỏi cur
    • nếu kích thước của cur bằng 2, thì -
      • xóa phần tử cuối cùng khỏi cur
• Từ phương thức chính, hãy làm như sau -
• res:=chuỗi trống, tmp:=chuỗi trống
• dfs (A, res, tmp)
• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{1,2,3,4}

Đầu ra

23:41