LeetCode：二進(jìn)制手表【401】

題目描述

二進(jìn)制手表頂部有 4 個(gè) LED 代表小時(shí)（0-11），底部的 6 個(gè) LED 代表分鐘（0-59）。

每個(gè) LED 代表一個(gè) 0 或 1，最低位在右側(cè)。

例如，上面的二進(jìn)制手表讀取 “3:25”。

給定一個(gè)非負(fù)整數(shù)?n?代表當(dāng)前 LED 亮著的數(shù)量，返回所有可能的時(shí)間。

案例:

輸入: n = 1 返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

?

注意事項(xiàng):

• 輸出的順序沒有要求。
• 小時(shí)不會(huì)以零開頭，比如 “01:00”?是不允許的，應(yīng)為 “1:00”。
• 分鐘必須由兩位數(shù)組成，可能會(huì)以零開頭，比如 “10:2”?是無效的，應(yīng)為 “10:02”。

題目分析

　　這道題目標(biāo)注為簡單題，但感覺做起來比較費(fèi)勁，雖然最后寫出來了，但感覺代碼很冗余。討論有很多非常巧妙的辦法，需要運(yùn)用數(shù)學(xué)方法，我是絕對想不出來的。

　　我的思路是這樣的，題目意思是在小時(shí)數(shù)組{1,2,4,8} 和分鐘數(shù)組{1,2,4,8,16,32}中一共選擇N個(gè)數(shù)來組成一個(gè)時(shí)間。

　　那我們第一個(gè)要解決的問題是如何在一個(gè)數(shù)組中選出所有N個(gè)數(shù)的組合。

　　1、如何取出組合的第一個(gè)數(shù)？

　　我們從左往右，首先我們將a加入tmpList(臨時(shí)存儲(chǔ)排列的線性表)中，此后再從它下一個(gè)位置開始找第二個(gè)、第三個(gè)數(shù)字，最后生成排列存儲(chǔ)在結(jié)果中。我們再將1作為第一個(gè)元素開始處理后，趕緊把他刪了，再將b加入到tmpList中，此后再從它下一個(gè)位置開始找第二個(gè)、第三個(gè)數(shù)字，最后生成排列存儲(chǔ)在結(jié)果中....

　　也就是說處理第i個(gè)位置的元素時(shí)，就要考慮到i位置的所有取值，我們在處理為a的元素后，趕緊把他刪了處理為b的元素.....這樣第i個(gè)位置就有所有的情況了。

　　

　　知道這個(gè)以后，我們就可以得到在一個(gè)數(shù)組中選出所有N個(gè)數(shù)的組合。

　　2、關(guān)于排列組合的一個(gè)典型的遞歸回溯框架是這樣的

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){if(tempList.size() == nums.length){list.add(new ArrayList<>(tempList));} else{for(int i = 0; i < nums.length; i++){if(tempList.contains(nums[i])) continue; // element already exists, skiptempList.add(nums[i]);backtrack(list, tempList, nums);tempList.remove(tempList.size() - 1);}} }

　　當(dāng)我們分別取出小時(shí)和分鐘的各種可能情況，再次做他們的笛卡爾積，從而生產(chǎn)所有的時(shí)間可能。　　

　　很抱歉的是，這道題并不需要嚴(yán)格的遞歸回溯框架，我從而使用了簡單使用了深搜。

/*** * @param arr 待產(chǎn)生排列的數(shù)組* @param index 位置下標(biāo)* @param cur 已經(jīng)找了CUR個(gè)數(shù)* @param n 一共要找N個(gè)數(shù)* @param val 已經(jīng)找到的數(shù)的和* @param res 當(dāng)招夠N個(gè)數(shù)后把他加入res表中* @param max val不能超過多少*/private void helper(int[] arr,int index,int cur,int n,int val,List<Integer> res,int max){if(cur>n)return;if(cur==n&&val<max)res.add(val);for(int i =index;i<arr.length;i++) {helper(arr, i+1,cur+1, n, val + arr[i],res,max);}}

Java題解

class Solution {public List<String> readBinaryWatch(int num) {int[] hour = {1,2,4,8};int[] minute ={1,2,4,8,16,32};List<Integer> hourList = new ArrayList<>();List<Integer> minuteList = new ArrayList<>();List<String> ans = new ArrayList<>();for(int i=0;i<=num;i++){helper(hour,0,0,i,0,hourList,12);helper(minute,0,0,num-i,0,minuteList,60);for(int hi = 0;hi<hourList.size();hi++)for(int mi =0;mi<minuteList.size();mi++){String minVal = String.valueOf(minuteList.get(mi));if(minVal.length()<2)minVal = "0"+minVal;ans.add(hourList.get(hi)+":"+minVal);}hourList = new ArrayList<>();minuteList = new ArrayList<>();}Collections.sort(ans);return ans;}private void helper(int[] arr,int index,int cur,int n,int val,List<Integer> res,int max){if(cur>n)return;if(cur==n&&val<max)res.add(val);for(int i =index;i<arr.length;i++) {helper(arr, i+1,cur+1, n, val + arr[i],res,max);}}}

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/MrSaver/p/9962717.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode：二进制手表【401】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。