(C卷,200分)- 根据IP查找城市（Java & JS & 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. 无论是否查到匹配正常都要输出分隔符。举例：假如输入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的最佳匹配城市。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 输入输出处理
void (async function () {
  // 城市IP列表
  const cities = (await readline()).split(";");
  // 带查询的IP列表
  const queryIps = (await readline()).split(",");

  // IP地址转整型
  function ip2dec(ip) {
    let res = 0;

    const blocks = ip.split(".");
    for (let block of blocks) {
      res = parseInt(block) | (res << 8);
    }

    return res;
  }

  class Range {
    constructor(city, startIpStr, endIpStr) {
      this.city = city;
      // 将IP地址转为整型
      this.startIpDec = ip2dec(startIpStr);
      this.endIpDec = ip2dec(endIpStr);
      this.ipLen = this.endIpDec - this.startIpDec + 1;
    }
  }

  const ranges = [];

  for (let s of cities) {
    const [city, startIpStr, endIpStr] = s.split(/[=,]/);
    ranges.push(new Range(city, startIpStr, endIpStr));
  }

  const ans = [];

  // 遍历待查询的IP地址
  for (let ip of queryIps) {
    const ipDec = ip2dec(ip);

    // 记录该目标IP地址的最佳匹配城市
    let city = "";
    // 记录最佳匹配城市IP段的长度
    let minLen = Infinity;

    // 将带查询IP与城市IP段列表逐一匹配
    for (let range of ranges) {
      // 如果带查询的IP地址 在某城市的IP段范围内，且该城市的IP段长度更小，则该城市为待查询IP的最佳匹配城市
      if (
        ipDec >= range.startIpDec &&
        ipDec <= range.endIpDec &&
        minLen > range.ipLen
      ) {
        city = range.city;
        minLen = range.ipLen;
      }
    }

    ans.push(city);
  }

  console.log(ans.join(","));
})();

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 city, String startIpStr, String endIpStr) {
      this.city = city;
      // 将IP地址转为整型
      this.startIpDec = ip2dec(startIpStr);
      this.endIpDec = ip2dec(endIpStr);
      this.ipLen = this.endIpDec - this.startIpDec + 1;
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    ArrayList<Range> ranges = new ArrayList<>();

    // 城市IP列表
    String[] cities = sc.nextLine().split(";");
    // 带查询的IP列表
    String[] queryIps = sc.nextLine().split(",");

    // 提取各个城市IP列表信息
    for (String city : cities) {
      String[] tmp = city.split("[=,]");
      ranges.add(new Range(tmp[0], tmp[1], tmp[2]));
    }

    StringJoiner sj = new StringJoiner(",");

    // 遍历待查询的IP地址
    for (String ip : queryIps) {
      long ipDec = ip2dec(ip);

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

      // 将带查询IP与城市IP段列表逐一匹配
      for (Range range : ranges) {
        // 如果带查询的IP地址 在某城市的IP段范围内，且该城市的IP段长度更小，则该城市为待查询IP的最佳匹配城市
        if (ipDec >= range.startIpDec && ipDec <= range.endIpDec && minLen > range.ipLen) {
          city = range.city;
          minLen = range.ipLen;
        }
      }

      sj.add(city);
    }

    System.out.println(sj);
  }

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

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

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

    return res;
  }
}

Python算法源码

import re
import sys


# IP地址转整型
def ip2dec(ipStr):
    res = 0

    blocks = ipStr.split(".")
    for block in blocks:
        res = int(block) | (res << 8)

    return res


class Range:
    def __init__(self, city, startIpStr, endIpStr):
        self.city = city
        # 将IP地址转为整型
        self.startIp = ip2dec(startIpStr)
        self.endIp = ip2dec(endIpStr)
        self.ipLen = self.endIp - self.startIp + 1


# 输入获取
cities = input().split(";")  # 城市IP列表
queryIps = input().split(",")  # 带查询的IP列表

# 核心代码
ranges = []

# 提取各个城市IP列表信息
for s in cities:
    # * 用于函数参数自动解构
    ranges.append(Range(*(re.split(r"[=,]", s))))

ans = []

# 遍历待查询的IP地址
for ip in queryIps:
    ipDec = ip2dec(ip)

    # 记录该目标IP地址的最佳匹配城市
    best_city = ""
    # 记录最佳匹配城市IP段的长度
    minLen = sys.maxsize

    # 将带查询IP与城市IP段列表逐一匹配
    for ran in ranges:
        # 如果带查询的IP地址 在某城市的IP段范围内，且该城市的IP段长度更小，则该城市为待查询IP的最佳匹配城市
        if ran.endIp >= ipDec >= ran.startIp and minLen > ran.ipLen:
            best_city = ran.city
            minLen = ran.ipLen

    ans.append(best_city)

print(",".join(ans))

C算法源码

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

#define CITY_NAME_LENGTH 100
#define CITY_LIST_LENGTH 500000
#define QUERY_LIST_LENGTH 700000

typedef struct Range {
    char city[CITY_NAME_LENGTH];
    long startIpDec;
    long endIpDec;
    long ipLen;
} Range;

// IP地址转整型
long ip2dec(char *ip) {
    long res = 0;

    int n1, n2, n3, n4;
    sscanf(ip, "%d.%d.%d.%d", &n1, &n2, &n3, &n4);

    res = n1 | (res << 8);
    res = n2 | (res << 8);
    res = n3 | (res << 8);
    res = n4 | (res << 8);

    return res;
}

Range *new_Range(char *city, char *startIpStr, char *endIpStr) {
    Range *range = (Range *) malloc(sizeof(Range));
    strcpy(range->city, city);
    range->startIpDec = ip2dec(startIpStr);
    range->endIpDec = ip2dec(endIpStr);
    range->ipLen = range->endIpDec - range->startIpDec + 1;
    return range;
}

// 第一行输入
char s1[CITY_LIST_LENGTH];

// 第二行输入
char s2[QUERY_LIST_LENGTH];


Range *ranges[CITY_LIST_LENGTH];
int ranges_size = 0;

int main() {
    gets(s1);

    char *token1 = strtok(s1, ";");
    while (token1 != NULL) {
        // 提取各个城市IP列表信息
        char city[CITY_NAME_LENGTH] = {''};
        char startIpStr[10] = {''};
        char endIpStr[10] = {''};

        sscanf(token1, "%[^=]=%[^,],%[^,]", city, startIpStr, endIpStr);
        ranges[ranges_size++] = new_Range(city, startIpStr, endIpStr);

        token1 = strtok(NULL, ";");
    }


    gets(s2);

    // 遍历待查询的IP地址
    char *token2 = strtok(s2, ",");
    while (token2 != NULL) {
        long ipDec = ip2dec(token2);

        // 记录该目标IP地址的最佳匹配城市
        char *city = "";
        // 记录最佳匹配城市IP段的长度
        long minLen = LONG_MAX;

        // 将带查询IP与城市IP段列表逐一匹配
        for (int i = 0; i < ranges_size; i++) {
            // 如果带查询的IP地址 在某城市的IP段范围内，且该城市的IP段长度更小，则该城市为待查询IP的最佳匹配城市
            if (ipDec >= ranges[i]->startIpDec && ipDec <= ranges[i]->endIpDec && minLen > ranges[i]->ipLen) {
                city = ranges[i]->city;
                minLen = ranges[i]->ipLen;
            }
        }

        printf("%s", city);

        token2 = strtok(NULL, ",");

        if(token2 != NULL) {
            printf(",");
        }
    }

    return 0;
}