day28|93. 复原 IP 地址|Leetcode 78. 子集|90.子集II
Leetcode 93. 复原 IP 地址
链接:93. 复原 IP 地址
thought:
for循环遍历所有s的字符,当当前字符段满足条件,塞入path,并进行递归,寻找下一个字符段,直到有三个点的存在,若最后一个剩下的字符段也满足条件,直接塞入res,return即可。然后进行回溯,开始找下一个字符段
完整C++代码如下:
class Solution {
public:
vector<string> res;
string path;
int pointNum = 0;
vector<string> restoreIpAddresses(string s) {
backtracking(0, s);
return res;
}
void backtracking(int start, string s) {
if (pointNum == 3) {
string cur = s.substr(start);
if (isValid(cur)) {
res.push_back(path + cur);
}
return;
}
for (int i = start; i < s.length(); i++) {//本层找所有情况
string cur = s.substr(start, i - start + 1);
if (isValid(cur)) {//本层满足,塞进path并递归
int len = path.length();
path += cur + ".";//本层已确定
pointNum++;
backtracking(i + 1, s);//向下递归下一层
path = path.substr(0, len);//回溯
pointNum--;//回溯
} else {
break;//此情况已经没有后续向下递归的必要
}
}
}
bool isValid(string str) {
if (str.empty() || str.length() > 3 || (str[0] == '0' && str.length() > 1))
return false;
int num = stoi(str);
return num >= 0 && num <= 255;
}
};
Leetcode 78. 子集
链接:78. 子集
thought:
- 递归中处理随函数变化变量或储存结果变量的两种方法:1.设为全局变量 2.作为参数传入递归函数
- 本题只是递归的过程中,每轮递归都存储当前path
完整C++代码如下:
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>>res;
vector<int>path;
backTrack(nums,path,0,res);
return res;
}
void backTrack(vector<int>&nums,vector<int>&path,int start,vector<vector<int>>&res){
res.push_back(path);
for(int i=start;i<nums.size();i++){
path.push_back(nums[i]);
backTrack(nums,path,i+1,res);
path.pop_back();
}
}
};
Leetcode 90.子集II
链接:90.子集II
thought:
比上一题多的情况是数组中的数可以是重复的,先排序,避免重复存相同数组的情况
完整C++代码如下:
class Solution {
private:
void backtracking(vector<vector<int>>& ans,vector<int>& cur,vector<int>& nums, int start) {
ans.push_back(cur);
for(int i = start;i<nums.size();i++){
if(i>start && nums[i]==nums[i-1])continue;//避免重复情况,例如[1,2,2]第1和第2结合,第1和第3结合
cur.push_back(nums[i]);
backtracking(ans,cur,nums, i+1);//递归
cur.pop_back();//回溯
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> cur;
sort(nums.begin(), nums.end());
backtracking(ans,cur,nums, 0);
return ans;
}
};
原文地址:https://blog.csdn.net/m0_74509890/article/details/136917052
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!