创新工场涂鸦移动2018校园招聘测试题-软件工程师-编程题一

发表于 | 分类于 ，

题目

描述

写一个算法判断某个字符串是不是一个合法的IP地址。

输入

1 行, 任意长度字符串

输出

1 行, 若字符串为合法 IP 地址,则输出 1,否则输出 0

Example

Input

::0.0.0.0

Output

1

题解

据 IPv6,IPv6 判断

  • IPv4
    • 点分十进制表示
    • 分四段,每段由一个值小于 256 大于等于 0 的数字组成
  • IPv6
    • 冒分十六进制表示
    • 分八段,每段由四位十六进制数字组成
    • 可以省略前导 0,若连续 x 段值都为零,则可以用 :: (双冒号)来代替,若同时存在多段连续 0 段,则只能压缩其中一段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>

using namespace std;
//判断IP
bool judgeIP(string ip)
{
    //ipv4,ipv6分隔符
    char delmtr6=':',delmtr4='.';
    //分隔符位置
    int d6,d4;
    //是否存在ipv4,ipv6分隔符
    bool isV4=0,isV6=0;

    //获得 ipv4 第一个分隔符位置,ipv6 最后一个分隔符位置
    d4=ip.find(delmtr4),d6=ip.find_last_of(delmtr6);

    //若两者都不存在,不合法
    if(d6==string::npos&&d4==string::npos)
        return 0;
    //存在 ipv6 分隔符则可能为 ipv6
    if(d6!=string::npos)
        isV6=1;
    //若存在 ipv4 分隔符,则可能是 ipv4
    if(d4!=string::npos)
        isV4=1;
    //若两者都存在,且 ipv6 最后一个分隔符在前,ipv4 第一个分隔符在后,则有可能是兼容性 ip
    if(isV4>isV6&&d6>d4)
        return 0;

    // ipv6 连续分隔符的个数
    int nearD6;
    // ipv6 连续双分隔的对数
    int doubleD6;
    // ipv4,ipv6 分段段数
    int v4Part,v6Part;
    // ipv6 分段长度
    int v6PL;
    // v4PL 取值为 1,10,100,用于计算 v4PV
    int v4PL;
    // ipv4 分段值
    int v4PV;

    int i=ip.length()-1;

    //可能为ipv4
    if(isV4)
    {
        for(v4PV=0,v4Part=v4PL=1; i>=0; --i)
        {
            //当前为ipv4分隔符
            if(ip[i]==delmtr4)
            {
                //分隔符位于最后或分段值 v4PV>255 ,不合法
                if(i==ip.length()-1||v4PV>255)
                    return 0;
                //分段数 v4Part+1,还原 v4PL,v4PV
                ++v4Part,v4PL=1,v4PV=0;
                //若分段数 v4part>4,则不合法
                if(v4Part>4)
                    return 0;
                continue;
            }
            //计算分段值 v4PV
            else if(ip[i]>='0'&&ip[i]<='9')
                v4PV+=(ip[i]-'0')*v4PL,v4PL*=10;
            //读到 ipv6分隔符,或读到字符串首
            else if(ip[i]==':'||i==0)
            {
                //当前段的值 v4PV>255,或段数不足 4,不合法
                if(v4PV>255||v4Part<4)
                    return 0;
                //ipv4 部分识别完毕
                if(v4Part==4)
                    break;
            }
            //忽略空格
            else if(ip[i]==' ')
                continue;
            //出现除 ipv4/ipv6 分隔符,数字 0-9,空格,之外的字符,不合法
            else
                return 0;
        }
    }
    //可能为兼容性 ip 或 ipv6
    if(isV6)
    {
        //当前字符的后一个非 空格 字符
        char nextC=0;
        //ipv6初始化
        v6Part=1,nearD6=doubleD6=0,v6PL=1;
        //兼容ip初始化
        if(isV4)
            v6Part=2;
        for(i; i>=0; --i)
        {
            //当前为 ipv6 分隔符
            if(ip[i]==delmtr6)
            {
                nextC=ip[i];
                //当前字符的后一个字符同为 ipv6 分隔符
                if(nextC==delmtr6)
                {
                    //连续分隔符的长度 nearD6+1
                    ++nearD6;
                    //若连续分隔符长度 nearD6>2,则不合法
                    if(nearD6>2)
                        return 0;
                    //若连续长度为 2,则连续双分隔的对数 doubleD6+1
                    if(nearD6==2)
                        ++doubleD6;
                    //若连续双分隔的对数 doubleD6>1,不合法
                    if(doubleD6>1)
                        return 0;
                }
                //分段数 v6Part+1,还原 v6PL,统计下个分段
                ++v6Part,v6PL=1;
                //分段数 v6Part>8,不合法
                if(v6Part>8)
                    return 0;
            }
            //判断十六进制
            else if(ip[i]>='0'&&ip[i]<='9'||ip[i]>='A'&&ip[i]<='F'||ip[i]>='a'&&ip[i]<='f')
            {
                nextC=ip[i];
                //分段长度 v6PL>4,不合法
                if(v6PL>4)
                    return 0;
                //分段长度 v6Part+1
                ++v6PL;
                //清除连续分隔符的长度 nearD6
                nearD6=0;
            }
            //忽略空格
            else if(ip[i]==' ')
                continue;
            //出现除了 ipv6 分隔符,十六进制数 (0-9,a-f,A-F),空格 之外的字符,不合法
            else
                return 0;
        }
        //无简化全 0 分组但分段数 v6Part<8,不合法
        if((!doubleD6)&&v6Part<8)
            return 0;
    }
    return 1;
}
//测试
int main()
{
    string ip;
    while(cin>>ip)
    {
        cout<<judgeIP(ip)<<endl;
    }
}

调用 Windows 或 Linux API 间接判断

  • 通过 IP 地址转换函数函数 int inet_pton(int af, const char *src, void *dst) 进行判断
    • af 为地址簇,IPv4 取 AF_INET,IPv6 取 AF_INET6
    • src 为 IP 字符数组
    • dst 为用来存储转化后的 IP 地址的对象,IPv4 为 in_addr 结构体对象,IPv6 为 in6_addr 结构体对象
    • 若返回值为 1 则说明IP合法,0 说明参数 af 指定的地址族或 src 格式不对,<0 说明函数出错
  • Windows 和 Linux 系统下的函数名相同,但是实现不同,需要包含不同的头文件
    • Windows
1
2
#include <Ws2tcpip.h>
#pragma comment (lib, "Ws2_32.lib")
* Linux
1
2
3
#include <sys/socket.h>
#include <netinet/in.h>
#include<arpa/inet.h>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>

using namespace std;
//判断IP
bool judgeIP(char* ip)
{
    //IPv4地址对象
    in_addr dist4;
    //IPv6地址对象
    in6_addr dist6;
    //IPv4,IPv6 转换返回值
    int res4,res6;
    //获取 IPv4,IPv6 转换返回值
    res4=inet_pton(AF_INET, ip, (void *)&dist4);
    res6=inet_pton(AF_INET6, ip, (void *)&dist6);
    //判断
    return res4>0||res6>0;
}
//测试
int main()
{
    char ip[100];
    while(cin>>ip)
    {
        cout<<judgeIP(ip)<<endl;
    }
}