公司网站建设推进表,成都品牌策划设计公司,美橙互联同类型网站,便民网app下载8.复原ip地址 有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 . 分隔。 例如#xff1a;0.1.2.201 和192.168.1.1 是 有效 IP 地址#xff0c;但是 …8.复原ip地址 有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 . 分隔。 例如0.1.2.201 和192.168.1.1 是 有效 IP 地址但是 0.011.255.245、192.168.1.312 和 192.1681.1 是 无效 IP 地址。 给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 . 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。 其实本题与上一题很像都是用分割线在所给字符串里进行切割本题如果切割到255的情况就得终止以及题目要求中ip地址只有四段即出现三个逗号时就得终止
class Solution {
public:vectorstringresult;//由题本题返回的结果是由字符串组成的一维数组//判断是否为合法ip地址bool isValid(const string s,int start,int end){if (start end) {return false;}if(s[start] 0 start!end )//整数可以是单个0但是不能是由0前导的整数{return false;}int num 0;for(int istart;iend;i){if(s[i]9 || s[i]0)//非法数字{return false;}num num*10 (s[i]-0);//本题传入的数字是字符串类型要记得转成整型if(num 255)//非法{return false;}}return true;}void backtracking(string s,int startIndex,int pointSum){//终止条件if(pointSum3){if(isValid(s,startIndex,s.size()-1)true){result.push_back(s); } return;}
for(int istartIndex;is.size();i){if(isValid(s,startIndex,i)true)//判断子区间是否为有效{s.insert(s.begin() i 1 , .); // 在i的后面插入一个逗点coutpointSum;pointSum;backtracking(s,i2,pointSum);//因为加了逗号占一个位置所以应该传入i2pointSum--;//回溯s.erase(s.begin()i1);//回溯}else{//不合法break;}}}vectorstring restoreIpAddresses(string s) {result.clear();if(s.size()4 || s.size()12)return result;//剪枝backtracking(s,0,0);return result;}
}; 疑惑点 bool isValid(const string s,int start,int end) { if (start end) { return false; } 为什么要加上这个判断不加上的话101023这个示例就过不去 分析原因因为 backtracking(s,i2,pointSum);这里的i是两个两个加 ** 全过程 ** 初始条件 输入: 101023 我们调用 restoreIpAddresses 方法它会执行以下步骤 初始化 result 调用 backtracking(s, startIndex0, pointSum0)。 递归模拟 第一次递归 (初始状态) startIndex 0, pointSum 0 遍历 i 从 startIndex0 开始尝试插入 .。 子循环: i0 子区间: 1合法isValid(0,0) 返回 true。 插入 .s 1.01023pointSum 1。 递归调用 backtracking(s, startIndex2, pointSum1)。 第二次递归 startIndex 2, pointSum 1 遍历 i 从 startIndex2 开始尝试插入 .。 子循环: i2 子区间: 0合法isValid(2,2) 返回 true。 插入 .s 1.0.1023pointSum 2。 递归调用 backtracking(s, startIndex4, pointSum2)。 第三次递归 startIndex 4, pointSum 2 遍历 i 从 startIndex4 开始尝试插入 .。 子循环: i4 子区间: 1合法isValid(4,4) 返回 true。 插入 .s 1.0.1.023pointSum 3。 递归调用 backtracking(s, startIndex6, pointSum3)。 第四次递归出现问题的地方 startIndex 6, pointSum 3 此时 pointSum 3 需要检查剩下的子区间是否合法。 调用 isValid(s, startIndex6, end5)这里的 end5 是 s.size()-1。 问题 startIndex6但 end5导致 start end。 9.子集 给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的 子集 幂集。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1 输入nums [1,2,3]
输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2 输入nums [0]
输出[[],[0]] 由上图可知本题与之前的回溯问题最大的区别就是之前的回溯算法题收集的都是叶子节点但是本题收集的是除根结点外所有结点
class Solution {
public:vectorintpath;vectorvectorintresult;void backtracking(vectorintnums,int startIndex){result.push_back(path);//收集空集if(startIndexnums.size())//终止条件{return;}
for(int i startIndex;inums.size();i){path.push_back(nums[i]);backtracking(nums,i1);path.pop_back();}}vectorvectorint subsets(vectorint nums) {path.clear();result.clear();backtracking(nums,0);return result;}
};
无剪枝操作因为本题需要遍历整个树并记录每个结点 10.子集问题II 给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的 子集幂集。 解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。 这题升级的点在于去重操作 思路效仿组合总和II先将数组进行排序后再传入 class Solution {
public:vectorintpath;vectorvectorintresult;void backtracking(vectorintnums,int startIndex,vectorboolused){result.push_back(path);if(startIndexnums.size()){return;}for(int istartIndex;inums.size();i){if(i0 nums[i]nums[i-1] used[i-1]false)//相同元素会产生的结果已经收集过了{continue;}path.push_back(nums[i]);used[i]true;backtracking(nums,i1,used);used[i]false;//回溯path.pop_back();}}vectorvectorint subsetsWithDup(vectorint nums) {path.clear();result.clear();vectorboolused(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums,0,used);return result;}
};
