网站建设业务员沟通需求,泵 品牌网站建设,有实力自适应网站建设哪家好,旅游网页设计作品欣赏#x1f57a;作者#xff1a; 主页 我的专栏C语言从0到1探秘C数据结构从0到1探秘Linux菜鸟刷题集 #x1f618;欢迎关注#xff1a;#x1f44d;点赞#x1f64c;收藏✍️留言 #x1f3c7;码字不易#xff0c;你的#x1f44d;点赞#x1f64c;收藏❤️关注对我真的… 作者 主页 我的专栏C语言从0到1探秘C数据结构从0到1探秘Linux菜鸟刷题集 欢迎关注点赞收藏✍️留言 码字不易你的点赞收藏❤️关注对我真的很重要有问题可在评论区提出感谢阅读 文章目录 前言93. 复原 IP 地址解题思路AC代码 78. 子集解题思路AC代码 90. 子集 II解题思路AC代码 491. 递增子序列解题思路AC代码 46. 全排列解题思路AC代码 前言
本篇共5题附有解题思路和AC代码。
边听歌边刷起来吧~
Make Believe
93. 复原 IP 地址 链接93. 复原 IP 地址 解题思路 travalBack 函数是递归函数用于遍历字符串 s 中可能的 IP 地址组合。它有三个参数staticIndec 表示当前小节的起始位置dotCount 表示已经添加的逗号数量。 当 dotCount 等于 3 时说明已经添加了三个逗号此时可以判断第三个逗号后面的字符组成的字符串是否满足 IP 地址的要求。如果满足则将该情况存入 res 中。 在 travalBack 函数中使用循环来遍历从 staticIndec 开始到字符串末尾的位置。对于每一个位置 i判断从 staticIndec 到 i 组成的小节是否满足 IP 地址的要求。 如果满足条件则在 s 中插入逗号并递归调用 travalBack 函数同时更新 staticIndec 为 i2dotCount 加 1表示处理下一个小节。 在递归调用结束后需要将插入的逗号删除以便进行下一次循环。 isIPmember 函数用于判断一个字符串是否满足 IP 地址的要求。它将字符串转换为整数并进行一系列的判断条件包括长度不为 1 且以 0 开头、只包含数字字符等。 在 restoreIpAddresses 函数中首先对输入字符串 s 的长度进行判断如果小于 4 或大于 12则直接返回空结果。然后调用 travalBack 函数开始递归遍历。 最终返回存储所有满足条件的 IP 地址组合的 res。
AC代码
class Solution {
public:vectorstring res;//staticIndec是这小节的开始dotCount是添加逗号的数量void travalBack(string s,int staticIndec,int dotCount){if(dotCount3){//如果添加的逗号的数量等于3了就可以判断第三个逗号后面的字符组成的字符串是否满足条件满足就把这一种情况存到res中。if(isIPmember(s,staticIndec,s.size()-1))res.push_back(s);return;}for(int istaticIndec;is.size();i){if(isIPmember(s,staticIndec,i)){//判断这一节是否满足条件s.insert(s.begin() i 1 , .);//向s中插入逗号.travalBack(s,i2,dotCount1);//因为插入了逗号所以staticIndec要多加1s.erase(s.begin() i 1);}else break;} }bool isIPmember(string s,int l,int r){string str s.substr(l,r-l1);if(str.size()!1 str[0]0)return false;for(int i0;istr.size();i){if(str[i]9||str[i]0){return false;}}if(str)return false;if(stoll(str)255)return false;return true;}vectorstring restoreIpAddresses(string s) {if(s.size()4||s.size()12)return res;travalBack(s,0,0);return res;}
};78. 子集 链接78. 子集 解题思路 终止条件不需要写出来因为当staticIndexnums.size()时循环已经终止了 for循环内在进入下一个节点前先将自己这个节点载入path中出来时就删去 可以看作是二叉树的前序遍历
AC代码
class Solution {
public:vectorvectorint res;vectorint path;void travalBack(vectorint nums,int staticIndex){res.push_back(path);for(int istaticIndex;inums.size();i){path.push_back(nums[i]);travalBack(nums,i1);path.pop_back();}}vectorvectorint subsets(vectorint nums) {travalBack(nums,0);return res;}
};90. 子集 II 链接90. 子集 II 解题思路
在求组合三的时候讲过解题思路这题也是类似的参看《[算法训练营] 回溯算法专题(一)》
AC代码
class Solution {
public:vectorvectorint res;vectorint path;void travalBack(vectorint nums,int staticIndex,vectorbool used){res.push_back(path);for(int istaticIndex;inums.size();i){if(i0nums[i]nums[i-1]used[i-1]false){continue;}else{path.push_back(nums[i]);used[i]true;travalBack(nums,i1,used);used[i]false;path.pop_back();}}}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(),nums.end());vectorbool 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:vectorvectorint res;vectorint path;void travalBack(vectorint nums,int staticIndex){if(path.size()2){res.push_back(path);}unordered_setint umap;for(int istaticIndex;inums.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,i1);path.pop_back();}}}vectorvectorint findSubsequences(vectorint 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:vectorvectorint res;vectorint path;//排列和组合不同它在乎顺序和单次所以要使用一个数组used来记录是否使用过void travalBack(vectorintnums ,vectorbool used){//判断是否是全排列即包含所有元素if(path.size()nums.size()){res.push_back(path);return;}for(int i0;inums.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();}}vectorvectorint permute(vectorint nums) {vectorbool used(nums.size(),false);travalBack(nums,used);return res;}
};
