LeetCode93. 复原IP地址
题目链接:93. 复原IP地址
独上高楼,望尽天涯
想起来简单,写起来还是很难的一道题, 小错误频发。
慕然回首,灯火阑珊
首先,因为本题要求只能分割成四段,所以不能用start_index来判断是否终止,而是使用point_num是否等于3来判断,point_num等于3即已经分割出三段了,这时候只需要判断剩下的第四段是否合法即可。
其次,和之前的题目不同, 本题不需要单独维护一个path来保存临时结果,只需要在原s上加点即可。
最后,最好使用stol代替stoi防止整型溢出,同时需要提前判断输入的两个参数是否合法,即第一个参数必须小于等于第二个参数。
class Solution {
private:
vector<string> result;
bool isIP(const string& s, int start, int end) {
if (start > end) {
return false;
}
else if(end - start > 0 && s[start] == '0') {
return false;
}
else if (stol(s.substr(start, end - start + 1)) > 255) { // stol防止整型溢出
return false;
}
return true;
}
void backtracking(string s, int start_index, int point_num) {
if (point_num == 3) { // 注意使用的是point_num判断终止
if (isIP(s, start_index, s.size() - 1)) {
result.push_back(s);
}
return;
}
for (int i = start_index; i < s.size(); i++) {
if (isIP(s, start_index, i)) {
s.insert(i + 1, "."); // 直接修改s即可
point_num++;
backtracking(s, i + 2, point_num);
s.erase(i + 1, 1);
point_num--;
}
else {
break;
}
}
}
public:
vector<string> restoreIpAddresses(string s) {
backtracking(s, 0, 0);
return result;
}
};
LeetCode78. 子集
题目链接:78. 子集
独上高楼,望尽天涯
比较简单的一道题,和组合问题很像,区别在于组合问题收集的是叶子节点的结果,本题是收集所有节点的结果。
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int start_index) {
result.push_back(path); // 收集所有节点的结果
for (int i = start_index; i < nums.size(); i++) {
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};
慕然回首,灯火阑珊
想的一样。
LeetCode90. 子集II
题目链接:90. 子集II
独上高楼,望尽天涯
和前面的一道题非常像,这次写在i < start_index
上卡壳了,还需要时间消化。
慕然回首,灯火阑珊
理解“树层去重”和“树枝去重”非常重要
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int start_index) {
result.push_back(path);
for (int i = start_index; i < nums.size(); i++) {
if (i > start_index && nums[i] == nums[i-1]){ // 注意这里,i > start_index非常重要
continue;
}
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
backtracking(nums, 0);
return result;
}
};
标签:index,day28,nums,LeetCode90,start,vector,子集,result,backtracking
From: https://www.cnblogs.com/BarcelonaTong/p/17071145.html