เวลาที่ใหญ่ที่สุดสำหรับตัวเลขที่ระบุใน C ++

สมมุติว่าเรามีอาร์เรย์ 4 หลัก เราต้องหาเวลา 24 ชั่วโมงที่ใหญ่ที่สุดที่จะทำได้ เรารู้ว่าเวลา 24 ชั่วโมงที่น้อยที่สุดคือ 00:00 น. และเวลาที่ใหญ่ที่สุดคือ 23:59 เริ่มตั้งแต่ 00:00 น. เวลาจะมากขึ้นหากเวลาผ่านไปตั้งแต่เที่ยงคืน เราต้องส่งคืนคำตอบเป็นสตริงความยาว 5 หากไม่มีเวลาที่ถูกต้องที่จะส่งคืน ให้ส่งคืนสตริงว่าง

ดังนั้น หากอินพุตเป็น [1,2,3,4] เอาต์พุตจะเป็น "23:41"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน isValid() ซึ่งจะรับสตริง a,
• ถ้า a[0]> '2' แล้ว −
  • คืนค่าเท็จ
• ถ้า a[0] เหมือนกับ '2' และ a[1]> '3' แล้ว −
  • คืนค่าเท็จ
• ถ้า a[3]> '5' แล้ว −
  • คืนค่าเท็จ
• คืนค่าจริง
• กำหนดฟังก์ชัน 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)
• ผลตอบแทน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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