华为OD统一考试 - 根据IP查找城市

题目描述

某业务需要根据终端的IP地址获取该终端归属的城市，可以根据公开的IP地址池信息查询归属城市。

地址池格式如下：

城市名=起始IP,结束IP

起始和结束地址按照英文逗号分隔，多个地址段采用英文分号分隔。比如：

City1=1.1.1.1,1.1.1.2;City1=1.1.1.11,1.1.1.16;City2=3.3.3.3,4.4.4.4;City3=2.2.2.2,6.6.6.6

一个城市可以有多个IP段，比如City1有2个IP段。

城市间也可能存在包含关系，如City3的IP段包含City2的IP段范围。

现在要根据输入的IP列表，返回最佳匹配的城市列表。

注：最佳匹配即包含待查询IP且长度最小的IP段，比如例子中3.4.4.4最佳匹配是City2=3.3.3.3,4.4.4.4，5.5.5.5的最佳匹配是City3=2.2.2.2,6.6.6.6

输入描述

输入共2行。

第一行为城市的IP段列表，多个IP段采用英文分号 ';' 分隔，IP段列表最大不超过500000。城市名称只包含英文字母、数字和下划线。最多不超过100000个。IP段包含关系可能有多层，但不超过100层。

第二行为查询的IP列表，多个IP采用英文逗号 ',' 分隔，最多不超过10000条。

输出描述

最佳匹配的城市名列表，采用英文逗号 ',' 分隔，城市列表长度应该跟查询的IP列表长度一致。

备注

1. 无论是否查到匹配正常都要输出分隔符。举例：假如输入IP列表为IPa,IPb，两个IP均未有匹配城市，此时输出为","，即只有一个逗号分隔符，两个城市均为空；
2. 可以假定用例中的所有输入均合法，IP地址均为合法的ipv4地址，满足 (1~255).(0~255).(0~255)​​​​​​​.(0~255​​​​​​​) 的格式，且可以假定用例中不会出现组播和广播地址；

用例

题目解析

本题主要难点在于判断一个IP地址是否属于一个IP段范围。

我的解决思路是，将IP地址转为整型数值，因为IP地址本质上是4*8位二进制数，所以每一个IP地址其实都能对应到一个整型数值。

而IP地址转为整型数值后，即可通过数值大小关系，判断某个IP地址是否属于某段IP范围。

之后就是，遍历待查询的IP地址，去和每一个IP段范围匹配，如果可以匹配上，且对应IP段范围更小，则对应IP段的城市就是当前待查询IP的最佳匹配城市。

import Foundation

struct City {
    var name = ""
    var ips: [Int64] = []
    var ipLen = Int64.max
}

func ODTest_2_17() {
    print("输入描述\r\n输入共2行。")
    print("第一行为城市的IP段列表，多个IP段采用英文分号 ';' 分隔，IP段列表最大不超过500000。\r\n城市名称只包含英文字母、数字和下划线。最多不超过100000个。IP段包含关系可能有多层，但不超过100层。")
    let cities = (readLine() ?? "").split(separator: ";").map { String($0) }
    var list: [City] = []
    cities.forEach { city in
        let item = city.split(separator: "=").map { String($0) }
        if item.count == 2 {
            // 将IP地址转为整型
            let ips = item[1].split(separator: ",").map { ip2dec(String($0)) }.sorted(by: <)
            let ipLen = ips[1] - ips[0]
            let model = City(name: item[0], ips: ips, ipLen: ipLen)
            list.append(model)
        }
    }
    print("第二行为查询的IP列表，多个IP采用英文逗号 ',' 分隔，最多不超过10000条。")
    let ips = (readLine() ?? "").split(separator: ",").map { ip2dec(String($0)) }

    var cityNames: [String] = []
    ips.forEach { ip in
        // 如果带查询的IP地址 在某城市的IP段范围内，且该城市的IP段长度更小，则该城市为待查询IP的最佳匹配城市
        guard let item = list.filter({ $0.ips[0] <= ip && $0.ips[1] >= ip }).sorted(by: { $0.ipLen < $1.ipLen }).first else {
            cityNames.append("无")
            return
        }
        cityNames.append(item.name)
    }
    print("最佳匹配的城市名列表，采用英文逗号 ',' 分隔，城市列表长度应该跟查询的IP列表长度一致。")
    print("\(cityNames.joined(separator: ","))")
}

// IP地址转整型
func ip2dec(_ ip: String) -> Int64 {
    var res: Int64 = 0

    let blocks = ip.split(separator: ".").map { Int64(String($0)) ?? 0 }

    for block in blocks {
        res = block | (res << 8)
    }

    return res
}