当前位置：首页 > news >正文

华为OD机试 - 根据IP查找城市（Java 2024 E卷 100分）

news 来源：原创 2024/9/20 7:53:23

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

地址池格式如下：

城市名=起始 IP,结束 IP

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

City1=1.1.1.1,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段，例如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，城市名称只包含英文字母Q，数字和下划线，段长不超过100000个。IP段包含关系的层数，但不超过100层。

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

三、输出描述

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

备注

无论是否有更佳匹配都需要输出结果，并用英文逗号分隔；假设输入IP列表为IPa,IPb,两个IP均未匹配城市，此时输出为“，”即只有一个逗号。

以列表形式输出，即按输入顺序输出城市名，IP地址符合合法的IPv4地址，满足（1255,0(255),0(255),0(255)）的格式，且可以假定有同/异网地址不会出现“播址”和“播址地址”；

四、测试用例

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

2、输出

City1,City2,City3

3、说明

City1有2个IP段，City3的IP段包含City2的IP段；
1.1.1.15仅匹配City1=1.1.1.11,1.1.1.16，所以City1就是最佳匹配；2.2.2.3仅匹配City3=2.2.2.2,6.6.6.6，所以City3是最佳匹配；3.3.3.5同时匹配为City2=3.3.3.3,4.4.4.4和City3=2.2.2.2,6.6.6.6，但是City2=3.3.3.3,4.4.4.4的IP段范围更小，所以City3为最佳匹配；

五、解题思路

首先，我们需要解析输入的城市IP段列表，将其存储在一个Map结构中，其中键为城市名称，值为该城市的所有IP段范围（Range对象的列表）。每个Range对象包含起始IP和结束IP，均转换为长整数（long）表示。
将IPv4地址从“点分十进制”格式转换为长整数，以便于比较和判断一个IP地址是否属于某个IP段。
对于每个需要查询的IP地址，遍历所有城市的IP段，找到能够包含该IP的且范围长度最长的IP段对应的城市。若找到多个符合条件的IP段，则选择其中范围最长的作为最佳匹配。
最终，将每个查询IP地址的最佳匹配城市按输入顺序输出。如果某个IP地址无法匹配到任何城市，则输出空字符串。

六、Java算法源码

public class OdTest01 {static class Range {long start;long end;public Range(long start, long end) {this.start = start;this.end = end;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取城市的IP段列表String cityIpList = scanner.nextLine().trim();// 读取查询的IP列表String ipList = scanner.nextLine().trim();// 解析城市IP段列表Map<String, List<Range>> cityIpMap = parseCityIpList(cityIpList);// 解析查询IP列表List<String> queryIps = Arrays.asList(ipList.split(","));// 查找最佳匹配城市List<String> result = findBestMatchingCities(cityIpMap, queryIps);// 输出结果System.out.println(String.join(",", result));}// 解析城市IP段列表private static Map<String, List<Range>> parseCityIpList(String cityIpList) {Map<String, List<Range>> cityIpMap = new HashMap<>();String[] cities = cityIpList.split(";");for (String city : cities) {String[] parts = city.split("=");String cityName = parts[0];String[] ipRanges = parts[1].split(",");List<Range> ranges = new ArrayList<>();for (int i = 0; i < ipRanges.length; i += 2) {long start = ipToLong(ipRanges[i]);long end = ipToLong(ipRanges[i + 1]);ranges.add(new Range(start, end));}cityIpMap.putIfAbsent(cityName, new ArrayList<>());cityIpMap.get(cityName).addAll(ranges);}return cityIpMap;}// 查找最佳匹配城市private static List<String> findBestMatchingCities(Map<String, List<Range>> cityIpMap, List<String> queryIps) {List<String> result = new ArrayList<>();for (String ip : queryIps) {long ipLong = ipToLong(ip);String bestMatchCity = "";long maxRangeLength = -1;for (Map.Entry<String, List<Range>> entry : cityIpMap.entrySet()) {String cityName = entry.getKey();for (Range range : entry.getValue()) {if (range.start <= ipLong && ipLong <= range.end) {long rangeLength = range.end - range.start;if (rangeLength > maxRangeLength) {bestMatchCity = cityName;maxRangeLength = rangeLength;}}}}result.add(bestMatchCity);}return result;}// 将IP地址转换为长整数private static long ipToLong(String ip) {String[] parts = ip.split("\\.");long result = 0;for (String part : parts) {result = result * 256 + Integer.parseInt(part);}return result;}
}