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)


相关推荐

  • 教你搭建一套自己的SVN服务器

    教你搭建一套自己的SVN服务器想不想自己搭建一套SVN服务器?来吧!Followme!

  • T-SQL基础–TOP

    T-SQL基础–TOP

    2021年11月26日
  • A4988与42步进电机

    A4988与42步进电机A4988电机驱动板引脚VMOT:电源正(8~35V),供电机GND:电机接地2B,2A:电机绕组2控制引脚1A.1B:电机绕组1控制引脚VDD:驱动板电源正(3~5V)GND:驱动板地ENABLE:引脚低电平,A4988才能进行电机驱动工作(悬空为默认状态,可以正常工作),高电平,A4988将不会经行电机驱动工作MS1,MS2,MS3:用来改变驱动模式具体如图REST:低电平…

  • HTML5火焰文字特效DEMO演示

    效果展示:http://hovertree.com/texiao/html5/26/效果图:扫描二维码查看效果:或者关注微信公众号ihewenqi,发送我或者张国荣,可以查看效果。代码

    2021年12月22日
  • pycharm新建anaconda_anaconda怎么创建虚拟环境

    pycharm新建anaconda_anaconda怎么创建虚拟环境在anaconda中已经有了一个比较全的环境,希望在Pycharm中使用,但百度后发现网上的一些方法已经在新版Pycharm中不一样的,在此记录下:File-&gt;Settings-&gt;Project:[当前项目名称]单击设置图标,然后选择【Add…】然后就是定位到anaconda中已有环境的python.exe所在目录了假设环境名称是tensorflow,一般路径是:C:\Users\…

  • 分区容错性和可用性的区别

    分区容错性和可用性的区别分区容错性:因为网络等硬件引起的问题,一台服务器崩溃了,保证能在其他服务器上也能顺利完成业务。可用性:因为软件代码层面的问题,一台服务器上的服务崩溃了,保证能在其他服务器上完成该业务。区别:分区容错性更偏向于硬件引起的问题可用性更偏向于软件代码层面的问题…

发表回复

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

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