JLUVicent

90子集II&78子集&93复原IP地址

 
  • 2023年 03月14日
  • 0 阅读

day28

93.复原IP地址

题目链接：93. 复原 IP 地址

解题思路：参考 视频

回溯抽象为树结构，for横向遍历，递归纵向遍历，本题直接在字符串s中进行修改，传入三个参数，一个字符串s一个开始索引，一个点计数，当点计数到达三个还需要判断是否最后一段合法，然后进行递归，注意递归时候i+2，还有c++中的插入和删除的命令insert(s.begin()+i+1,’.’); erase(s.begin()+i+1)

93.复原IP地址

  • 如何判断字符串是否合法？

    1.字符串中存在非法字符

    2.字符串中有前导0

    3.字符串中的数大于255了

    nums = nums*10 + (s[i]-'0')

    4.开头索引大于结尾索引

class Solution {
public:
    //递归函数
    // 定义结果数组
    vector<string> result;
    void backtracking(string& s,int startIndex,int pointsum){   //还加const呢，被修改了 隔着卡半天
        // 确定终止条件
        if ( pointsum == 3){
            if(isVaild(s,startIndex,s.size()-1)){
                // 这里是判断最后一个分割点之后的元素，如255.255.255.368 判断369
                result.push_back(s);
                return;
            }
        }

        // 单层遍历逻辑
        for( int i = startIndex; i < s.size(); i++){
            if(isVaild(s,startIndex,i)){
                // cout<<s[i]<<endl;
                // s.insert(s.begin()+i+1,'.');
                s.insert(s.begin() + i + 1 , '.'); 
                pointsum +=1;
            
            // 递归
            backtracking( s, i+2,pointsum); //这里应该用i+2因为已经插入了一个.
            // 回溯
            s.erase(s.begin()+i+1);
            pointsum -= 1;
            }
            else{break;}
        }

    }

    // 判断字符串是否合法
    bool isVaild(const string& s,int start,int end){
        if( start > end){
            return false;   //如果左区间大于右区间，不合法
        }

        if( s[start] == '0' && start != end){
            //第一个数字为0不合法
            return false;
        }

        int num = 0;
        for( int i = start; i<=end; i++){
            if(s[i] > '9' || s[i] < '0' ){
                //非法字符
                return false;
            }
            num = num*10 + (s[i]-'0');  //这里字符串转换为数字的写法！！！
            if( num > 255 ){    //大于255不合法
                return false;
            }
        }
        return true;
    }

    vector<string> restoreIpAddresses(string s) {
        backtracking( s, 0,0);
        return result;

    }
};

78.子集

题目链接：78. 子集

解题思路：参考 视频

和组合问题差不错，只是收获结果的方式不一样，需要在树的每一层都收获结果，因此注意收获结果的位置。

class Solution {
public:

    // 定义结果数组
    vector<vector<int>> result;
    vector<int> path;
    void backtracking( vector<int>& nums, int startIndex ){
        // 开始收获结果
        result.push_back(path); //可以理解为开始就把空集加进去
        // 终止条件
        if( startIndex >= nums.size()) return;

        // 单层逻辑
        for( int i = startIndex; 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 result;

    }
};

90.子集II

题目链接：90. 子集 II

解题思路：

子集的思路加上去重的逻辑，组合II那块去重的逻辑

class Solution {
public:

    // 定义存放结果的全局变量
    vector<int> path;
    vector<vector<int>> result;
    void backtracking( vector<int>& nums,int startIndex,vector<bool>used){
        // 先收获结果
        result.push_back(path);
        if( startIndex >= nums.size()) return;

        // 单层逻辑
        for( int i = startIndex; i < nums.size(); i++){
            if( i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;  //确定前一个元素是否被使用过
            path.push_back(nums[i]);    //加入元素
            used[i] = true;
            backtracking(nums,i+1,used);
            // 回溯
            path.pop_back();
            used[i] = false;
            
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        // 对数组进行排序
        sort( nums.begin(), nums.end());        //排序
        vector<bool> used(nums.size(),false);   //定义使用数组
        backtracking( nums,0,used);
        return result;
    }
};
搜索