首页 > 代码库 > leetcode第一刷_Restore IP Addresses
leetcode第一刷_Restore IP Addresses
字符串的问题真是难,一般递归比较好写代码,一般地归还会超时,而且测试用例特别多。。
这道题刚拿到手时直接慌了,这情况也太多了,后来冷静下来想想,其实还是比较单纯的。一个ip地址,肯定是四个整数加三个点构成,四个整数要满足什么呢,0~255嘛,还有呢,就是这四个整数必须正好把原来的字符串给用完。一开始忽略掉的一类测试用类是前面有0但实际这个数不是零的情况。
用什么来穷举呢,或者说穷举的对象是什么呢?当然是要插入的三个点的位置,数的有效范围很小,因此穷举的范围也很小,1~3个数位而已,代码一看,就明白是怎么回事了。我最开始的时候想着是把每一个小数字用substr存起来,然后最后拼接,这样的开销太大了,不建议。
bool isValide(string s, int start, int end){ if(end - start > 3) return false; if(s[start] == ‘0‘ && end-start>0) return false; int res = 0; for(int i=start;i<=end;i++) res = res*10+(s[i]-‘0‘); if(res<0||res>255) return false; return true; } class Solution { public: vector<string> restoreIpAddresses(string s) { vector<string> res; int len = s.length(); if(len<4) return res; string tp(len+3, ‘#‘); for(int i=0;i<3&&i<len-3;i++){ if(!isValide(s, 0, i)) continue; //cout<<i<<" i"<<endl; for(int j=i+1;j<i+4&&j<len-2;j++){ if(!isValide(s, i+1, j)) continue; //cout<<j<<" j"<<endl; for(int k=j+1;k<j+4&&k<len-1;k++){ //cout<<k<<" k"<<endl; if(!(isValide(s, j+1, k)&&isValide(s, k+1, len-1))) continue; //cout<<"**"<<endl; int index = 0, m = 0; while(index<=i) tp[m++] = s[index++]; tp[m++] = ‘.‘; while(index<=j) tp[m++] = s[index++]; tp[m++] = ‘.‘; while(index<=k) tp[m++] = s[index++]; tp[m++] = ‘.‘; while(index<len) tp[m++] = s[index++]; //cout<<tp<<endl; res.push_back(tp); } } } return res; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。