https://leetcode.com/problems/binary-watch/description/
题目
A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).
Each LED represents a zero or one, with the least significant bit on the right.
For example, the above binary watch reads “3:25”.
Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example:
Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
Note:
- The order of output does not matter.
- The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
- The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.
题目翻译
题目解析
参考答案
排列组合
#include <iostream>
#include <string>
using namespace std;
void func(const string & strSource, const int iMaxNum, const int iSelectNum,
int iCurIndex, int iCurLeftNum, string & strCurResult)
{
if (iCurLeftNum == 0)
{
cout << strCurResult << endl;
return;
}
for (int i = iCurIndex; i + iCurLeftNum <= iMaxNum; i++)
{
strCurResult.push_back(strSource[i]);
func(strSource, iMaxNum, iSelectNum, i + 1, iCurLeftNum - 1, strCurResult);
strCurResult.pop_back();
}
}
int main()
{
string strResult;
func("abcdef", 6, 2, 0, 2, strResult);
return 0;
}
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
class Solution {
public:
Solution()
: hour(4, vector<string>()),
minute(6, vector<string>())
{
int i;
for (i = 0; i < 4; i++)
{
int iCurResult = 0;
func(4, 0, i, iCurResult, hour[i]);
}
for (i = 0; i < 6; i++)
{
int iCurResult = 0;
func(6, 0, i, iCurResult, minute[i]);
}
vPrint();
}
void vPrint()
{
for (int i = 0; i < 4; i++)
{
vector<string>::iterator iter = hour[i].begin();
while (iter != hour[i].end())
{
cout << *iter << " ";
++iter;
}
cout << endl;
}
cout << endl;
for (int i = 0; i < 6; i++)
{
vector<string>::iterator iter = minute[i].begin();
while (iter != minute[i].end())
{
cout << *iter << " ";
++iter;
}
cout << endl;
}
}
vector<string> readBinaryWatch(int num)
{
}
private:
void func(const int iMaxNum, int iCurIndex, int iCurLeftNum, int iCurResult, vector<string> & vecResult)
{
if (iCurLeftNum == 0)
{
char acResult[10] = { 0 };
sprintf(acResult, "%d", iCurResult);
vecResult.push_back(acResult);
return;
}
for (int i = iCurIndex; i + iCurLeftNum <= iMaxNum; i++)
{
iCurResult += pow(2, i);
func(iMaxNum, i + 1, iCurLeftNum - 1, iCurResult, vecResult);
iCurResult -= pow(2, i);
}
}
vector<vector<string>> hour;
vector<vector<string>> minute;
};
int main()
{
Solution o;
return 0;
}
最终
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
class Solution {
public:
Solution()
: hour(4, vector<string>()),
minute(6, vector<string>())
{
int i;
for (i = 0; i < 4; i++)
{
int iCurResult = 0;
func(4, 0, i, iCurResult, hour[i], 12, false);
}
for (i = 0; i < 6; i++)
{
int iCurResult = 0;
func(6, 0, i, iCurResult, minute[i], 60, true);
}
vPrint();
}
void vPrint()
{
for (int i = 0; i < 4; i++)
{
vector<string>::iterator iter = hour[i].begin();
while (iter != hour[i].end())
{
cout << *iter << " ";
++iter;
}
cout << endl;
}
cout << endl;
for (int i = 0; i < 6; i++)
{
vector<string>::iterator iter = minute[i].begin();
while (iter != minute[i].end())
{
cout << *iter << " ";
++iter;
}
cout << endl;
}
cout << endl;
}
vector<string> readBinaryWatch(int num)
{
vector<string> vecResult;
for (int i = 0; i <= num; i++)
{
if (i <= 3)
{
int j = num - i;
if (0 <= j && j <= 5)
{
vector<string>::iterator iterHour = hour[i].begin();
while (iterHour != hour[i].end())
{
vector<string>::iterator iterMinute = minute[j].begin();
while (iterMinute != minute[j].end())
{
vecResult.push_back(*iterHour + ":" + *iterMinute);
++iterMinute;
}
++iterHour;
}
}
}
}
return vecResult;
}
private:
void func(const int iMaxNum, int iCurIndex, int iCurLeftNum, int iCurResult, vector<string> & vecResult, const int iMaxValue, bool bFormatZero)
{
if (iMaxValue <= iCurResult)
{
return;
}
if (iCurLeftNum == 0)
{
char acResult[10] = { 0 };
sprintf(acResult, bFormatZero ? "%02d" : "%d", iCurResult);
vecResult.push_back(acResult);
return;
}
for (int i = iCurIndex; i + iCurLeftNum <= iMaxNum; i++)
{
iCurResult += pow(2, i);
func(iMaxNum, i + 1, iCurLeftNum - 1, iCurResult, vecResult, iMaxValue, bFormatZero);
iCurResult -= pow(2, i);
}
}
vector<vector<string>> hour;
vector<vector<string>> minute;
};
int main()
{
Solution o;
vector<string> vecResult = o.readBinaryWatch(2);
vector<string>::iterator iter = vecResult.begin();
while (iter != vecResult.end())
{
cout << *iter << endl;
++iter;
}
return 0;
}
