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

ปัญหา

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

เช่น ถ้าผนวกเข้าเป็น [1,2,3,4] ผลลัพธ์จะเป็น "23:41"

วิธีแก้ปัญหา

1. กำหนดฟังก์ชัน isValid() รับสตริง a:
   • ถ้า a[0] > '2' คืนค่า false
   • ถ้า a[0] == '2' และ a[1] > '3' คืนค่า false
   • ถ้า a[3] > '5' คืนค่า false
   • คืนค่า true
2. กำหนดฟังก์ชัน dfs() รับอาร์เรย์ A, res, cur:
   • ถ้าขนาดของ cur เท่ากับ 5:
     • ถ้า isValid(cur) และ cur > res แล้ว: res := cur
     • คืนค่า
   • for i := 0 ถึง 3 ทำ:
     • ถ้า 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
3. จากเมธอดหลัก:
   • res := สตริงว่าง, tmp := สตริงว่าง
   • dfs(A, res, tmp)
   • คืนค่า res

ตัวอย่างโค้ด C++

#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