IPv4地址区间合并方案

问题定义

输入包含多个IPv4地址表示项，支持单个IP地址或IP地址段形式。需将输入数据进行去重合并，输出连续的地址区间。

输入示例

{"192.168.0.1", "192.168.0.12-192.168.0.15", "192.168.0.2", 
 "192.168.0.7-192.168.0.9", "192.168.0.11", "192.168.0.3-192.168.0.5",
 "192.168.0.16", "192.168.0.100"}

输出示例

{"192.168.0.1-192.168.0.5", "192.168.0.7-192.168.0.9", 
 "192.168.0.11-192.168.0.16", "192.168.0.100"}

该问题基于经典区间合并算法，但需处理IP地址的特殊性。由于Java的int类型无法完整表示32位IP地址，需使用long类型进行存储和比较。转换过程涉及字符串与二进制位操作的双向映射。

地址编码转换

将IP地址转换为long类型的核心思想是：将四个8位字段通过位移和按位或操作组合成32位二进制数。以下为三种实现方式：

位移优先方案

public static long parseIpToLong(String ip) {
    String[] segments = ip.split("\\.");
    long value = 0;
    
    for (int i = 0; i < 4; i++) {
        value |= Long.parseLong(segments[i]) << (24 - 8 * i);
    }
    
    return value;
}

循环优化方案

public static long parseIpToLong(String ip) {
    String[] segments = ip.split("\\.");
    long value = 0;
    
    for (int i = 0; i < 4; i++) {
        value |= Long.parseLong(segments[i]) << (24 - 8 * i);
    }
    
    return value;
}

位掩码方案

public static String formatIpAddress(long ip) {
    StringBuilder sb = new StringBuilder();
    
    sb.append((ip >> 24) & 0xFF).append(".");
    sb.append((ip >> 16) & 0xFF).append(".");
    sb.append((ip >> 8) & 0xFF).append(".");
    sb.append(ip & 0xFF);
    
    return sb.toString();
}

区间合并算法

实现核心逻辑如下：

1. 将地址转换为数值数组
2. 按起始地址排序
3. 遍历数组进行合并

public static long[][] combineIntervals(long[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingLong(a -> a[0]));
    
    List<long[]> result = new ArrayList<>();
    long start = intervals[0][0], end = intervals[0][1];
    
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= end + 1) {
            end = Math.max(end, intervals[i][1]);
        } else {
            result.add(new long[]{start, end});
            start = intervals[i][0];
            end = intervals[i][1];
        }
    }
    result.add(new long[]{start, end});
    
    return result.toArray(new long[result.size()][2]);
}

完整实现

import java.util.*;

public class AddressMerger {
    public static void main(String[] args) {
        String[] entries = {"192.168.0.1", "192.168.0.12-192.168.0.15", 
                           "192.168.0.2", "192.168.0.7-192.168.0.9", 
                           "192.168.0.11", "192.168.0.3-192.168.0.5", 
                           "192.168.0.16", "192.168.0.100"};
        
        List<String> output = processAddresses(entries);
        
        for (String addr : output) {
            System.out.println(addr);
        }
    }

    public static List<String> processAddresses(String[] input) {
        List<String> result = new ArrayList<>();
        long[][] intervals = new long[input.length][2];
        
        for (int i = 0; i < input.length; i++) {
            String entry = input[i];
            int dashIndex = entry.indexOf('-');
            
            if (dashIndex > 0) {
                intervals[i][0] = parseIpToLong(entry.substring(0, dashIndex));
                intervals[i][1] = parseIpToLong(entry.substring(dashIndex + 1));
            } else {
                intervals[i][0] = parseIpToLong(entry);
                intervals[i][1] = intervals[i][0];
            }
        }
        
        intervals = combineIntervals(intervals);
        
        for (long[] interval : intervals) {
            if (interval[0] == interval[1]) {
                result.add(formatIpAddress(interval[0]));
            } else {
                result.add(formatIpAddress(interval[0]) + "-" + formatIpAddress(interval[1]));
            }
        }
        
        return result;
    }
}