IP 到 CIDR

难度:

标签:

题目描述

代码结果

运行时间: 31 ms, 内存: 16.0 MB

/*
 * 题目思路:
 * 1. 将起始IP地址转换为整数。
 * 2. 根据需要的IP数量，找到最大的CIDR块。
 * 3. 根据找到的CIDR块，更新起始IP和剩余数量。
 * 4. 重复上述过程直到覆盖所有的IP地址。
 */

import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class IPtoCIDRStream {
    public List<String> ipToCIDR(String ip, int n) {
        long start = ipToLong(ip);
        return Stream.iterate(new long[]{start, n}, arr -> arr[1] > 0, arr -> {
            long mask = Math.max(33 - Long.numberOfTrailingZeros(arr[0] & -arr[0]), 33 - Integer.numberOfTrailingZeros(arr[1]));
            arr[0] += 1 << (32 - mask);
            arr[1] -= 1 << (32 - mask);
            return arr;
        }).map(arr -> longToIP(arr[0]) + "/" + Math.max(33 - Long.numberOfTrailingZeros(arr[0] & -arr[0]), 33 - Integer.numberOfTrailingZeros(arr[1])))
          .limit(n)
          .collect(Collectors.toList());
    }

    private long ipToLong(String ip) {
        String[] ipParts = ip.split("\\.");
        long result = 0;
        for (String part : ipParts) {
            result = result * 256 + Integer.parseInt(part);
        }
        return result;
    }

    private String longToIP(long ip) {
        return String.format("%d.%d.%d.%d", (ip >> 24) & 255, (ip >> 16) & 255, (ip >> 8) & 255, ip & 255);
    }
}

解释

方法:

这道题目要求将IP地址转换为CIDR表示法，覆盖给定数量的IP地址。题解的思路是首先将IP地址转换为整数形式，然后根据给定的数量计算出范围内的IP地址，并逐个将它们转换回CIDR表示法。在转换过程中，需要注意的是计算出最大可能的子网掩码位数，以覆盖尽可能多的IP地址。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在将IP地址转换为整数形式时，具体是如何处理四个分段的IP数据的？能否详细解释每一个位操作的目的和结果？

▷

在将IP地址转换为整数形式时，首先将IP地址按点分隔成四个部分，每部分代表一个8位的二进制数。这四个部分分别对应IP地址的四个字节。将这四个部分转换为整数后，通过位运算将它们组合成一个32位的整数。具体操作为：第一部分乘以2的24次方（即左移24位），第二部分乘以2的16次方（即左移16位），第三部分乘以2的8次方（即左移8位），第四部分保持不变。这样，第一部分在最高的8位，第二部分在接下来的8位，依此类推，组成了一个完整的32位整数。这个整数的二进制表示就是原IP地址的直接表达形式。

🦆

在计算CIDR子网掩码时，为什么要从末尾连续0的个数开始计算，这与CIDR的哪些特性相关？

▷

CIDR（无类别域间路由）表示法中，子网掩码表示为斜杠后的数字，这个数字表示网络地址中固定不变的位数。在计算子网掩码时，末尾连续0的个数表示当前可用于分配的IP地址范围的位数，这些0可以变化以形成新的IP地址。从末尾连续0的个数开始计算是为了确定在当前IP地址后可以连续分配的最大IP地址数量。例如，如果末尾有3个连续的0，则可以表示8个（2^3）连续的IP地址。这种计算方式直接关联到CIDR的网络和主机部分的划分，其中网络部分由1的位表示，主机部分由0的位表示。

🦆

循环中的条件`if intIPStart | int('1'*k, base=2) <= intIPEnd`是如何确保所选的子网掩码可以覆盖所需范围的IP地址的？能否解释这个位操作的逻辑？

▷

这个条件使用的是位或运算来确定所选子网掩码是否可以覆盖要求的IP地址范围。`int('1'*k, base=2)`生成一个数，其二进制表示中末尾有k个1，其余位都是0。当这个数与intIPStart进行位或运算时，它实际上是将intIPStart的末尾k个位设置为1，这代表了当前子网掩码下，intIPStart可以表示的最大IP地址。如果这个结果小于或等于intIPEnd，那么说明当前的子网掩码可以包括从intIPStart到intIPEnd的所有IP地址。这个操作保证了所选子网掩码的有效性，确保它能覆盖指定的IP地址范围。

🦆

在更新IP地址范围时，使用`intIPStart = (intIPStart | int('1'*k, base=2)) + 1`进行更新的原理是什么？这样做有什么特定的优势？

▷

这条更新语句的目的是将当前范围的起始IP地址更新为下一个子网的起始地址。`intIPStart | int('1'*k, base=2)`的操作将intIPStart的末尾k位设置为1，这表示当前子网可以包含的最大IP地址。通过在这个结果后加1，将IP地址更新到下一个可能的子网的起始地址。这样做的特定优势在于能够快速跳过当前已经计算和分配的CIDR块，直接移动到下一个需要计算的IP地址段，提高了算法的效率和执行速度。通过这种方式，我们可以保证每次循环处理的都是一个新的子网范围，避免了重复处理或IP地址的遗漏。

相关问题

复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

1 <= s.length <= 20
s 仅由数字组成

验证IP地址

给定一个字符串 queryIP。如果是有效的 IPv4 地址，返回 "IPv4" ；如果是有效的 IPv6 地址，返回 "IPv6" ；如果不是上述类型的 IP 地址，返回 "Neither" 。

有效的IPv4地址 是 “x1.x2.x3.x4” 形式的IP地址。其中 0 <= x_i <= 255 且 x_i 不能包含 前导零。例如: “192.168.1.1” 、 “192.168.1.0” 为有效IPv4地址， “192.168.01.1” 为无效IPv4地址; “192.168.1.00” 、 “[email protected]” 为无效IPv4地址。

一个有效的IPv6地址 是一个格式为“x1:x2:x3:x4:x5:x6:x7:x8” 的IP地址，其中:

1 <= x_i.length <= 4
x_i 是一个 十六进制字符串 ，可以包含数字、小写英文字母( 'a' 到 'f' )和大写英文字母( 'A' 到 'F' )。
在 x_i 中允许前导零。

例如 "2001:0db8:85a3:0000:0000:8a2e:0370:7334" 和 "2001:db8:85a3:0:0:8A2E:0370:7334" 是有效的 IPv6 地址，而 "2001:0db8:85a3::8A2E:037j:7334" 和 "02001:0db8:85a3:0000:0000:8a2e:0370:7334" 是无效的 IPv6 地址。

示例 1：

输入：queryIP = "172.16.254.1"
输出："IPv4"
解释：有效的 IPv4 地址，返回 "IPv4"

示例 2：

输入：queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
输出："IPv6"
解释：有效的 IPv6 地址，返回 "IPv6"

示例 3：

输入：queryIP = "256.256.256.256"
输出："Neither"
解释：既不是 IPv4 地址，又不是 IPv6 地址

提示：

queryIP 仅由英文字母，数字，字符 '.' 和 ':' 组成。

角矩形的数量打开转盘锁