尚仁网站建设,手机怎么制作网站教程视频教程,动态图表制作方法,做a爱片网站题目#xff1a;93.复原IP地址、78.子集、90.子集II
参考链接#xff1a;代码随想录
93.复原IP地址
思路#xff1a;本题的思路和上题切割回文串类似#xff0c;也是先要写一个判断函数#xff0c;然后一个个切割。对返回条件#xff0c;如果路径长度已经为4#xff…题目93.复原IP地址、78.子集、90.子集II
参考链接代码随想录
93.复原IP地址
思路本题的思路和上题切割回文串类似也是先要写一个判断函数然后一个个切割。对返回条件如果路径长度已经为4则可以判断是否切割完毕如果已经切割到最后则可以把path加入结果for循环用于判断end即切割位置递归用于逐个往后切割。时间复杂度O(n*2^n)。
class Solution {
public:bool isValidIp(string s,int begin,int end){//同样我们尽量不用子串使用begin和end,[begin,end)if(end-begin1||end-begin1end-begin3s[begin]!0){//长度符合要求,长度为1时可以为任何值长度为2和3的时候必须满足首位不为0string s1string(s.begin()begin,s.begin()end);//生成子串使用substr函数也可以int istoi(s1);//转换为intif(i0i255){return true;}}return false;}string strToIP(vectorstring path){//将向量转换为IP地址string ip;ippath[0];ip.push_back(.);ippath[1];ip.push_back(.);ippath[2];ip.push_back(.);ippath[3];return ip;}vectorstring ans;vectorstring path;//用于记录路径void backtracking(const string s,int begin,int end){//end才是第一次切割的位置!if(path.size()4){//已经达到4的长度if(ends.size()){//end越界说明已经全部选完了ans.push_back(strToIP(path));}return;}for(int iend;is.size();i){if(!isValidIp(s,begin,i)){//第一次切割不满足直接往后切continue;}path.push_back(string(s.begin()begin,s.begin()i));backtracking(s,i,i1);//如果切到结尾i1size1path.pop_back();}}vectorstring restoreIpAddresses(string s) {backtracking(s,0,1);return ans;}
};这里有一个问题比如25525511135如果切割了2,5,5这时判断最后一个不管怎么切割都要进入下一层递归实际上这时候已经不可能完成结果可以进行剪枝处理。可以根据begin和path大小来剪枝当path长度为1时如果剩余长度size-begin9则剪枝当path长度为2时剩余长度size-begin6则剪枝当path长度为3时剩余长度size-begin3则剪枝。可以将其写入for循环的条件判断中。
for(int iend;is.size()s.size()-begin3*(4-path.size());i)想这个剪枝用了很长时间在面试的时候如果能通过就不要细想剪枝了。 标答使用的是左闭右闭区间增加了一个变量portNum用于记录逗点个数直接在原来的字符串上增加逗点分割空间占用比我们更小。标答也没有完全剪枝只是粗略的根据总长度剪枝了一下。 标答
class Solution {
private:vectorstring result;// 记录结果// startIndex: 搜索的起始位置pointNum:添加逗点的数量void backtracking(string s, int startIndex, int pointNum) {if (pointNum 3) { // 逗点数量为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)) { // 判断 [startIndex,i] 这个区间的子串是否合法s.insert(s.begin() i 1 , .); // 在i的后面插入一个逗点pointNum;backtracking(s, i 2, pointNum); // 插入逗点之后下一个子串的起始位置为i2pointNum--; // 回溯s.erase(s.begin() i 1); // 回溯删掉逗点} else break; // 不合法直接结束本层循环}}// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法bool isValid(const string s, int start, int end) {if (start end) {return false;}if (s[start] 0 start ! end) { // 0开头的数字不合法return false;}int num 0;for (int i start; i end; i) {if (s[i] 9 || s[i] 0) { // 遇到非数字字符不合法return false;}num num * 10 (s[i] - 0);if (num 255) { // 如果大于255了不合法return false;}}return true;}
public:vectorstring restoreIpAddresses(string s) {result.clear();if (s.size() 4 || s.size() 12) return result; // 算是剪枝了backtracking(s, 0, 0);return result;}
};时间复杂度O(3^4)直接根据IP地址的构成计算的时间复杂度。
78.子集
思路本题要考虑子集的元素个数在主函数中根据元素个数分类从0到nums.size()。在回溯函数中把元素个数k作为一个固定值当路径长度等于k时返回。其他步骤和前面题目就类似了。剪枝不再过细考虑。时间复杂度O(n^3*2^n)和前面的题目我们多写了一个for循环。
class Solution {
public:vectorvectorint ans;vectorint path;void backtracking(vectorint nums,int k,int begin){//k为长度,一直保持不变,begin为开始取的位置if(path.size()k){//路径长度为k返回ans.push_back(path);return;}for(int ibegin;inums.size()-1;i){path.push_back(nums[i]);backtracking(nums,k,i1);//开始选下一个path.pop_back();}}vectorvectorint subsets(vectorint nums) {for(int k0;knums.size();k){//根据长度分类0为空集backtracking(nums,k,0);}return ans;}
};看完标答发现可以不用在主函数中写for循环可以在每一层取元素的时候就直接将其加入ans中第一层取1个元素第二层取2个元素。 标答
class Solution {
public:vectorvectorint ans;vectorint path;void backtracking(vectorint nums,int begin){//k为长度,一直保持不变,begin为开始取的位置if(beginnums.size()){//开始位置已经到达末尾return;}for(int ibegin;inums.size()-1;i){path.push_back(nums[i]);ans.push_back(path);//每一层遍历都要直接将结果加入ansbacktracking(nums,i1);//开始选下一个path.pop_back();}}vectorvectorint subsets(vectorint nums) {ans.push_back(path);//先加入一个空集backtracking(nums,0);return ans;}
};时间复杂度O(n*2^n)。
90.子集II
思路结合之前used去重的思路加入上题即为答案。时间复杂度O(n*2^n)。
class Solution {
public:vectorvectorint ans;vectorint path;void backtracking(vectorint nums,int begin,vectorint used){ans.push_back(path);//先加入自己这样不用额外添加空集if(beginnums.size()){return;}for(int ibegin;inums.size();i){if(i0nums[i]nums[i-1]used[i-1]0){//两个相邻且前一个未使用过说明是同一层的直接跳过continue;}path.push_back(nums[i]);used[i]1;backtracking(nums,i1,used);path.pop_back();used[i]0;}}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(),nums.end());vectorint used(nums.size(),0);//先全部初始化为0backtracking(nums,0,used);return ans;}
};也可以不用used不过我们初学者最好用好理解。
