C++ Non-recursive BFS, 0ms.


  • 0
    A

    First generate the permutations that satisfy the LED number constraint, then convert them to string.

    10 / 10 test cases passed
    Status: Accepted
    Runtime: 0 ms

    class Solution {
    public:
        vector<string> readBinaryWatch(int num) {
            vector<array<uint, 2>> v;
            v.push_back({0, 0});
            for (uint i = 0; i < num; i++) {
                for (uint j = 0, jj = v.size(); j < jj; j++) {
                    for (uint k = v[j][1], kk = 10 - num + i; k <= kk; ) {
                        if (k == kk) { v[j][0] |= 1 << k++; v[j][1] = k; }
                        else v.push_back({v[j][0] | 1 << k++,  k});
                    }
                }
            }
            vector<string> res;
            for (uint i = 0, ii = v.size(), j = 0; i < ii; i++) {
                if ((v[i][1] = v[i][0] >> 6) >= 12 || (v[i][0] &= 0x3F) >= 60) continue; // skip hours 12:xx or minutes xx:60
                res.push_back("");
                res[j].push_back(v[i][0] % 10 + '0');
                v[i][0] /= 10;
                res[j].push_back(v[i][0] % 10 + '0');
                res[j].push_back(':');
                res[j].push_back(v[i][1] % 10 + '0');
                if (v[i][1] /= 10) res[j].push_back(v[i][1] % 10 + '0');
                reverse(res[j].begin(), res[j].end()); // everything was in reverse order
                j++;
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.