回溯法

401.二进制手表

题目

回溯类思路

  • ①画出递归树,找到状态变量(回溯函数的参数),这一步非常重要※
  • ②根据题意,确立结束条件
  • ③找准选择列表(与函数参数相关),与第一步紧密关联※
  • ④判断是否需要剪枝
  • ⑤作出选择,递归调用,进入下一层
  • ⑥撤销选择

①画出递归树,找到状态变量

灯的数目是越来越少的,参数这里可以使用num计数,当num减少到0时输出结果。index指示当前选择的节点。使用pair存储小时和分钟。

void backtrace(int num,int index,pair<int,int> &time){}

②根据题意,确立结束条件

 if(num==0){   
          if(time.first>11||time.second>59)
            return;
            string temp_hour=to_string(time.first);
            string temp_minute=to_string(time.second);
            if(temp_minute.size()==1){
               temp_minute.insert(0,"0");
            }
            ans.push_back(temp_hour+":"+temp_minute);
            return;
      }

③找准选择列表(与函数参数相关)

vector<int> watch={1,2,4,8,1,2,4,8,16,32};//前四号是小时,后面是分钟的二进制值
for(int i=index;i<10;i++){
     //一共十个待选项
}

④判断是否需要剪枝

 for(int i=index;i<10;i++){
       if(time.first>11||time.second>59)
            break;
       
 }

⑤作出选择,递归调用,进入下一层

 for(int i=index;i<10;i++){
       if(time.first>11||time.second>59)
            break;
         if(i<4){
             time.first+=watch[i];
         }else{
             time.second+=watch[i];
         }
         backtrace(num-1,i+1,time); //这里是i+1,之前的已经选过了
}

⑥撤销选择

 for(int i=index;i<10;i++){
       if(time.first>11||time.second>59)
            break;
         pair<int,int> temp=time;
         if(i<4){
             time.first+=watch[i];
         }else{
             time.second+=watch[i];
         }
         backtrace(num-1,i+1,time);
         time=temp;
 }

全部代码

class Solution {
 public:
  vector<string> ans;
  vector<int> watch={1,2,4,8,1,2,4,8,16,32};
  vector<string> readBinaryWatch(int num) {
      pair<int,int>time(0,0);
      backtrace(num,0,time);
      return ans;
  }
  void backtrace(int num,int index,pair<int,int> &time){
      if(num==0){   
          if(time.first>11||time.second>59)
            return;
            string temp_hour=to_string(time.first);
            string temp_minute=to_string(time.second);
            if(temp_minute.size()==1){
               temp_minute.insert(0,"0");
            }
            ans.push_back(temp_hour+":"+temp_minute);
            return;
      }
      for(int i=index;i<10;i++){
       if(time.first>11||time.second>59)
            break;
         pair<int,int> temp=time;
         if(i<4){
             time.first+=watch[i];
         }else{
             time.second+=watch[i];
         }
         backtrace(num-1,i+1,time);
         time=temp;
      }
  }
};

执行结果

image 98

One thought on “401.二进制手表

发表评论