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

OD统一考试

题解： Java / Python / C++

题目描述

某业务需要根据终端的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

输入：
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
1.1.1.15,3.3.3.5,2.2.2.3

输出：
City1,City2,City3

题解

这道题目涉及到对IP地址范围的处理和匹配，可以通过以下步骤解决：

1. 将输入的IP范围按照起始IP排序，以便后续的查找操作。
2. 对于每个待查询的IP，从排序后的IP范围列表中找到满足条件的最佳匹配，即包含待查询IP且长度最小的IP段。
3. 输出最佳匹配的城市列表。

在此题目中为了方便的对 ip 进行处理，代码中将字符串的ip转成了等价的正整数。

具体实现中，可以使用类来表示IP范围，然后对IP范围列表进行排序。

在查询时，遍历排序后的IP范围列表，找到最佳匹配的城市。

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class IpRange {
   
    public String city;
    public long startIp;
    public long endIp;

    public IpRange(String city, long startIp, long endIp) {
   
        this.city = city;
        this.startIp = startIp;
        this.endIp = endIp;
    }
}

/**
 * @author code5bug
 */
public class Main {
   
    public static void main(String[] args) {
   
        Scanner scanner = new Scanner(System.in);

        List<IpRange> ipRanges = new ArrayList<>();

        // 读取 IP 范围并进行排序
        String[] rangeInputs = scanner.nextLine().split(";");
        for (String rangeInput : rangeInputs) {
   
            String[] parts = rangeInput.split("=");
            String city = parts[0];
            String[] ipRange = parts[1].split(",");
            long startIp = ipToLong(ipRange[0]), endIp = ipToLong(ipRange[1]);
            ipRanges.add(new IpRange(city, startIp, endIp));
        }
        ipRanges.sort((x, y) -> (int) (x.startIp - y.startIp));

        // 查询并输出结果
        String[] ipInputs = scanner.nextLine().split(",");
        List<String> results = new ArrayList<>();
        for (String ipInput : ipInputs) {
   
            results.add(findCity(ipRanges, ipToLong(ipInput)));
        }
        System.out.println(String.join(",", results));
    }

    /**
     * IP 字符串转成10进制的整数
     *
     * @param ip
     * @return
     */
    private static long ipToLong(String ip) {
   
        String[] ipParts = ip.split("\\.");
        return (0L | Integer.parseInt(ipParts[0]) << 24) |
                (Integer.parseInt(ipParts[1]) << 16) |
                (Integer.parseInt(ipParts[2]) << 8) |
                Integer.parseInt(ipParts[3]);
    }

    /**
     * 根据IP 查询归属城市, 返回最佳匹配城市名称（既满足条件且长度最小的IP段）
     *
     * @param ipRanges
     * @param ip
     * @return
     */
    private static String findCity(List<IpRange> ipRanges, long ip) {
   
        String city = "unknown";
        long cityLength = Long.MAX_VALUE;
        for (IpRange ipRange : ipRanges) {
   
            if (ipRange.startIp > ip) break;

            long length = ipRange.endIp - ipRange.startIp + 1;
            if (ipRange.startIp <= ip && ip <= ipRange.endIp && length < cityLength) {
   
                cityLength = length;
                city = ipRange.city;
            }
        }

        return city;
    }
}

Python

from math import inf
import string


def ip_to_int(ip: string):
    """ IP 字符串转成10进制的整数 """
    ip_nums = list(map(int, ip.split('.')))
    return ip_nums[0] << 24 | ip_nums[1] << 16 | ip_nums[2] << 8 | ip_nums[3]


class IpRange:
    """ IP范围 """

    def __init__(self, city, start_ip, end_ip):
        self.start_ip = ip_to_int(start_ip)
        self.end_ip = ip_to_int(end_ip)
        self.city = city


ip_ranges = []
for sip in input().split(";"):
    city, iprange = sip.split("=")
    start_ip, end_ip = iprange.split(",")
    ip_ranges.append(IpRange(city, start_ip, end_ip))

# 根据 x.start_ip 升序 进行排序
ip_ranges.sort(key=lambda x: x.start_ip)


def find_city(ip):
    """ 根据IP 查询归属城市 """
    global ip_ranges

    # 返回最佳匹配城市名称（既满足条件且长度最小的IP段）
    city, city_length = "unknown", inf
    for it in ip_ranges:
        if it.start_ip > ip:
            break

        lenght = it.end_ip - it.start_ip + 1
        if it.start_ip <= ip <= it.end_ip and lenght < city_length:
            city_length = lenght
            city = it.city

    return city


rs = []
for sip in input().split(","):
    rs.append(find_city(ip_to_int(sip)))
print(",".join(rs))

C++

#include <bits/stdc++.h>

using namespace std;

class IpRange {
   
public:
    string city;
    long startIp;
    long endIp;

    IpRange(string city, long startIp, long endIp)
        : city(move(city)), startIp(startIp), endIp(endIp) {
   }
};

// IP 字符串转成10进制的整数
long ipToLong(const string& ip) {
   
    istringstream iss(ip);
    string token;
    long result = 0;
    while (getline(iss, token, '.')) {
   
        result = (result << 8) | stoi(token);
    }
    return result;
}

// 根据IP 查询归属城市, 返回最佳匹配城市名称（既满足条件且长度最小的IP段）
string findCity(const vector<IpRange>& ipRanges, long ip) {
   
    string city = "unknown";
    long cityLength = LONG_MAX;

    for (const auto& ipRange : ipRanges) {
   
        if (ipRange.startIp > ip) break;

        long length = ipRange.endIp - ipRange.startIp + 1;
        if (ipRange.startIp <= ip && ip <= ipRange.endIp && length < cityLength) {
   
            cityLength = length;
            city = ipRange.city;
        }
    }

    return city;
}


vector<string> split(const string &str, const char &delim) {
   
    vector<string> res;
    stringstream ss(str);
    string tmp;
    while (getline(ss, tmp, delim)) {
   
        if (!tmp.empty()) res.push_back(std::move(tmp));
    }
    return res;
}

int main() {
   
    vector<IpRange> ipRanges;

    // 读取 IP 范围并进行排序
    string inputLine;
    getline(cin, inputLine);

    vector<string> parts = split(inputLine, ';');
    for(string& part : parts) {
   
        vector<string> arr = split(part, '=');
        string city = arr[0];

        vector<string> ips = split(arr[1], ',');
        ipRanges.emplace_back(city, ipToLong(ips[0]), ipToLong(ips[1]));
    }

    sort(ipRanges.begin(), ipRanges.end(), [](const auto& x, const auto& y) {
   
        return x.startIp < y.startIp;
    });

    // 查询并输出结果
    getline(cin, inputLine);

    vector<string> results;
    for(auto& ip : split(inputLine,',')) {
   
        results.push_back(findCity(ipRanges, ipToLong(ip)));
    }


    for(int i=0; i<results.size(); i++) {
   
        if(i + 1 == results.size()) {
   
            cout << results[i] << endl;
        } else {
   
            cout << results[i] << ",";
        }
    }

    return 0;
}

‍❤️‍华为OD机试面试交流群（每日真题分享）： 加V时备注“华为od加群”

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏