P2508. IPv4地址转换成整数

解题思路

本题涉及的进制转换和 Python 内置函数的知识可查看 算法题中常用数学概念、公式、方法汇总 和 Python 常用内置函数、方法、技巧汇总 相关内容。

非法判断

对于输入的原字符串 s，我们可以很方便地使用 split() 方法，以 "#" 为分隔符，将其分割为一个字符串列表 IPv4_lst。然后对 IPv4_lst 考虑以下特殊情况：

• IPv4_lst 长度不为 4
• IPv4_lst 中存在某一个字符串，不是纯数字
• IPv4_lst[0] 即第一小节的取值范围不是 1-128
• IPv4_lst[1]、IPv4_lst[2]、IPv4_lst[3] 即第二、三、四小节的取值范围不是 0-255

如果满足以上任何一种情况，输入均是一个 非法字符，应该输出 "invalid IP"。对应代码：

转换过程

对于一个合法的输入，我们需要理解将 IPv4 地址转换为整数是一个怎么样的过程，再将抽象的过程翻译成代码即可。属于一道非常纯粹的 模拟题。

以 128#0#255#255 转为 2147549183（0x8000ffff）为例，其过程如下：

1. 以 # 为分隔符，将原输入字符串分割为四个小节，为 4 个十进制数整数，即 IPv4_lst = ["128", "0", "255", "255"]。

2. 每个十进制整数都可以转换为一个 两位的十六进制整数，即 ["80", "00", "ff", "ff"]。 十进制的 128、0、255、255 分别对应十六进制的 80、00、ff、ff。 之所以是两位的十六进制整数，是因为取值范围（0-255）的最大值，十进制的 255 = 16 * 16 - 1，等于十六进制的 "ff"，最多为两位。 直接使用 hex() 内置函数对原十进制数进行转换，将得到一个形如 "0xFF" 的字符串，其中前缀 "0x" 表示这是一个十六进制数。在这里需要使用 切片 对 "0x" 进行去除。 如果原十进制数小于 16，那么转换后的数字位数为 1，需要在前面补一个 "0"，才能使得其十六进制数的位数保持为 2。譬如十进制的 15，其十六进制为 "f"，位数为 1 位，需要在前面补一个 "0" 将其变成 "0f"。

3. 将上述的 4 个两位的十六进制整数进行拼接，得到一个 八位的十六进制数 "8000FFFF"。

4. 将这个八位的十六进制数转化为十进制整数，得到答案 2147549183。

把所有代码组织在一起就是答案了。

复杂度分析 设输入字符串长度为 L（合法输入至多十几个字符）。

• 时间复杂度：O(L)。按 "#" 分割、isdigit 纯数字检查、各小节的范围判断，都只是对输入做常数趟线性扫描，代价 O(L)；合法时的转换阶段对固定的 4 个小节各做一次十进制转十六进制（每段数值不超过 255，结果至多两位）、必要时补前导 0、拼接成 8 位十六进制串再用 int(…, base=16) 转回十进制，操作对象长度都有常数上界，整体是常数代价。因此瓶颈就在线性的输入扫描上，实际工作量接近常数。
• 空间复杂度：O(1)。只保存 4 个小节的字符串及其两位十六进制形式，以及 isError 等常数个变量，长度均有常数上界。