返回目录

题目描述

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

Python算法源码

class Range:
    def __init__(self, city, start_ip_str, end_ip_str):
        self.city = city
        # 将IP地址转为整型
        self.start_ip_dec = self.ip_to_dec(start_ip_str)
        self.end_ip_dec = self.ip_to_dec(end_ip_str)
        self.ip_len = self.end_ip_dec - self.start_ip_dec + 1

    @staticmethod
    def ip_to_dec(ip_str):
        res = 0
        blocks = ip_str.split('.')
        for block in blocks:
            res = (int(block)) | (res << 8)
        return res


if __name__ == "__main__":
    # 城市IP列表
    cities = input().split(";")
    # 带查询的IP列表
    query_ips = input().split(",")

    ranges = []

    # 提取各个城市IP列表信息
    for city in cities:
        tmp = city.split("=")
        city_name = tmp[0]
        ip_range = tmp[1].split(",")
        ranges.append(Range(city_name, ip_range[0], ip_range[1]))

    result = []

    # 遍历待查询的IP地址
    for ip in query_ips:
        ip_dec = Range.ip_to_dec(ip)

        # 记录该目标IP地址的最佳匹配城市
        city = ""
        # 记录最佳匹配城市IP段的长度
        min_len = float('inf')

        # 将带查询IP与城市IP段列表逐一匹配
        for r in ranges:
            # 如果带查询的IP地址在某城市的IP段范围内，且该城市的IP段长度更小，则该城市为待查询IP的最佳匹配城市
            if r.start_ip_dec <= ip_dec <= r.end_ip_dec and min_len > r.ip_len:
                city = r.city
                min_len = r.ip_len

        result.append(city)

    print(",".join(result))

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Range {
    char *city;
    long start_ip_dec;
    long end_ip_dec;
    long ip_len;
};

long ip_to_dec(char *ip_str) {
    long res = 0;
    char *token;
    token = strtok(ip_str, ".");
    while (token != NULL) {
        res = (atoi(token)) | (res << 8);
        token = strtok(NULL, ".");
    }
    return res;
}

int main() {
    char input[1000];
    fgets(input, sizeof(input), stdin);

    // 城市IP列表
    char *city_token = strtok(input, ";");
    struct Range ranges[100]; // Assuming a maximum of 100 ranges
    int range_count = 0;

    while (city_token != NULL) {
        char *city_ip = strdup(city_token);
        char *city_name = strtok(city_ip, "=");
        char *ip_range = strtok(NULL, ",");
        char *start_ip = strtok(ip_range, "-");
        char *end_ip = strtok(NULL, "-");
        ranges[range_count].city = strdup(city_name);
        ranges[range_count].start_ip_dec = ip_to_dec(start_ip);
        ranges[range_count].end_ip_dec = ip_to_dec(end_ip);
        ranges[range_count].ip_len = ranges[range_count].end_ip_dec - ranges[range_count].start_ip_dec + 1;
        range_count++;
        city_token = strtok(NULL, ";");
        free(city_ip);
    }

    fgets(input, sizeof(input), stdin);
    char *ip_token = strtok(input, ",");
    while (ip_token != NULL) {
        long ip_dec = ip_to_dec(ip_token);
        char *city = "";
        long min_len = __LONG_MAX__;
        for (int i = 0; i < range_count; i++) {
            if (ip_dec >= ranges[i].start_ip_dec && ip_dec <= ranges[i].end_ip_dec && min_len > ranges[i].ip_len) {
                city = ranges[i].city;
                min_len = ranges[i].ip_len;
            }
        }
        printf("%s,", city);
        ip_token = strtok(NULL, ",");
    }

    return 0;
}

Java算法源码

import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  
  static class Range {
    String city;
    long startIpDec;
    long endIpDec;
    long ipLen;

    public Range(String cityName, String startIp, String endIp) {
      this.city = cityName;
      // 将IP地址转为整型
      this.startIpDec = convertIpToDecimal(startIp);
      this.endIpDec = convertIpToDecimal(endIp);
      this.ipLen = this.endIpDec - this.startIpDec + 1;
    }
  }
  
  static class AdditionalInfo {
    String data;
    int count;

    public AdditionalInfo(String data, int count) {
      this.data = data;
      this.count = count;
    }

    // 显示附加信息
    public void displayInfo() {
      System.out.println("附加信息: " + data + ", 数量: " + count);
    }
  }
  
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    ArrayList<Range> ranges = new ArrayList<>();
    ArrayList<AdditionalInfo> additionalInfos = new ArrayList<>();
    int counter = 0;

    // 获取城市IP列表
    String[] citiesData = scanner.nextLine().split(";");
    // 获取待查询的IP列表
    String[] queryIps = scanner.nextLine().split(",");

    // 提取各个城市IP列表信息
    while (counter < citiesData.length) {
      String[] temp = citiesData[counter].split("[=,]");
      ranges.add(new Range(temp[0], temp[1], temp[2]));
      counter++;
    }

    StringJoiner stringJoiner = new StringJoiner(",");

    counter = 0;
    // 遍历待查询的IP地址
    while (counter < queryIps.length) {
      long ipDecimal = convertIpToDecimal(queryIps[counter]);

      // 记录该目标IP地址的最佳匹配城市
      String city = "";
      // 记录最佳匹配城市IP段的长度
      long minLength = Long.MAX_VALUE;

      int innerCounter = 0;
      // 将带查询IP与城市IP段列表逐一匹配
      while (innerCounter < ranges.size()) {
        Range range = ranges.get(innerCounter);

        // 如果带查询的IP地址在某城市的IP段范围内，且该城市的IP段长度更小，则该城市为待查询IP的最佳匹配城市
        if (ipDecimal >= range.startIpDec && ipDecimal <= range.endIpDec && minLength > range.ipLen) {
          city = range.city;
          minLength = range.ipLen;
        }

        innerCounter++;
      }

      stringJoiner.add(city);
      counter++;
    }

    System.out.println(stringJoiner);

    // 使用附加信息
    AdditionalInfo additionalInfo = new AdditionalInfo("测试", 5);
    additionalInfo.displayInfo();
  }

  // IP地址转整型
  public static long convertIpToDecimal(String ip) {
    long result = 0;

    String[] blocks = ip.split("\\.");

    for (String block : blocks) {
      result = (Integer.parseInt(block)) | (result << 8);
    }

    return result;
  }
}