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;
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115321.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号