网站开发的一般流程,新闻写作网站,上海牛巨微seo,大诚设计网站建设OD统一考试 题解#xff1a; Java / Python / C 题目描述
某业务需要根据终端的IP地址获取该终端归属的城市#xff0c;可以根据公开的IP地址池信息查询归属城市。
地址池格式如下#xff1a;
城市名起始IP#xff0c;结束IP
起始和结束地址按照英文逗号分隔#xff0… OD统一考试 题解 Java / Python / C 题目描述
某业务需要根据终端的IP地址获取该终端归属的城市可以根据公开的IP地址池信息查询归属城市。
地址池格式如下
城市名起始IP结束IP
起始和结束地址按照英文逗号分隔多个地址段采用英文分号分隔。 比如 City11.1.1.1,1.1.1.2;City11.1.1.11,1.1.1.16;City23.3.3.3,4.4.4.4;City32.2.2.2,6.6.6.6。 一个城市可以有多个IP段比如City1有2个IP段。 城市间也可能存在包含关系比如City3的IP段范围包括City2的IP段范围。 现在要根据输入的IP列表返回最佳匹配的城市列表。
注最佳匹配即可包含待查询IP且长度最小的IP段比如例子中的 3.4.4.4的最佳匹配是City23.3.3.3,4.4.4.4; 5.5.5.5的最佳匹配是City32.2.2.2,6.6.6.6。
输入描述
输入共2行。
第一行为城市的IP段列表多个IP段采用英文分号’;分隔IP段列表最大不超过500000。
城市名称只包含英文字母、数字和下划线最多不超过100000个。
IP段包含关系可能有多层但不超过100层。
第二行为查询的IP列表多个IP采用英文逗号’,分隔最多不超过10000条。
输出描述
最佳匹配的城市名列表采用英文逗号,分隔城市列表长度应该跟查询的IP列表长度一致。
示例1
输入
City11.1.1.1,1.1.1.2;City11.1.1.11,1.1.1.16;City23.3.3.3,4.4.4.4;City32.2.2.2,6.6.6.6
1.1.1.15,3.3.3.5,2.2.2.3输出
City1,City2,City3题解 这道题目涉及到对IP地址范围的处理和匹配可以通过以下步骤解决 将输入的IP范围按照起始IP排序以便后续的查找操作。对于每个待查询的IP从排序后的IP范围列表中找到满足条件的最佳匹配即包含待查询IP且长度最小的IP段。输出最佳匹配的城市列表。 在此题目中为了方便的对 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);ListIpRange 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(,);ListString 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(ListIpRange 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 stringdef 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 cityip_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(keylambda x: x.start_ip)def find_city(ip): 根据IP 查询归属城市 global ip_ranges# 返回最佳匹配城市名称既满足条件且长度最小的IP段city, city_length unknown, inffor it in ip_ranges:if it.start_ip ip:breaklenght it.end_ip - it.start_ip 1if it.start_ip ip it.end_ip and lenght city_length:city_length lenghtcity it.cityreturn cityrs []
for sip in input().split(,):rs.append(find_city(ip_to_int(sip)))
print(,.join(rs))
C
#include bits/stdc.husing 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 vectorIpRange 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;
}vectorstring split(const string str, const char delim) {vectorstring res;stringstream ss(str);string tmp;while (getline(ss, tmp, delim)) {if (!tmp.empty()) res.push_back(std::move(tmp));}return res;
}int main() {vectorIpRange ipRanges;// 读取 IP 范围并进行排序string inputLine;getline(cin, inputLine);vectorstring parts split(inputLine, ;);for(string part : parts) {vectorstring arr split(part, );string city arr[0];vectorstring 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);vectorstring results;for(auto ip : split(inputLine,,)) {results.push_back(findCity(ipRanges, ipToLong(ip)));}for(int i0; iresults.size(); i) {if(i 1 results.size()) {cout results[i] endl;} else {cout results[i] ,;}}return 0;
} ❤️华为OD机试面试交流群每日真题分享 加V时备注“华为od加群” 整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
