[Java知识库][Java] 201812-3 CIDR合并

• 从90分到100分，主要是运行超时的问题，这个我主要使用栈来优化

• 样例输入1

2
1
2

• 样例输出1

1.0.0.0/8
2.0.0.0/8

• 样例输入2

2
10/9
10.128/9

• 样例输出2

10.0.0.0/8

• 样例输入3

2
0/1
128/1

• 样例输出3

0.0.0.0/0

import java.io.*;
import java.util.*;

class Prefix implements Comparable<Prefix> {
	private int len;
	// ip对应的32位整数值，需要使用long型保存
	private long val;

	public int getLen() {
		return len;
	}

	public int compareTo(Prefix that) {
		if (this.val == that.val) {
			return this.len - that.len;
		}
		if (this.val < that.val) {
			return -1;
		}
		else if (this.val == that.val) {
			return 0;
		}
		else {
			return 1;
		}
	}

	public Prefix(Prefix a) {
		this.val = a.val;
		this.len = a.len - 1;
	}

	public Prefix(String ip, int len) {
		this.val = 0;
		this.len = len;
		// 这里的split里面是正则表达式，需要注意
		String[] arr = ip.split("\\.");
		// System.out.println(Arrays.toString(arr));
		long base = 1;
		for (int i = 3; i >= 0; i--) {
			val += base * Integer.parseInt(arr[i]);
			base *= 256;
		}
	}

	public boolean isSubsetOf(Prefix that) {
		// this的前缀长度更长
		if (this.len < that.len) {
			return false;
		}
		// 前n位bits需相等
		int n = that.len;
		long num = ((long)Math.pow(2, n) - 1) << (32 - n);
		return (this.val & num) == (that.val & num);
	}

	// 注意，这里我想不到这种方法
	public boolean match(Prefix that) {
		// a和b长度需相等
		if (this.len != that.len) {
			return false;
		}
		// 且前n位bits需相等
		int n = len - 1;
		long num = ((long)Math.pow(2, n) - 1) << (32 - n);
		if ((this.val & num) != (that.val & num)) {
			return false;
		}
		// 同时第len位bit不能相同
		long flag = (long) 1 << (32 - len);
		if ((this.val & flag) == (that.val & flag)) {
			return false;
		}
		return true;
	}

	@Override
	public String toString() {
		long base = 256 * 256 * 256;	
		long val_cp = this.val;
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < 4; i++) {
			sb.append(val_cp / base).append(".");
			val_cp -= val_cp / base * base;
			base /= 256;
		}
		sb.setCharAt(sb.length() - 1, '/');
		sb.append(this.len);
		return sb.toString();
	}
}

public class Main {

    public static void main(String[] args) throws IOException {
		// Use BufferedReader rather than RandomAccessFile; it's much faster
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

	    int n = Integer.parseInt(f.readLine());
		Prefix[] prefixes = new Prefix[n];
		for (int i = 0; i < n; i++) {
			String prefix = f.readLine();
			StringBuilder sb = new StringBuilder(); 
			int len = 0;

			// 统计点的数量来求出前缀长度和补全IP地址
			int dot_count = 0;
			for (char ch : prefix.toCharArray()) {
				if (ch == '.') dot_count++;
			}
			// 标准型：a3.a2.a1.a0/len
			// 省略后缀型：标准型基础上，只写出IP地址的高位部分位段，没有写的认为是0
			int index = prefix.indexOf('/');
			if (index != -1) {
				sb.append(prefix.substring(0, index));
	 			len = Integer.parseInt(prefix.substring(index + 1));
			}
			// 省略长度型：长度为8、16、24、32时，可以省略斜线和前缀长度
			else {
				sb.append(prefix);
				len = dot_count * 8 + 8;
			}
			// 这里是将后缀省略的0补上
			for (int j = dot_count; j < 3; j++) {
				sb.append(".0");
			}
			prefixes[i] = new Prefix(sb.toString(), len);
		}

		// 以IP地址为第一关键字，以前缀长度为第二关键字，从小到大排序
		Arrays.sort(prefixes);

		// 从小到大合并，这里使用stack进行优化，从90分提到100分
		Stack<Prefix> stack = new Stack<>();
		stack.push(prefixes[0]);
		for (int i = 1; i < prefixes.length; i++)
		{
			if (!prefixes[i].isSubsetOf(stack.peek())) {
				stack.push(prefixes[i]);
			}
		}
		List<Prefix> list = new ArrayList<>();
		for (Prefix prefix : stack) {
			list.add(prefix);
		}

		// 同级合并
		for (int i = 0; i < list.size(); i++) {
			Prefix a = list.get(i);
			if (i + 1 < list.size())
			{
				Prefix b = list.get(i + 1);
				// 确保new_a的合法性
				// a与b互补，即a和b的并集等于new_a的匹配集
				if (a.getLen() > 0 && a.match(b)) 
				{
					list.set(i, new Prefix(a));
					list.remove(i + 1);
					// 之前存在元素
					if (i > 0) i-=2;
					else i--;
				}
			}
		}

		for (int i = 0; i < list.size(); i++) {
			out.println(list.get(i));
		}
	    out.close();
	    f.close();
	}
}