您的位置:首页 > 文旅 > 旅游 > 算法day23| 93.复原IP地址、78.子集、90.子集II

算法day23| 93.复原IP地址、78.子集、90.子集II

2024/12/23 9:29:00 来源:https://blog.csdn.net/2402_84438596/article/details/142062645  浏览:    关键词:算法day23| 93.复原IP地址、78.子集、90.子集II

算法day23| 93.复原IP地址、78.子集、90.子集II

  • 93.复原IP地址
  • 78.子集
  • 90.子集II

93.复原IP地址

有效 IP 地址 正好由四个整数(每个整数位于 0255 之间组成,且不能含有前导 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 中的任何数字。你可以按 任何 顺序返回答案。

示例 1:

输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]

示例 2:

输入:s = "0000"
输出:["0.0.0.0"]

示例 3:

输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示:

  • 1 <= s.length <= 20
  • s 仅由数字组成
class Solution {
public:vector<string> result;bool effetive(string s, int start, int end){if(start>end)return false;if(s[start]=='0'&&end!=start)return false;int sum=0;for(int i=start;i<=end;i++){if(s[i]<'0'||s[i]>'9')return false;sum=sum*10+(s[i]-'0');if(sum>255)return false;}return true;}void backtracking(string &s,int startIndex, int pointNum){if(pointNum==3){if(effetie(s,startIndex,s.size()-1))result.push_back(s);return;}for(int i=startIndex;i<s.size();i++){if(effetive(s,startIndex,i)){s.insert(s.begin()+i+1,'.');pointNum++;backtracking(s,i+2,pointNum);s.erase(s.begin()+i+1);pointNum--;}elsebreak;}return;}vector<string> restoreIpAddresses(string s) {backtracking(s,0,0);return result;}
};

易错点:

  • 对于effective函数的判断,注意传进来的start和end的含义都是下标,再for循环的时候直接用,不能减一
  {sum=sum*10+(s[i]-'0');if(sum>255)return false;}

if(sum>255)一定要写在for循环内部,不要等它全部遍历完再判断,因为这有可能会超过int的范围

  • backtracking(s,i+2,pointNum);,下一层的startIndex从i+2开始,因为此时的i+1已经变成了‘.’

难点:

  • 采用pointNum来辅助判断终止条件,同时也满足了题目要求,一举两得
  • 在回溯函数内,如果一层中出现了不满足的情况,直接舍弃这一层。所以是break,而不是continue

78.子集

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的

子集(幂集)。

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

示例 1:

输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2:

输入:nums = [0]
输出:[[],[0]]

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums,int startIndex){if(startIndex==nums.size())return;for(int i=startIndex;i<nums.size();i++){path.push_back(nums[i]);result.push_back(path);backtracking(nums,i+1);path.pop_back();}return;}vector<vector<int>> subsets(vector<int>& nums) {result.push_back(path);backtracking(nums,0);return result;}
};

这题是集合问题的模板题,先在草稿纸上画出树形图,然后要原有的思路分析即可

易错点:

  • result要先插入一个空的path

90.子集II

给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的

子集(幂集)。

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

示例 1:

输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2:

输入:nums = [0]
输出:[[],[0]]

提示:

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

易错点:

  • 由于used数组需要初始化,而且需要借助nums.size()这一条件,所以只能在主函数里面,并代入回溯函数,不能作为全局变量。
sort(nums.begin(),nums.end());
  • 去重操作必须要先排序,现有排序才能有去重

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com