首页 > 代码库 > leetcode_401_Binary Watch_回溯法_java实现

leetcode_401_Binary Watch_回溯法_java实现

题目:

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 = 1
Return: ["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".

 

解题思路:

 回溯法特点:

1.递归  

2.有树形结构,对问题进行遍历  

3.最重要的一点就是碰到不符合的条件的分支停止递归,进行回溯。

4.得到最终结果进行回溯,再遍历下一种情况

     

 * 本题递归

 * 从问题抽象到子问题:

 * 问题:在0到9这10个位置上可以点亮n盏灯

 * 操作:在位置i(0=<i<=9)上点亮一盏灯

 * 操作后得到子问题:在i+1到9这些位置上可以点亮n-1盏灯

 *

 * 递归结束条件:n==0,当灯已经都点亮时,得到一个最终解,递归终止,逐步返回,同时也逐步回溯,把所有沿途点亮的灯都灭掉。

有一个小疑问点说明一下:例如当n=7,i=7时,也就是,当剩下的位置数小于还需要点亮的灯的数量时,这时候程序依然可以正确运行

因为这时候不等n减少到0,i 就会首先增大到大于9,for循环就会不执行,递归就会一层一层传递回来。

代码:

 1 public static List<String> readBinaryWatch(int num) {
 2         List<String> times = new ArrayList<String>(); //时间集合
 3         int[] watch = new int[10];  //数组表示灯的位置,下标为 0到3 表示 小时的最高位到最低位
 4         //下标为4到9表示分钟的最高位到最低位。
//例如:watch[0]的权是8,watch[3]的权是1,watch[4]的权是32,watch[9]的权是1
5 Trial(num, 0, watch, times); 6 return times; 7 } 8 //n代表亮灯的数量,a代表现在可亮灯位置的第一位(最后一位是 9) 9 //这个代表的含义是:在位置(以数组下标表示)a到9 可以点亮n盏灯,
//第一次调用时a=0,代表的意思是在数组下标 0到9 可以点亮n盏灯
10 public static void Trial(int n,int a,int[] watch,List<String> times){ 11 if(n==0) { 12 String time = ""; 13 int hour = SumOfIntArray(3, 0, watch); 14 time = time + hour + ":"; 15 int minute = SumOfIntArray(9, 4, watch); 16 if(minute<10) time = time+0+minute; 17 else time = time + minute; 18 times.add(time); 19 return; //递归返回,这句话关键代码,一定不要忘了!!! 20 //但是本程序这行不加不影响,大不了不返回上一层,接着执行,
//n减小成负数,a不停增加,直到大于9,再逐步返回。
21 } 24 for(;a<=9;a++){ 25 watch[a] = 1;//在a位置点亮一盏灯 26 //当不是下面这些情况时,递归循环,如果是的话,不进入循环,直接回溯 27 if( ! ((watch[0] == 1 && watch[1] == 1) || 28 (watch[4] == 1 && watch[5] == 1 && watch[6] == 1 && watch[7] == 1))){ 29 //进入递归循环,子问题的意思是:在位置(以数组下标表示)a+1到9 可以点亮n-1盏灯 30 Trial(n-1, a+1, watch, times); 31 } 32 watch[a]=0; //回溯 33 } 34 return; 35 } 36 public static int SumOfIntArray(int a,int b,int[] times){
//a是低位,b是高位,a是3或9,b是0或4 37 int sum = 0; 38 int mi = 0; 39 for(int i=a;i>=b;i--){ 40 sum = (int) (sum +times[i]*Math.pow(2, mi)); 41 mi++; 42 } 43 return sum; 44 }

 

leetcode_401_Binary Watch_回溯法_java实现