前言
本篇共5题，附有解题思路和AC代码。
边听歌边刷起来吧~
93. 复原 IP 地址
链接：93. 复原 IP 地址
解题思路
- travalBack 函数是递归函数，用于遍历字符串 s 中可能的 IP 地址组合。它有三个参数：staticIndec 表示当前小节的起始位置，dotCount 表示已经添加的逗号数量。
- 当 dotCount 等于 3 时，说明已经添加了三个逗号，此时可以判断第三个逗号后面的字符组成的字符串是否满足 IP 地址的要求。如果满足，则将该情况存入 res 中。
- 在 travalBack 函数中使用循环来遍历从 staticIndec 开始到字符串末尾的位置。对于每一个位置 i，判断从 staticIndec 到 i 组成的小节是否满足 IP 地址的要求。
- 如果满足条件，则在 s 中插入逗号，并递归调用 travalBack 函数，同时更新 staticIndec 为 i+2，dotCount 加 1，表示处理下一个小节。
- 在递归调用结束后，需要将插入的逗号删除，以便进行下一次循环。
- isIPmember 函数用于判断一个字符串是否满足 IP 地址的要求。它将字符串转换为整数，并进行一系列的判断条件，包括长度不为 1 且以 0 开头、只包含数字字符等。
- 在 restoreIpAddresses 函数中，首先对输入字符串 s 的长度进行判断，如果小于 4 或大于 12，则直接返回空结果。然后调用 travalBack 函数开始递归遍历。
- 最终返回存储所有满足条件的 IP 地址组合的 res。
AC代码
class Solution { public: vector<string> res; //staticIndec是这小节的开始，dotCount是添加逗号的数量 void travalBack(string& s,int staticIndec,int dotCount) { if(dotCount==3){//如果添加的逗号的数量等于3了就可以判断第三个逗号后面的字符组成的字符串是否满足条件，满足就把这一种情况存到res中。 if(isIPmember(s,staticIndec,s.size()-1))res.push_back(s); return; } for(int i=staticIndec;i<s.size();++i){ if(isIPmember(s,staticIndec,i)){//判断这一节是否满足条件 s.insert(s.begin() + i + 1 , '.');//向s中插入逗号"." travalBack(s,i+2,dotCount+1);//因为插入了逗号，所以staticIndec要多加1 s.erase(s.begin() + i + 1); } else break; } } bool isIPmember(string& s,int l,int r){ string str = s.substr(l,r-l+1); if(str.size()!=1 && str[0]=='0')return false; for(int i=0;i<str.size();++i){ if(str[i]>'9'||str[i]<'0'){ return false; } } if(str=="")return false; if(stoll(str)>255)return false; return true; } vector<string> restoreIpAddresses(string s) { if(s.size()<4||s.size()>12)return res; travalBack(s,0,0); return res; } };
78. 子集
链接：78. 子集
解题思路
- 终止条件：不需要写出来因为当staticIndex>nums.size()时，循环已经终止了
- for循环内：在进入下一个节点前先将自己这个节点载入path中，出来时就删去
- 可以看作是二叉树的前序遍历
AC代码
class Solution { public: vector<vector<int>> res; vector<int> path; void travalBack(vector<int>& nums,int staticIndex) { res.push_back(path); for(int i=staticIndex;i<nums.size();++i) { path.push_back(nums[i]); travalBack(nums,i+1); path.pop_back(); } } vector<vector<int>> subsets(vector<int>& nums) { travalBack(nums,0); return res; } };
90. 子集 II
链接：90. 子集 II
解题思路
- 在求组合三的时候讲过解题思路，这题也是类似的参看《[算法训练营] 回溯算法专题(一)》
AC代码
class Solution { public: vector<vector<int>> res; vector<int> path; void travalBack(vector<int>& nums,int staticIndex,vector<bool> used) { res.push_back(path); for(int i=staticIndex;i<nums.size();++i) { if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false) { continue; } else{ path.push_back(nums[i]); used[i]=true; travalBack(nums,i+1,used); used[i]=false; path.pop_back(); } } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<bool> used(nums.size(),false); travalBack(nums,0,used); return res; } };
491. 递增子序列
链接：491. 递增子序列
解题思路
- 终止条件：当path长度大于2时都可以保留，但是和之前不同在于不需要return，如果return会导致只有长度为2的path
- 这题需要去重但是不能使用排序，因为题目要求是原数组的递增子序列
- 在判断是否能够加入当前数字时的条件是：
- 如果当前的path不为空，那么前一个值必须比后一个值小，否则跳过
- 还有就是当前的值是否“用过”，这里需要注意一个点，在for循环之前要使用一个set来记录元素是否使用过，如果使用过就要跳过，避免重复
AC代码
class Solution { public: vector<vector<int>> res; vector<int> path; void travalBack(vector<int>& nums,int staticIndex) { if(path.size()>=2){ res.push_back(path); } unordered_set<int> umap; for(int i=staticIndex;i<nums.size();++i) { if((!path.empty()&&path.back()>nums[i])||umap.find(nums[i])!=umap.end()) { continue; } else{ path.push_back(nums[i]); umap.insert(nums[i]); travalBack(nums,i+1); path.pop_back(); } } } vector<vector<int>> findSubsequences(vector<int>& nums) { travalBack(nums,0); return res; } };
46. 全排列
链接：46. 全排列
解题思路
- 首先，定义了一个全局变量res，用于存储最终的结果，即全排列的集合。
- 定义了一个全局变量path，用于存储当前正在生成的一个排列。
- 定义了一个辅助函数travalBack，用于进行回溯遍历生成全排列。
- 在travalBack函数中，首先判断当前path的长度是否等于给定数组nums的长度，如果相等，说明已经生成了一个完整的排列，将其加入到res中，并返回。
- 如果path的长度不等于nums的长度，就需要继续生成排列。通过一个循环遍历nums数组的每一个元素。
- 在循环中，首先判断当前元素是否已经被使用过，即used[i]是否为true，如果是，则跳过当前元素，继续下一次循环。
- 如果当前元素没有被使用过，将其加入到path中，将used[i]设置为true表示该元素已经被使用。
- 然后，递归调用travalBack函数，继续生成下一个元素的排列。
- 在递归调用结束后，需要将used[i]重新设置为false，表示该元素未被使用。
- 同时，还需要将path中的最后一个元素移除，以便生成下一个排列。
- 在permute函数中，首先创建一个大小为nums长度的布尔型数组used，初始值都为false。
- 然后调用travalBack函数，开始生成全排列。
- 最后返回得到的全排列结果res。
AC代码
class Solution { public: vector<vector<int>> res; vector<int> path; //排列和组合不同，它在乎顺序和单次，所以要使用一个数组used来记录是否使用过 void travalBack(vector<int>&nums ,vector<bool> used) { //判断是否是全排列，即包含所有元素 if(path.size()==nums.size()){ res.push_back(path); return; } for(int i=0;i<nums.size();++i){ //used[i]等于true说明已经使用1过这个数了，就要跳过 if(used[i]==true)continue; path.push_back(nums[i]); used[i]=true; travalBack(nums,used); used[i]=false; path.pop_back(); } } vector<vector<int>> permute(vector<int>& nums) { vector<bool> used(nums.size(),false); travalBack(nums,used); return res; } };
