🌕 401. 二进制手表

难度: 🌕

问题描述

---

解法 1 - 枚举

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        // 思路：
        // 小时共有 [0, 11] 状态；分钟共有 [00, 59] 状态
        // 枚举所有可能状态，借助内置函数统计每个状态下 1 的个数，小时 + 分钟 == target 表示该数合法
        List<String> res = new ArrayList<>();
        for(int i = 0; i <= 11; i ++) {
            for(int j = 0; j <= 59; j ++) {
                int a = Integer.bitCount(i);
                int b = Integer.bitCount(j);
                if(a + b == turnedOn) {
                    // 添加该时刻到结果集中
                    StringBuilder sb = new StringBuilder();
                    sb.append(i).append(':');
                    if(j < 10) {
                        sb.append('0');
                    }
                    sb.append(j);
                    res.add(sb.toString());
                }
            }
        }
        return res;
    }
}

---

输出 1

---

解法 2 - 回溯

class Solution {
    int[] hours = new int[] {8, 4, 2, 1};
    int lenH = 4;
    ArrayList<Integer> hs;
    int[] minutes = new int[] {32, 16, 8, 4, 2, 1};
    int lenM = 6;
    ArrayList<Integer> ms;
    public List<String> readBinaryWatch(int turnedOn) {
        // 思路：
        // 回溯
        // 将总灯数分配为 小时 & 分钟，然后各自递归
        List<String> res = new ArrayList<>();
        for(int i = 0; i <= turnedOn; i ++) {
            hs = new ArrayList<>();
            mySolHour(i, 0, 0, 0);
            ms = new ArrayList<>();
            mySolMin(turnedOn - i, 0, 0, 0);
            for(int m: hs) {
                for(int n: ms) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(m).append(":");
                    if(n < 10) {
                        sb.append("0");
                    }
                    sb.append(n);
                    res.add(sb.toString());
                }
            }
        }
        return res;
    }

    private void mySolHour(int target, int prev, int index, int sum) {
        // 递归终止条件
        if(sum > 11) {
            return;
        }
        if(prev == target) {
            // 正好点亮了目标数的灯
            hs.add(sum);
            return;
        }
        if(index >= lenH) {
            return;
        }
        
        // 有 2 种选择，点亮 | 不点亮 当前灯
        mySolHour(target, prev, index + 1, sum); // 不点亮
        mySolHour(target, prev + 1, index + 1, sum + hours[index]);
    }

    private void mySolMin(int target, int prev, int index, int sum) {
        // 递归终止条件
        if(target < 0 || target > lenM) {
            return;
        }
        if(sum > 59) {
            return;
        }
        if(prev == target) {
            // 正好点亮了目标数的灯
            ms.add(sum);
            return;
        }
        if(index >= lenM) {
            return;
        }
        
        // 有 2 种选择，点亮 | 不点亮 当前灯
        mySolMin(target, prev, index + 1, sum); // 不点亮
        mySolMin(target, prev + 1, index + 1, sum + minutes[index]);
    }
}

---

输出 2