题意理解

IP地址作为一个字符串输入,要判断其是否合法,即判断每个数字是不是处于0/~255之间。

方法一

从左向右遍历字符串,按照字符'.'就将字符串分隔成4个子串,用stoi()函数将其转化为数字,然后再判断每个数字是否出于0/~255之间,有一个不处于,则该IP地址不合法。 同时,要判断是否分为了4个数字,数字前是否有'+',是否两个'.'连在一起,是否有'0'开头的数字(不为0)。

示意图如下:
alt

具体代码如下:

#include<iostream>
#include<string>
#include<cstdlib>

using namespace std;

int main()
{
    string s;
    while (cin>>s)
    {
        bool ip = true;
        int count=0;
        for (int i=0;i<s.size();i++)
        {
            int num = 0;
            string temp = "";
            while(s[i]!='.' && i<s.size())
            {
                temp = temp + s[i];
                i++;
            }
            count++;
            //判断是否出现0开头的数字(不是0),或者两个点连在一起的情况。
            if ((temp[0]=='0' && temp.size()>1) || temp.size()==0 
                || temp[0]=='+')
            {
                ip = false;
                break;
            }
            num = stoi(temp);
            if (num<0 || num>255)
            {
                ip = false;
                break;
            }
        }
        if (count!=4) ip = false;//判断是不是分隔为4个数字
        if (ip) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

时间复杂度: O(N)O(N)。遍历一遍IP地址字符串。
空间复杂度: O(1)O(1)。没有开辟新空间。

方法二

使用strtok()方法对字符串进行分割,注意其参数的形式分别为为char[]和const char*。

具体代码如下:

#include<iostream>
#include<string>
#include<string.h>
#include<stdio.h>
#include<cstdlib>

using namespace std;

int main()
{
    char s[100];
    while (cin>>s)
    {
        bool ip = true;
        const char *p = ".";
        char *split;
        int count=0;
        //使用strtok分割字符串
        split = strtok(s, p);
        while (split)
        {
            count++;
            string temp = split;
            if ((temp[0]=='0' && temp.size()>1) || temp.size()==0 
                || temp[0]=='+')
            {
                ip = false;
                break;
            }
            int num = stoi(split);
            split = strtok(NULL, p);
            if (num<0 || num>255)
            {
                ip = false;
                break;
            }
            
        }
        if (count!=4) ip=false;
        if (ip) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

时间复杂度: O(N)O(N)。遍历一遍IP地址字符串。
空间复杂度: O(1)O(1)。没有开辟新空间。