合并IP地址

合并IP地址

问题描述

给定一组IPv4地址,其中每个元素可能由单个IP构成(例如192.168.0.1),也可能由一个IP段构成(如192.168.0.10 - 192.168.0.15),请将给定的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"}

这个问题是基于

LC56区间合并问题

但问题是首先需要将IP地址区间转换为可比较的区间,但注意到Java中Int类型最大只能表示31位的正数,并不能完整的表示一个32位IP地址,而Java并没有提供无符号数,所以存储IP地址,并且用来比较大小,需要用到long类型,输出要求是同样的IP格式,所以涉及到IP地址的Stringlong的相互转换。

StringToLong

显而易见的是,32位的IP地址由.分割为256进制的四个8位的字段,当转换成数字时,可以从右往左逐乘相加。

public static long ipToLong(String ip) {
        String ips[] = ip.split("\\.");
		long ipLong = 0;
    
        for (int i = 0; i < 0; i++) {
            ipLong = ipLong * 256 + Long.parseLong(ips[i]);
        }

        return ipLong;
}

但是存在一种效率更高的方法,就是对于每个字段,我们进行移位操作,然后再做一个|操作,比如对于192.168.19.1这个地址来说,转换成二进制即11000000 10101000 00010011 00000001 192是字段的高8位,

我们将IP按.分割为大小为4的数组后,将第一个数字,左移24位,即得到11000000 00000000 00000000 00000000,同样将第二个数字左移16位,得到10101000 00000000 00000000,以此类推,将第三个数字左移8位得到00010011 00000000,最低的八位不需要移位,然后将四个结果进行操作,得到的就是IP地址的十进制形式。具体实现形式如下

public static long ipToLong(String ip) {
        String ips[] = ip.split("\\.");

        long ipLong = (Long.parseLong(ips[0]) << 24) |
                      (Long.parseLong(ips[1]) << 16) |
                      (Long.parseLong(ips[2]) << 8) |
                      (Long.parseLong(ips[3]));

        return ipLong;
    }

或者写成循环

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

        return ipLong;
    }

LongToString

这里同样可以贯彻上面对位运算的思想,依旧使用上面的栗子IP地址192.168.19.1的数字表示为ip = 3232240385,我们将long类型从左往右逐步取8位,对于高8位只需要,将long类型的IP地址右移24位即可(这里注意一点,如果是32位的int类型进行转换时需要使用无符号位移>>>),即ip>>24,而要取到从左往右第二个8bit时,我们可以将ip的高8位置零,具体做法0xffffff & ip,然后右移16位即可,同样取第三个8bit,可以将高16位置零,然后右移8位即可,最后只需将高24位置零可以得到低8位,然后中间假如分隔符拼接得到String类型的IP地址,具体做法如下。

public static String ipToString(Long ip) {
        StringBuilder sb = new StringBuilder();

        sb.append(String.valueOf(ip >> 24));
        sb.append(".");
        sb.append(String.valueOf((0xffffff & ip) >> 16));
        sb.append(".");
        sb.append(String.valueOf((0xffff & ip) >> 8));
        sb.append(".");
        sb.append(String.valueOf(0xff & ip));

        return sb.toString();
}

也可以写成循环

public static String ipToStringCycle(long ip) {
        String ipString[] = new String[4];

        for (int i = 0; i < 4; i++) {
            //取long类型ip地址的后32位
            long and = ip & (0xffffffff >>> (i * 8));
            //取上面结果的高8位
            ipString[i] = String.valueOf(and >> ((3 - i) * 8));
        }

        return String.join(".", ipString);
}

区间合并

接下来看如何将区间进行合并操作,首先将给定的数组按左边界进行排序操作,然后遍历排好序的二维数组(数组中每一维两个元素代表一个区间的左右端点)此时

  1. 如果当前区间的左端点在数组arr中最后一个区间的右端点之后,那么它们不会重合,我们可以直接将这个区间加入数组arr的末尾;

  2. 否则,它们重合,我们需要用当前区间的右端点更新数组arr中最后一个区间的右端点,将其置为二者的较大值。

这样我们就可以在只遍历一次O(n)时间复杂度下将区间合并。

public static long[][] mergeSection(long[][] arr) {
    Arrays.sort(arr, (a, b) -> (int)(a[0] - b[0]));

    int  n = arr.length;
    List<long[]> list = new ArrayList<>();

    for (int i = 0; i < n; i++) {
        long left = arr[i][0], right = arr[i][1];
        //[a,b]区间和[b + 1, c]区间可以构成[a,c]区间
        //所以在遍历[a,b]时,只需要判断是否b >= b-1即可
        while (i < n - 1 && right  >= arr[i + 1][0] - 1) {
            right = Math.max(right, arr[i + 1][1]);
            i++;
        }
        list.add(new long[]{left, right});
    }
    
    return list.toArray(new long[list.size()][2]);
}

完整代码

public class IPMerge {
    public static void main(String[] args) {
        String[] ss = {"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> list = new ArrayList<>();
        for (int i = 0; i < ss.length; i++) {
            list.add(ss[i]);
        }


        List<String> res = merge(list);

        for (String s : res) {
            System.out.println(s);
        }
    }

    public static List<String> merge (List<String> input) {
        // write code here
        int n = input.size();
        List<String> res = new ArrayList<>();
        long[][] arr = new long[n][2];

        for (int i = 0; i < n; i++) {
            String ipStr = input.get(i);
            long ip1, ip2;
            int index = ipStr.indexOf(‘-‘);
            if (index >= 0) {
                ip1 = ipToLong(ipStr.substring(0, index));
                ip2 = ipToLong(ipStr.substring(index + 1, ipStr.length()));
            } else {
                ip1 = ipToLong(ipStr.substring(0, ipStr.length()));
                ip2 = ip1;
            }
            arr[i][0] = ip1;
            arr[i][1] = ip2;
        }

        arr = mergeSection(arr);

        for (long[] a : arr) {
            if (a[0] == a[1]) {
                res.add(ipToString(a[0]));
            } else {
                String s = ipToString(a[0]) + "-" + ipToString(a[1]);
                res.add(s);
            }
        }

        return res;
    }

    public static long[][] mergeSection(long[][] arr) {
        Arrays.sort(arr, (a, b) -> (int)(a[0] - b[0]));

        int  n = arr.length;
        List<long[]> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            long left = arr[i][0], right = arr[i][1];
            //[a,b]区间和[b + 1, c]区间可以构成[a,c]区间
            //所以在遍历[a,b]时,只需要判断是否b >= b-1即可
            while (i < n - 1 && right  >= arr[i + 1][0] - 1) {
                right = Math.max(right, arr[i + 1][1]);
                i++;
            }
            list.add(new long[]{left, right});
        }

        return list.toArray(new long[list.size()][2]);
    }

    public static long ipToLong(String ip) {
        String ips[] = ip.split("\\.");

        long ipLong = 0;
        for (int i = 0; i < 4; i++) {
            ipLong |= Long.parseLong(ips[i]) << (24 - 8 * i);
        }
        
        return ipLong;
    }

    public static String ipToString(long ip) {
        String ipString[] = new String[4];

        for (int i = 0; i < 4; i++) {
            //取long类型ip地址的后32位
            long and = ip & (0xffffffff >>> (i * 8));
            //取上面结果的高8位
            ipString[i] = String.valueOf(and >> ((3 - i) * 8));
        }

        return String.join(".", ipString);
    }
}

合并IP地址

上一篇:linux jdk1.8安装


下一篇:vue拖拽建站的简单模式vue-grid-layout