代码随想录打卡第二十五天
代码随想录–回溯部分
day 24 休息
day 25 回溯第三天
一、力扣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且整体在0-255之间,则可以下一步递归,否则不递归
代码如下:
class Solution {
public:
vector<string> 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;
}
}
vector<string> 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:
vector<int> path;
vector<vector<int>> result;
void backTracking(vector<int> & 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();
}
}
vector<vector<int>> subsets(vector<int>& 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:
vector<int> path;
vector<vector<int>> result;
vector<bool> used;
void backTracking(vector<int> & 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;
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
used = vector<bool>(nums.size(), false);
backTracking(nums, 0);
return result;
}
};
原文地址:https://blog.csdn.net/weixin_48013375/article/details/140430786
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!