Leetcode 401. Binary Watch

Tyan

发布于 2019-05-25 22:19:09

3820

发布于 2019-05-25 22:19:09

文章被收录于专栏：SnailTyanSnailTyan

文章作者：Tyan

博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

Version 1

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> result;
        vector<int> hourBits = countBits(11);
        vector<int> miniteBits = countBits(59);
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 60; j++) {
                if(hourBits[i] + miniteBits[j] == num) {
                    string s = to_string(i) + (j<10?(":0" + to_string(j)):(":" + to_string(j)));
                    result.push_back(s);
                }
            }
        }
        return result;
    }

private:
    vector<int> countBits(int num) {
        vector<int> array(num + 1, 0);
        for(int i = 1; i <= num; i++) {
            array[i] = array[(i & (i - 1))] + 1;
        }
        return array;
    }
};

Version 2

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> result;
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 60; j++) {
                if(bitset<10>((i << 6) + j).count() == num) {
                    string s = to_string(i) + (j<10?(":0" + to_string(j)):(":" + to_string(j)));
                    result.push_back(s);
                }
            }
        }
        return result;
    }
};

Version 3

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> result;
        for(int h = 0; h < 12; h++) {
            for(int m = 0; m < 60; m++) {
                if(bitset<10>((h << 6) + m).count() == num) {
                    result.emplace_back(to_string(h) + (m<10?(":0" + to_string(m)):(":" + to_string(m))));
                }
            }
        }
        return result;
    }
};