leetcode基本的なバックトラッキングバイナリ時計

Leetcode Basic Backtracking Binary Watch

バイナリ時計の上部には数時間（0〜11）の4つのLEDがあり、下部には数分（0〜59）の6つのLEDがあります。

各LEDは0または1を表し、最下位ビットが右側にあります。

たとえば、上記のバイナリウォッチは「3:25」を読み取ります。

オンになっているLEDの現在の数を表す負でない整数nが与えられた場合、可能なすべての時間を返します。

場合：

入力：n = 1
戻り値：[「1:00」、「2:00」、「4:00」、「8:00」、「0:01」、「0:02」、「0:04」、「0:08」 、 '0：16'、 '0:32']

予防：

The order of output is not required. The hour will not start with a zero. For example, '01:00' is not allowed, it should be '1:00'. The minute must consist of two digits and may start with a zero. For example, '10:2' is invalid and should be '10:02'.

アイデア：
1.バックトラッキング方法
長さ10の配列を設定します。最初の4桁は時間、最後の6桁は分です。これは、10個の要素から4つの順列と組み合わせの問題をフィルター処理するのと同じです。

#include #include #include #include #include using namespace std vector<string> res void track(int n,int index,vector<int> &vec,int sumH,int sumM,int start) { if (index == n) { if (sumM < 10) res.push_back(to_string(sumH) + ':0' + to_string(sumM)) else res.push_back(to_string(sumH) + ':' + to_string(sumM)) cout << sumH << ' ' << sumM<<endl return } for (int i = start i < 10 i++) { if (!vec[i]) {//Not visited if (i < 4 && (pow(2,i)+sumH < 12)) {//hour vec[i] = 1 //if (vec[i] * pow(2, i) + sumH == 12) cout << 'why' track(n, index + 1, vec, sumH + pow(2, i), sumM, i+1) vec[i] = 0 } else if (i >= 4 && ( pow(2, i-4) + sumM < 60)) {//minute vec[i] = 1 track(n, index + 1, vec, sumH, sumM + pow(2, i - 4),i+1) vec[i] = 0 } } } } vector<string> readBinaryWatch(int num) { vector<int> vec(10, 0)//The first 4 digits store hours, and the last 4 digits store minutes track(num, 0, vec, 0, 0, 0) return res } int main() { readBinaryWatch(2) }

2. 1-11と1-59の2つのサイクルを設定してから、バイナリに変換し、1の数を数えます。