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 = 1Return: ["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".
題目分析：狀態壓縮
我寫的渣渣代碼 4ms
public class Solution { public final int hTime[] = {1, 2, 4, 8}; public final int mTime[] = {1, 2, 4, 8, 16, 32}; public int calOne(int num) { int ans = 0; while(num != 0) { ans += (num & 1); num >>= 1; } return ans; } public List readBinaryWatch(int num) { List ans = new ArrayList<>(); int all = 1 << 10; for (int i = 0; i < all; i ++) { if (calOne(i & (all - 1)) != num) { continue; } int h = (i & 15); int m = (i & 1008); Integer hnum = new Integer(0); Integer mnum = new Integer(0); for (int j = 0; j < 4; j ++) { if (((1 << j) & h) != 0) { hnum += hTime[j]; } } for (int j = 4; j < 11; j ++) { if (((1 << j) & m) != 0) { mnum += mTime[j - 4]; } } if (mnum < 60 && hnum < 12) { if (mnum < 10) { ans.add(hnum.toString() + ":0" + mnum.toString()); } else { ans.add(hnum.toString() + ":" + mnum.toString()); } } } return ans; }}
Discuss里大神的代碼，不過速度慢了點，跑了20+
public class Solution { public List readBinaryWatch(int num) { List ans = new ArrayList<>(); for (int h = 0; h < 12; h ++) for (int m = 0; m < 60; m ++) if (Integer.bitCount((h << 6) + m) == num) ans.add(String.format("%d:%02d", h, m)); return ans; }} 就愛閱讀www.92to.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20161206/63525.html
文章列表
留言列表
