题意

判断给定ip是否合法

方法

内置库

对于这种大量场景地方都会用到的函数，如果是在面向用户生产代码中，尽可能的不要自己实现，而是使用很多人用过有保障的库函数

inet_pton这个函数在成功时返回1，失败时返回0，所以我们直接调用它即可

代码

#include<bits/stdc++.h>
#include<arpa/inet.h>
using namespace std;
int main(){
    string s;
    while(getline(cin,s)){
        struct sockaddr_in sa;
        printf("%s\n",inet_pton(AF_INET, s.c_str(), &(sa.sin_addr))?"YES":"NO");
    }
    return 0;
}

复杂度分析

时间复杂度: 对于地址，每一位解析都是常数的操作代价，所以时间复杂度为$O(n)O(n)$

空间复杂度: 主要消耗在字符串的存储，所以空间复杂度为$O(n)O(n)$

手动实现

一个ip实际上是由4个[0,255] 之间的值拼接而成, 所以验证其是否都在范围内即可

以题目的样例255.255.255.1000为例子

代码

#include<bits/stdc++.h>
#include<arpa/inet.h>
using namespace std;
bool valids(const char *s,int n){
    if(n == 0)return false;
    if(s[0] == '0' && n > 1)return false; // 前导零
    int v = 0;
    for(int i = 0;i<n;i++){
        if(!isdigit(s[i]))return false;
        v*=10;
        v+=s[i]-'0';
    }
    return v >= 0 && v <= 255;
}
void work(string &s){
    int n = s.length();
    int p = 0; // 字符串 起始位置
    int cnt = 0;
    for(int i=0;i<=n;i++){
        if(s[i] == '.' || s[i] == '\0'){
            if(!valids(s.c_str() + p,i-p)){
                printf("NO\n");
                return ;
            }
            p = i+1; // 下一个开始位置
            cnt ++;
        }
    }
    printf("%s\n",cnt == 4?"YES":"NO"); // 4位
}

int main(){
    string s;
    while(getline(cin,s)){
        work(s);
    }
    return 0;
}

复杂度分析

时间复杂度: 每一位解析都是常数的操作代价，所以时间复杂度为$O(n)O(n)$

空间复杂度: 主要消耗在字符串的存储，所以空间复杂度为$O(n)O(n)$