学习目标：
- 93.复原IP地址
- 78.子集
- 90.子集II
学习内容：
93.复原IP地址
/class Solution {
public:// string path;vector<string> result;bool isValid(const string& s, int start, int end) {if(start>end)return false;if(s[start]=='0'&&(end-start) >= 1)return false;int num=0;for(int i=start;i<=end;i++){if(s[i]<'0'||s[i]>'9')//遇到异常字符return false;num = num * 10 + (s[i] - '0');if(num>255)return false;}return true;}void backtracking(string s,int startIndex, int pointNum){if(pointNum == 3){// 判断第四段子字符串是否合法，如果合法就放进result中if (isValid(s, startIndex, s.size() - 1)) {result.push_back(s);}return;}for(int i = startIndex;i<s.size();i++){if(isValid(s,startIndex,i)){s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点pointNum++;backtracking(s,i+2,pointNum);pointNum--;s.erase(s.begin() + i + 1); // 回溯删掉逗点}else{break;}}}vector<string> restoreIpAddresses(string s) {int startIndex =0;int pointNum=0;if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了backtracking(s,startIndex,pointNum);return result;}
};
错误以及注意事项
backtracking(s,i+2,pointNum);因为添加了一个点，所以应该从i+2开始下一轮回溯。- continue 用于跳过当前迭代，继续下一次迭代，而 break 用于立即退出当前循环。所以在发现s中的某一段已经不符合IP地址要求后应该立刻break跳出循环。
if(num>255||num<0) return false;不需要检查num<0，因为num 是无符号整数，不可能小于0。另外，对于当前数字的首位为0的情况，可以直接跳过而不用继续判断后续数字。这样可以提高效率和简化代码。if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了并没有想到这个
78.子集
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums,int startIndex){if(startIndex>nums.size())return;for(int i = startIndex;i<nums.size();i++){path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}result.push_back(path);}vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums,0);return result;}
};
错误以及注意事项
- 想了半天卡在了树没有画对。
//或者终止条件改改然后把收集的子集那一行放在上面
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己if (startIndex >= nums.size()) { // 终止条件可以不加return;}for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};
90.子集II
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums,vector<bool> used,int startIndex){if(startIndex > nums.size()){return;}for(int i = startIndex;i < nums.size();i++){ if(i > startIndex && nums[i]==nums[i-1] && used[i-1]==0){continue;}path.push_back(nums[i]);used[i]=true;backtracking(nums,used,i+1);used[i]=false;path.pop_back();}result.push_back(path);}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());vector<bool> used(nums.size(), false);backtracking(nums,used,0);return result;}
};
错误以及注意事项
- ac！但是要找时间刷排序。
continue和break的区别
在 C++ 中，continue 和 break 是两种用于控制流程的关键字，它们的作用和用法略有不同：
continue：continue语句用于终止当前迭代的循环，并开始下一次迭代。- 当程序执行到
continue语句时，它会跳过当前迭代中剩余的代码，直接开始下一次迭代。 - 主要用于在循环中执行一些条件检查，如果某些条件满足，就跳过当前迭代，执行下一次迭代。
示例：
for (int i = 0; i < 5; ++i) {if (i == 2) {continue; // 当 i 等于 2 时，跳过当前迭代，开始下一次迭代}cout << i << endl;
}
// 输出：
// 0
// 1
// 3
// 4
break：break语句用于立即终止当前所在的循环（for、while或do-while循环），并跳出该循环。- 当程序执行到
break语句时，它会退出当前的循环，继续执行循环后面的代码。 - 主要用于在循环中满足某些条件时提前终止循环，通常用于在搜索或迭代过程中找到所需结果后立即退出循环。
示例：
for (int i = 0; i < 5; ++i) {if (i == 3) {break; // 当 i 等于 3 时，立即退出循环}cout << i << endl;
}
// 输出：
// 0
// 1
// 2
总之，continue 用于跳过当前迭代，继续下一次迭代，而 break 用于立即退出当前循环。
学习时间：
2024.2.22 19:30-21:44
