【EASY】IP to CIDR

发布于: 2019-02-02 23:01
阅读: 79
评论: 0
喜欢: 1

问题

原题链接:https://leetcode.com/problems/ip-to-cidr/

Given a start IP address ip and a number of ips we need to cover n, return a representation of the range as a list (of smallest possible length) of CIDR blocks.

A CIDR block is a string consisting of an IP, followed by a slash, and then the prefix length. For example: "123.45.67.89/20". That prefix length "20" represents the number of common prefix bits in the specified range.

Example 1:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]
Explanation:
The initial ip address, when converted to binary, looks like this (spaces added for clarity):
255.0.0.7 -> 11111111 00000000 00000000 00000111
The address "255.0.0.7/32" specifies all addresses with a common prefix of 32 bits to the given address,
ie. just this one address.

The address "255.0.0.8/29" specifies all addresses with a common prefix of 29 bits to the given address:
255.0.0.8 -> 11111111 00000000 00000000 00001000
Addresses with common prefix of 29 bits are:
11111111 00000000 00000000 00001000
11111111 00000000 00000000 00001001
11111111 00000000 00000000 00001010
11111111 00000000 00000000 00001011
11111111 00000000 00000000 00001100
11111111 00000000 00000000 00001101
11111111 00000000 00000000 00001110
11111111 00000000 00000000 00001111

The address "255.0.0.16/32" specifies all addresses with a common prefix of 32 bits to the given address,
ie. just 11111111 00000000 00000000 00010000.

In total, the answer specifies the range of 10 ips starting with the address 255.0.0.7 .

There were other representations, such as:
["255.0.0.7/32","255.0.0.8/30", "255.0.0.12/30", "255.0.0.16/32"],
but our answer was the shortest possible.

Also note that a representation beginning with say, "255.0.0.7/30" would be incorrect,
because it includes addresses like 255.0.0.4 = 11111111 00000000 00000000 00000100 
that are outside the specified range.

Note:

  • ip will be a valid IPv4 address.
  • Every implied address ip + x (for x < n) will be a valid IPv4 address.
  • n will be an integer in the range [1, 1000].

分析过程

  • 输入:一个 ip 地址和一个整数 n
  • 输出:满足有 n 个不小于给定 ip 地址的 CIDR 块列表
  • 思路:题目读了半天也没明白啥意思。CIDR 块以 ip 地址斜杠一个整数组成,表示该 ip 地址的前整数位不变,剩下的几位随意组合,形成一个 ip 地址区间。题目要求输出几个 CIDR 块,输出一共有 n 个 ip 地址的 CIDR 块。
    • 起点就是输入的 ip 地址,由于 ip 不能小于当前的 ip,因此只能 0 变 1,不能 1 变 0。可以使用 ip & -ip 可以找到最后一个 1 的位置,来确定步长的最大值。
    • 由于给定了 n,ip 数量不能超过 n,因此需要根据 n 调整步长。
    • 确定步长以后更新 ip 和 n 即可。

解决方法

class Solution {
    
    func IPToInt64(ip: String) -> Int64 {
        // 假设都是合法的
        let strs = ip.components(separatedBy: ".")
        return Int64(strs[0])! << 24 + Int64(strs[1])! << 16 + Int64(strs[2])! << 8 + Int64(strs[3])!
    }
    
    func Int64ToIP(val: Int64, step: Int64) -> String {
        // 假设都是合法的
        return "\(val >> 24 & 255).\(val >> 16 & 255).\(val >> 8 & 255).\(val & 255)/\(32 - Int(log2(Float(step))))"
    }
    
    func ipToCIDR(_ ip: String, _ n: Int) -> [String] {
        var res = [String]()
        var val = IPToInt64(ip: ip)
        var n = Int64(n)
        while n > 0 {
            // val & -val 运算取的是 val 中从右往左第一个 1 所在位置
            var step = val & -val
            // 由于题目限定 n 个 ip,因此 step 不能超过 n
            while step > n {
                step = step >> 1
            }
            res.append(Int64ToIP(val: val, step: step))
            // 更新起点和 n
            val += step
            n -= step
        }
        
        return res;
    }
}

Thanks for reading.

All the best wishes for you! 💕