93. 复原 IP 地址
思路
1.先判断每个部分是不是符合要求
2.如果符合要求则加入path，递归下一层
3.当遍历到字符串末尾，如果有四层，则加入结果，否则直接返回。
实现
点击查看代码
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
backTracking(s, 0, path,0);
return result;
}
string path;
vector<string> result;
void backTracking( string& s, int startIndex, string path, int count) {
if(startIndex == s.size()) {
if(count == 4) {
path.pop_back();
result.push_back(path);
}
return;
}
for(int i = startIndex; i <= startIndex+2 && i < s.size(); i++) {
if(!isValid(s,startIndex,i)){
continue;
}
backTracking(s, i+1, path + s.substr(startIndex, i - startIndex + 1)+'.', count+1);
}
}
bool isValid(string s, int start, int end) {
if(end-start > 0 && s[start] == '0') return false;
string n = s.substr(start, end - start + 1);
int m = stoi(n);
if(m < 0 || m > 255) return false;
return true;
}
};
78.子集
思路
自己问题相比于组合问题更加简单，只是结果变成了求所有的节点。
实现
点击查看代码
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
backTracking(nums, 0);
return result;
}
vector<int> path;
vector<vector<int>> result;
void backTracking(const 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();
}
}
};
90. 子集 II
思路
增加一个去重的逻辑
实现
点击查看代码
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
backTracking(nums, 0);
return result;
}
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++) {
if(i > startIndex && nums[i] == nums[i-1]) continue;
path.push_back(nums[i]);
backTracking(nums, i+1);
path.pop_back();
}
}
};