某业务需要根据终端的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列表长度一致。
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
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* Created with IntelliJ IDEA.
*
* @Author: Amos
* @E-mail: amos@amoscloud.com
* @Date: 2023/12/9
* @Time: 11:01
* @Description:
*/
public class Main01 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String ipRanges = scanner.nextLine();
String ips = scanner.nextLine();
System.out.println(findCities(ipRanges, ips));
scanner.close();
}
private static long ipToInt(String ip) {
String[] parts = ip.split("\\.");
return (long) Integer.parseInt(parts[0]) << 24
| Integer.parseInt(parts[1]) << 16
| Integer.parseInt(parts[2]) << 8
| Integer.parseInt(parts[3]);
}
private static Map<Long, String> parseIPRanges(String ipRangesStr) {
Map<Long, String> ranges = new HashMap<>();
for (String part : ipRangesStr.split(";")) {
String[] cityAndRange = part.split("=");
String city = cityAndRange[0];
String[] startEnd = cityAndRange[1].split(",");
long startIp = ipToInt(startEnd[0]);
long endIp = ipToInt(startEnd[1]);
ranges.put((startIp << 32) | endIp, city);
}
return ranges;
}
private static String findCity(String ip, Map<Long, String> ranges) {
long ipInt = ipToInt(ip);
String bestMatch = null;
long bestRange = Long.MAX_VALUE;
for (Map.Entry<Long, String> entry : ranges.entrySet()) {
long range = entry.getKey();
long startIp = range >> 32;
long endIp = range & 0xFFFFFFFFL;
if (startIp <= ipInt && ipInt <= endIp) {
long currentRange = endIp - startIp;
if (bestMatch == null || currentRange < bestRange) {
bestMatch = entry.getValue();
bestRange = currentRange;
}
}
}
return bestMatch;
}
public static String findCities(String ipRangesStr, String ipsStr) {
Map<Long, String> ranges = parseIPRanges(ipRangesStr);
String[] ips = ipsStr.split(",");
StringBuilder result = new StringBuilder();
for (String ip : ips) {
if (result.length() > 0) result.append(",");
result.append(findCity(ip, ranges));
}
return result.toString();
}
}