一、题目

题目描述：

某业务需要根据终端的IP地址获取该终端归属的城市，可以根据公开的IP地址池信息查询归属城市地址池格式如下:
城市名=起始IP, 结束IP
起始和结束地址按照英文逗号分隔，多个地址段采用英文分号分隔。比如:
City1=1.1.1.1,1.1.1.2;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段，比如例子中
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列表长度一致。

备注
无论是否查到匹配正常都要输出分隔符。举例：假如输入IP列表为IPa,IPb，两个IP均未有匹配城市，此时输出为","，即只有一个逗号分隔符，两个城市均为空；
可以假定用例中的所有输入均合法，IP地址均为合法的ipv4地址，满足(1/255),(0/255)(0/255,0/255)的格式，且可以假定用例中不会出现组播和广播地址，

示例1：
输入：
City1=1.1.1.1,1.1.1.2;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
3.4.4.4,5.5.5.5

输出：
City2,City3

二、核心解题思路💡

1. IP地址数字化 (IP to Integer)

字符串形式的IP（如 192.168.1.1）无法直接进行大小比较或计算长度。

• 转换公式：将IPv4看作一个32位整数。

IPint=octet1×2563+octet2×2562+octet3×2561+octet4×2560

• 优势：
  • 比较大小：直接整数比较。
  • 计算长度： Length=Endint−StartintLength=Endint​−Startint​ 。
  • 判断包含： Startint≤Queryint≤EndintStartint​≤Queryint​≤Endint​ 。

2. 数据结构设计

我们需要存储所有IP段信息以便查询。

• 结构体/对象：Segment { CityName, StartIP, EndIP, Length }。
• 存储：将所有解析后的段存入一个列表 List<Segment>。
  • *注：虽然数据量达50万，但对于1万次查询， O(N×M) 的暴力扫描在现代计算机上约为 5×109 次操作，可能在Java中稍慢（约1-2秒），在Go中较快。为了保险起见，或者如果时间限制严格（如<1s），可以考虑排序+二分查找优化，但考虑到“最小长度”可能需要遍历所有覆盖区间，线性扫描是最稳妥且逻辑最简单的做法（50万 * 1万 = 50亿，在C++/Go中通常能过，Java需开启JIT优化）。
  • 优化策略：实际上，题目中“不超过100层嵌套”暗示了重叠不会无限复杂。对于机考场景，直接遍历所有段寻找最优解通常是可接受的，因为逻辑简单不易出错。若需极致优化，可先按 StartIP 排序，利用二分查找缩小候选范围，再在候选集中找最小长度。
  • 本解法策略：采用全量遍历对比。因为 500,000×10,000 在最坏情况下确实较大，但实际测试用例通常不会达到极值，且很多IP段不重叠，可快速剪枝。若担心超时，可在解析后按 StartIP 排序，查询时只遍历 StartIP <= QueryIP 的段，一旦 StartIP > QueryIP 即可停止（前提是排序）。我们将采用排序优化版，确保高效。

3. 匹配算法流程

对每一个查询IP q：

1. 将 q 转为整数 qInt。
2. 初始化 bestCity = "", minLen = Infinity。
3. 遍历所有IP段 seg：
   • 剪枝优化：如果 seg.Start > qInt，由于已排序，后续段起点都更大，不可能包含 qInt，直接 break。
   • 包含判断：若 seg.Start <= qInt <= seg.End：
     • 计算当前长度 len = seg.End - seg.Start。
     • 贪心更新：若 len < minLen，则更新 minLen = len, bestCity = seg.City。
     • （若 len == minLen，题目未说明优先级，通常保留第一个或任意一个即可，本题逻辑隐含唯一最小或任意均可）。
4. 将 bestCity 加入结果列表。

---

三、Java 实现 (面向对象 + 流式处理)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    // 定义IP段结构
    static class IpSegment implements Comparable<IpSegment> {
        String city;
        long start;
        long end;
        long length;

        public IpSegment(String city, long start, long end) {
            this.city = city;
            this.start = start;
            this.end = end;
            this.length = end - start;
        }

        // 按起始IP排序，用于查询时的剪枝优化
        @Override
        public int compareTo(IpSegment o) {
            return Long.compare(this.start, o.start);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 读取第一行：IP段定义
        String line1 = br.readLine();
        if (line1 == null || line1.isEmpty()) return;
        
        List<IpSegment> segments = new ArrayList<>();
        String[] segmentStrs = line1.split(";");
        
        for (String segStr : segmentStrs) {
            // 格式：City=Start,End
            int eqIndex = segStr.indexOf('=');
            String city = segStr.substring(0, eqIndex);
            String ips = segStr.substring(eqIndex + 1);
            String[] ipRange = ips.split(",");
            
            long startIp = ipToLong(ipRange[0].trim());
            long endIp = ipToLong(ipRange[1].trim());
            
            segments.add(new IpSegment(city, startIp, endIp));
        }
        
        // 排序优化：按起始IP升序
        Collections.sort(segments);

        // 读取第二行：查询IP列表
        String line2 = br.readLine();
        if (line2 == null || line2.isEmpty()) {
            System.out.println("");
            return;
        }
        
        String[] queryIps = line2.split(",");
        List<String> results = new ArrayList<>();

        // 处理每个查询
        for (String qIpStr : queryIps) {
            long qIp = ipToLong(qIpStr.trim());
            String bestCity = "";
            long minLen = Long.MAX_VALUE;

            // 遍历查找
            for (IpSegment seg : segments) {
                // 剪枝：如果当前段的起点已经大于查询IP，后续段起点更大，不可能包含
                if (seg.start > qIp) {
                    break;
                }
                
                // 判断是否包含
                if (qIp >= seg.start && qIp <= seg.end) {
                    if (seg.length < minLen) {
                        minLen = seg.length;
                        bestCity = seg.city;
                    }
                }
            }
            results.add(bestCity);
        }

        // 输出结果，用逗号连接
        System.out.println(String.join(",", results));
    }

    // IP字符串转长整型
    private static long ipToLong(String ip) {
        String[] parts = ip.split("\\.");
        long res = 0;
        for (String part : parts) {
            res = res * 256 + Integer.parseInt(part);
        }
        return res;
    }
}

Java 代码亮点

1. Comparable 接口：对IP段进行预排序，使得查询时可以利用 break 提前终止循环，大幅减少无效比较。
2. long 类型：IP转换使用 long 防止溢出（虽然IPv4 int 够用，但无符号处理在Java中较麻烦，long 更安全直观）。
3. String.join：优雅地处理输出格式，自动处理空字符串占位。

---

四、Go (Golang) 实现 (高性能 + 简洁)🚀

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

// IpSegment 定义IP段结构
type IpSegment struct {
	City   string
	Start  uint32
	End    uint32
	Length uint32
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	
	// 读取第一行
	if !scanner.Scan() {
		return
	}
	line1 := scanner.Text()
	
	var segments []IpSegment
	parts := strings.Split(line1, ";")
	
	for _, p := range parts {
		if p == "" {
			continue
		}
		eqIdx := strings.Index(p, "=")
		city := p[:eqIdx]
		ipRange := strings.Split(p[eqIdx+1:], ",")
		
		startIp := ipToUint32(strings.TrimSpace(ipRange[0]))
		endIp := ipToUint32(strings.TrimSpace(ipRange[1]))
		
		segments = append(segments, IpSegment{
			City:   city,
			Start:  startIp,
			End:    endIp,
			Length: endIp - startIp,
		})
	}
	
	// 排序：按起始IP升序
	sort.Slice(segments, func(i, j int) bool {
		return segments[i].Start < segments[j].Start
	})
	
	// 读取第二行
	if !scanner.Scan() {
		fmt.Println("")
		return
	}
	line2 := scanner.Text()
	
	queryIps := strings.Split(line2, ",")
	results := make([]string, 0, len(queryIps))
	
	for _, qStr := range queryIps {
		qIp := ipToUint32(strings.TrimSpace(qStr))
		bestCity := ""
		minLen := uint32(1<<32 - 1) // Max uint32
		
		for _, seg := range segments {
			// 剪枝优化
			if seg.Start > qIp {
				break
			}
			
			// 包含判断
			if qIp >= seg.Start && qIp <= seg.End {
				if seg.Length < minLen {
					minLen = seg.Length
					bestCity = seg.City
				}
			}
		}
		results = append(results, bestCity)
	}
	
	fmt.Println(strings.Join(results, ","))
}

// ipToUint32 将IP字符串转换为uint32
func ipToUint32(ip string) uint32 {
	parts := strings.Split(ip, ".")
	var res uint32 = 0
	for _, part := range parts {
		val, _ := strconv.Atoi(part)
		res = (res << 8) + uint32(val)
	}
	return res
}

Go 代码亮点

1. uint32 类型：完美契合IPv4的32位特性，内存占用更小，运算速度极快。
2. 位运算转换：(res << 8) + val 比乘法运算略快，体现底层优化。
3. sort.Slice：匿名函数排序，语法简洁灵活。
4. 性能优势：Go 的协程和编译型特性使其在处理 50万+ 数据遍历时，通常比 Java 启动更快，内存更省，非常适合此类IO密集兼计算型的机考题。

---

五、关键细节与避坑指南⚠️

1. 空匹配的处理

• 题目要求：无论是否匹配，都要输出分隔符。
• 实现：初始化 bestCity 为空字符串 ""。如果遍历完没找到，结果列表中就是空字符串。使用 join(",", list) 时，空元素会自动变成两个连续的逗号（如 CityA,,CityB），完全符合题目要求。

2. IP转换的陷阱

• 不要直接用字符串比较IP！"10.0.0.1" 在字典序上小于 "9.0.0.1"，但在数值上远大于它。必须转为整数。
• Java中 Integer.parseUnsignedInt 或直接累加均可，推荐用 long 避免符号位困扰。

3. “最小长度”的定义

• 长度 = EndIP - StartIP。
• 题目中的“包含关系”是解题关键。如果有三个区间都包含目标IP，必须选出跨度最小的那个。这不能通过简单的二分查找直接得到结果（二分只能找到位置），必须在候选集中比较长度。

4. 性能优化必要性

• 如果不排序直接暴力遍历：500,000×10,000=5×109 次操作。在C++/Go中可能勉强卡在2-3秒，在Java中极易超时（TLE）。
• 排序后：对于每个查询，一旦 StartIP > TargetIP 就停止。平均情况下，只需要遍历一小部分数据，效率提升巨大。

---

六、复杂度分析📊

假设 IP段数量为 N (50万)，查询数量为 M (1万)。

• 时间复杂度：
  • 排序： O(Nlog⁡N) 。
  • 查询：最坏情况 O(M×N) （所有段都重叠且起点很小），但平均情况远优于 O(M×N) ，接近 O(M×K) ，其中 K 是平均重叠层数（题目提示不超过100层，所以 K 很小）。
  • 综合：在数据分布均匀的情况下，效率极高。
• 空间复杂度：
  • O(N) 存储所有IP段对象。

---

七、总结

这道题是典型的区间查询问题。

• 核心转化：IP →→ Integer。
• 核心策略：排序 + 剪枝遍历 + 贪心选优（最小长度）。
• 语言选择：
  • Java：生态好，类库丰富，适合构建复杂对象模型。
  • Go：启动快，内存低，原生支持高并发和字符串处理，是刷算法题的利器。

掌握这种“预处理排序 + 线性扫描剪枝”的思路，可以解决绝大多数区间覆盖、日程安排、资源分配类问题。祝大家机考顺利，Offer拿到手软！