当前位置：首页 > article >正文

代码随想录算法训练营第二十一天 | LeetCode93.复原IP地址、LeetCode78.子集、LeetCode90.子集II

article 2024/11/7 22:53:06

代码随想录算法训练营第二十一天 | LeetCode93.复原IP地址、LeetCode78.子集、LeetCode90.子集II

01-1 LeetCode93.复原IP地址

相关资源

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

文章讲解：LeetCode93：复原IP地址

视频讲解：LeetCode：93.复原IP地址

题目：

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

第一想法：类似于回文子串，用"."进行分割

遇到的困难：这道题目写了好久好久才写出来，主要问题在于递归的终止条件不太清楚，并且判断每个整数段是否位于 0 到 255 之间组成，且不能含有前导 0写法上出错过。

实现：

class Solution {
public:
    vector<string> result;
    string str;
    bool judge(string& s, int start, int end){
        int count = 0;
        if(end-start+1>3){
            return false;
        }
        if(end==start){
            return true;
        }
        if(end==start+1){
            if(s[start]=='0'){
                return false;
            }
            else{
                return true;
            }
        }
        if(end==start+2){
            if(s[start]=='0'){
                return false;
            }
            else{
                count += (s[start]-'0')*100+(s[start+1]-'0')*10+s[start+2]-'0'; 
                if(count<=255){
                    return true;
                }
                else{
                    return false;
                }
            }
        }
        return false;       
    }

    void backtracking(string& s, int startIndex, int part){
        if(startIndex >= s.size()){
            return;
        }
        if(part == 3){
            if(judge(s,startIndex,s.size()-1)){
                string str_cut = s.substr(startIndex, s.size()-startIndex);
                string str_temp = str  + str_cut;
                result.push_back(str_temp);
            }
            return;
        }
        for(int i = startIndex; i <= startIndex + 2 && i < s.size(); i++ ){
            if(judge(s,startIndex,i)){
                string str_cut = s.substr(startIndex, i-startIndex+1);
                str = str + str_cut + ".";
                backtracking(s,i+1,part+1);
                for(int i = 0; i < str_cut.size() + 1; i++){
                        str.pop_back();
                }
            }
        }
        return;
    }
    vector<string> restoreIpAddresses(string s) {
        backtracking(s,0,0);
        return result;
    }
};

看完代码随想录之后的想法： 思路大差不差，但录哥直接在原字符串中insert和erease

ToDo：复习！

01-2 LeetCode78.子集

相关资源

题目链接：78. 子集
文章讲解：LeetCode78.子集
视频讲解：LeetCode：78.子集

题目：

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

第一想法：其实就是组合，但需要把空集加入结果集，并且每个叶子节点都要记录

实现：

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

看完代码随想录之后的想法：思路一致

ToDo：复习

01-3 LeetCode90.子集II

相关资源

题目链接：90. 子集 II

文章讲解：子集II

视频讲解： LeetCode：90.子集II

题目：

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

第一想法：和之前的组合总和II很相似，也是需要一个去重的过程

实现：

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

看完代码随想录之后的想法：思路一致

ToDo：勤加复习

查看全文

http://www.kler.cn/a/383579.html