401. Binary Watch -- back tracking

发布时间：2020-12-14 04:14:56 所属栏目：大数据来源：网络整理

导读：题意：给你个二进制手表，上面有两排LED等，第一排为hour,第二排为minutes。? ? ? ? ? ? ?告诉你表上有n 个LED 灯亮着，输出所有可能的时间。题解：? 把上面 10个 LED 等抽象成10个数 0~9，现在亮着 n （n9) 个灯，表示从 nums 里取出? n 个数的“排列

题意：给你个二进制手表，上面有两排LED等，第一排为hour,第二排为minutes。?

? ? ? ? ? ?告诉你表上有n 个LED 灯亮着，输出所有可能的时间。

题解：? 把上面 10个 LED 等抽象成10个数 0~9，现在亮着 n （n<9) 个灯，表示从 nums 里取出? n 个数的“排列”?

?int[] nums = {0,1,2,3,4,5,6,7,8,9};

对于求解时间，可以用如下map,如果 num <=5 表示 mins，剩下的为hour
int[] map = {1,16,32,8};

需要注意判定不合法的时间， hour>=12,mins>=60 则不合法。还有注意输出格式， hour 可以是1位到2位， min 必须保持两位，也就是说 min<=9 前面要补0.?

code 如下：?

class Solution {
    public List<String> readBinaryWatch(int n) {
        
        int[] nums = {0,9};
        
        int[] map = {1,8};
        
        List<String> result = new ArrayList<>();
        
        dfs(new ArrayList<>(),result,nums,n,0,map) ;
        
        return result;
    }
    
    private void dfs(List<Integer> curResult,List<String> result,int[] nums,int n,int start,int[] map){
        if(curResult.size() == n){
             String time = convert_time(curResult,map);
             if(!time.equals("-1")) result.add(time);
              return;   
        }
        
        for(int i=start; i<nums.length; i++){
            curResult.add(nums[i]);
            dfs(curResult,i+1,map);
            curResult.remove(curResult.size()-1);
        }
    }
    
    private String convert_time(List<Integer> list,int[] map){
        int hour = 0;
        int min = 0;
        for(int num: list){
            if(num<=5){
                min += map[num];
            }
            else{
               hour += map[num]; 
            }
            
            if(min>=60 || hour>=12) return "-1";
        }
        
        return String.valueOf(hour) + ":" +(min < 10 ? "0"+ String.valueOf(min): String.valueOf(min));
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!