/* 题目描述：给定一个数组，里面有6个整数，求这个数组能够表示的最大24进制的时间是多少，

输出这个时间，无法表示输出invalid。

输入描述:

输入为一个整数数组，数组内有六个整数。输入整数数组长度为6，不需要考虑其它长度，

元素值为0或者正整数，6个数字每个数字只能使用一次。

输出描述:

输出为一个24进制格式的时间，或者字符串"invalid"。

备注:输出时间格式为xx:xx:xx格式。

示例1

输入

[0,2,3,0,5,6]

输出

23:56:00

示例2

输入

[9,9,9,9,9,9]

输出

invalid*/

今天面试的时候给了我这个手撕题，没有写出来。面试没了，痛苦…，还要接着刷题。

我的想法是先解析这个数组为2位-2位-2位的数组，然后将结果存入到一个path中，并把这个path放到一个result数组中。然后对数组进行遍历，取hour,minutes和second的最大值。可惜写不出来，脑袋一团浆糊。下面是ChatGPT给出的我的思路的答案。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    string parseTime(vector<int>& nums) {
        string res = "invalid";
        vector<int> path;
        vector<bool> used(6, false);
        backtrack(nums, path, used, res);
        return res;
    }
private:
    void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, string& res)
    {
        if(path.size() == 3) {
            int h = path[0], m = path[1], s = path[2];
            if(h < 24 && m < 60 && s < 60) {
                string cur = (h<10?"0":"") + to_string(h) + ":" +
                             (m<10?"0":"") + to_string(m) + ":" +
                             (s<10?"0":"") + to_string(s);
                if(res == "invalid" || cur > res) res = cur;
            }
            return;
        }
        for (int i = 0; i < 6; i++) {
            if(used[i]) continue;
            used[i] = true;
            for (int j = 0; j < 6; j++) {
                if(i == j || used[j]) continue;
                used[j] = true;
                int num = nums[i] * 10 + nums[j];
                path.push_back(num);
                backtrack(nums, path, used, res);
                path.pop_back();
                used[j] = false;
            }
            used[i] = false;
        }
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {0,2,3,0,5,6};
    cout << sol.parseTime(nums1) << endl;
    
    vector<int> nums2 = {9,9,9,9,9,9};
    cout << sol.parseTime(nums2) << endl;
    return 0;
}

直接在typora里写代码，体验不太行～。

over.