专门做图片的网站cms,百度搜索提交入口,cms系统主要功能,哪个做企业网站代码随想录–回溯部分
day 24 休息 day 25 回溯第三天 文章目录 代码随想录--回溯部分一、力扣93--复原IP地址二、力扣78--子集三、力扣90--子集Ⅱ 一、力扣93–复原IP地址
代码随想录题目链接#xff1a;代码随想录 有效 IP 地址 正好由四个整数#xff08;每个整数位于 0…代码随想录–回溯部分
day 24 休息 day 25 回溯第三天 文章目录 代码随想录--回溯部分一、力扣93--复原IP地址二、力扣78--子集三、力扣90--子集Ⅱ 一、力扣93–复原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 中的任何数字。你可以按 任何 顺序返回答案 简单来说就是穷举把一个数组按照规则分成四串所有的可能性
类似分割回文串但是需要修改“回文串”的判断逻辑
把切下来的子串用于判断当其开头不是0且整体在0-255之间则可以下一步递归否则不递归
代码如下
class Solution {
public:vectorstring result;bool isValid(const string s){int num 0;if (s.size() 1 s[0] 0|| !s.size()) return false;else {for (int i 0; i s.size(); i) {if (s[i] 9 || s[i] 0) return false;num num * 10 (s[i] - 0);if (num 255) { return false;}}if(num 255 || num 0) return false;return true;}}void backTracking(string s, int startIndex, int pointNum){if(pointNum 3){string temp string(s.begin() startIndex, s.end());if(isValid(temp)){result.push_back(s); }return;}for(int i startIndex; i s.size(); i ){string test string(s.begin() startIndex, s.begin() i 1);if(isValid(test)) {s.insert(s.begin() i 1, .);pointNum ;backTracking(s, i 2, pointNum);s.erase(s.begin() i 1);pointNum --;}else break;}}vectorstring restoreIpAddresses(string s) {if (s.size() 4 || s.size() 12) return result;backTracking(s, 0, 0);return result;}
};切割字符串这里需要注意是左闭右开的
所以是startIndex i 1
二、力扣78–子集
代码随想录题目链接代码随想录 给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的 子集幂集。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 非常像力扣77–组合的问题只不过是k在动态的变化
只要在判断return的条件上修改一下就行了
不再需要判断是否能够加入result中也不用中断后续的递归只管让代码运行即可
这样就能做到遍历完整的树每次回溯都需要把自身加入结果中不需要判断了
代码如下
class Solution {
public:vectorint path;vectorvectorint result;void backTracking(vectorint nums, int startIndex){result.push_back(path);for(int i startIndex; i nums.size(); i ){path.push_back(nums[i]);backTracking(nums, i 1);path.pop_back();}}vectorvectorint subsets(vectorint nums) {backTracking(nums, 0);return result;}
};输入 nums [1,2,3] 输出 [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]] 从输入输出也能看出回溯的顺序先是搜索完1向下的一整串返回后从2继续向下搜索
所以每层都需要记录自己不然会漏掉
三、力扣90–子集Ⅱ
代码随想录题目链接代码随想录 给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的 子集幂集。 解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。 不同于子集这次给的num会存在重复数字输出要去重
思想和组合总和Ⅲ是一样的对nums排序并且通过used数组记录回溯层数
这样判断前一位和后一位是否相同且是否在一层就可以做到去重复了
代码如下
class Solution {
public:vectorint path;vectorvectorint result;vectorbool used;void backTracking(vectorint nums, int startIndex){result.push_back(path);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);path.pop_back();used[i] false;}}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(), nums.end());used vectorbool(nums.size(), false);backTracking(nums, 0);return result;}
};
