文章題目來源于leetcode，解法學(xué)習(xí)了討論去的解法。
問題：有一種二進(jìn)制LED表。上面的4個LED燈表示小時，下面6個LED燈表示分鐘。給定一個int值，寫出可能表示的時間。例如輸入1，
Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]
注意：1輸出結(jié)果的順序無所謂；2 小時不能有高位0，例如”01:00”是錯誤的，”1:00”是正確的；3 分鐘用兩位數(shù)表示，例如”1:1”是錯誤的，”1:01”是正確的。
思路：這是一道典型的深度優(yōu)先搜索，枚舉各種情況就好了。枚舉所有小時的可能性，再枚舉所有分鐘的可能性。我確定我會做，但是失敗了。因為我同時在枚舉小時和分鐘。以前處理的都是單個的枚舉。
private void visit(
int num,
int countHour,
int countMinute,
int startHourIndex,
int startMinuteIndex) {
if (num ==
0) {
if (countHour <
12) {String
str = countHour +
":" + (countMinute <
10 ?
"0" + countMinute : countMinute);
if (!list.contains(
str)) {list.add(
str);}}}
else {
if (startMinuteIndex < mininutes.length) {visit(num -
1, countHour, countMinute + mininutes[startMinuteIndex], startHourIndex, startMinuteIndex +
1);visit(num, countHour, countMinute, startHourIndex, startMinuteIndex +
1);}
if (startHourIndex < hours.length) {visit(num -
1, countHour + hours[startHourIndex], countMinute, startHourIndex +
1, startMinuteIndex);visit(num, countHour, countMinute, startHourIndex +
1, startMinuteIndex);}}}
收獲：
1 看了別人的解決方案后，分別枚舉小時、分鐘，最后再組合到一起。
2 還有一種方法更牛。提前把所有小時的可能組合、所有分鐘可能的組合列出來。然后再把小時、分鐘組合。參考鏈接。
private int[] hours =
new int[] {
1,
2,
4,
8 };
private int[] mininutes =
new int[] {
1,
2,
4,
8,
16,
32 };
private List<String> list;
public List<String>
readBinaryWatch(
int num) {list =
new ArrayList<String>();
for (
int i =
0; i <= num; i++) {List<Integer> hours = visitHour(i);List<Integer> minutes = visitMinute(num - i);
for (Integer h : hours) {
if (h <
12) {
for (Integer m : minutes) {
if (m <
60) {list.add(h +
":" + (m <
10 ?
"0" + m : m));}}}}}
return list;}
private List<Integer>
visitMinute(
int num) {List<Integer> list =
new ArrayList<Integer>();visit2(num,
0,
0,list,mininutes);
return list;}
private List<Integer>
visitHour(
int num) {List<Integer> list =
new ArrayList<Integer>();visit2(num,
0,
0,list,hours);
return list;}
private void visit(
int num,
int count,
int startIndex, List<Integer> list,
int[] nums) {
if(num<=
0){list.add(count);
return;}
if(startIndex>=nums.length){
return;}visit(num-
1,count+nums[startIndex],startIndex+
1,list,nums);visit(num,count,startIndex+
1,list,nums);}
/*** visit的另外一種寫法* @param num* @param count* @param startIndex* @param list* @param nums*/private void visit2(
int num,
int count,
int startIndex, List<Integer> list,
int[] nums) {
if(num<=
0){list.add(count);
return;}
for(
int i=startIndex;i<nums.length;i++){visit2(num-
1,count+nums[i],i+
1,list,nums);}}
參考資料：
1 [題目](https://leetcode.com/problems/binary-watch/#/description)
2 討論1
3 討論2
總結(jié)
以上是生活随笔為你收集整理的401 binary watch的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
