93.复原IP地址

虽然自己写的比较复杂，但还是自己独立写出来了。

自己写的时候遇到的问题有：

没搞清substr的parameter用处，第二个parameter是定义该string的长度，而不是endpoint在哪。我还以为是start_index和i的边界设的不管用了呢。

检查字符串不能有先导0的时候，把string单纯为0的情况给误杀了。

class Solution {
public:
 vector<string> res;
 vector<string> cur_path;
 void backtracking(string s,int start_index){
     if(start_index >= s.length()){
         if(checkValidIp(cur_path)){
             string valid_path;
             for(int i=0; i<cur_path.size(); i++){
                 if(i != cur_path.size()-1){
                     valid_path = valid_path + cur_path[i] + '.';            
                 }
                 else{
                     valid_path = valid_path + cur_path[i];
                 }
             }
             res.push_back(valid_path);
         }
         return ;
     }
     for(int i=start_index; i<s.length(); i++){
         if(i-start_index < 3){
             string temp_s = s.substr(start_index,(i-start_index+1));
             cur_path.push_back(temp_s);
             backtracking(s,i+1);
             cur_path.pop_back();
         }
     }
 }
 bool checkValidIp(vector<string> path_collection){
     for(int i=0; i<path_collection.size(); i++){
         if(path_collection[i].length()!= 1 && path_collection[i][0]== '0'){
             return false;
         }
         else{
             int path_to_num = stoi(path_collection[i]);
             if(path_to_num<0 || path_to_num>255){
                 return false;
             }
         }
     }
     if(path_collection.size()!=4){
         return false;
     }
     return true;
 }
 vector<string> restoreIpAddresses(string s) {
     backtracking(s,0);
     return res;
 }
};

看了Carl的答案，他首先是在主程序里检查了s的长度不能小于4 也不能大于12。也算是剪枝了。另外他是每要加一个num到path结果之前就检查它合不合规，不像我到了最后才检查。

78.子集

嘿嘿，灵机一动想出来了。（虽然瞟了一眼Carl的讲解）。其实就是在边界内把所有结果都加进去。考察的就是对回溯算法的了解透不透彻。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>& nums, int start_index){
        if(start_index <= nums.size()){
            res.push_back(path);
        }
        if(start_index > nums.size()){
            return ;
        }
        for(int i=start_index; i<nums.size(); i++){
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums,0);
        return res;
    }
};

90.子集II

这道题其实就是之前两道题的集合版。但是我在去重那步还是做错了，我想的是当i>0的时候且当前值和上个值一样，i++来进行跳过重复的值。但是其实跳过的话，应该用continue，而且应该是当start_index< i 的时候再跳过。毕竟当多层循环后，i初始的值就是大于0的，必须是大于start_index才说明目前的i不是for loop里第一次loop。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>& nums, int start_index){
        if(start_index <= nums.size()){
            res.push_back(path);
        }
        if(start_index > nums.size()){
            return ;
        }
        for(int i=start_index; i<nums.size(); i++){
            if(start_index<i && nums[i] == nums[i-1]){
                continue;
            }
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        backtracking(nums,0);
        return res;
    }
};

代码随想录算法训练营第二十七天| 回溯算法

93.复原IP地址

78.子集

90.子集II

CATALOG

FEATURED TAGS