Massive Algorithms: LeetCode 751

LeetCode 751 - IP to CIDR

http://bookshadow.com/weblog/2017/12/24/leetcode-ip-to-cidr/

Given a start IP address ip and a number of ips we need to cover n, return a representation of the range as a list (of smallest possible length) of CIDR blocks.

A CIDR block is a string consisting of an IP, followed by a slash, and then the prefix length. For example: "123.45.67.89/20". That prefix length "20" represents the number of common prefix bits in the specified range.

Example 1:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]
Explanation:
The initial ip address, when converted to binary, looks like this (spaces added for clarity):
255.0.0.7 -> 11111111 00000000 00000000 00000111
The address "255.0.0.7/32" specifies all addresses with a common prefix of 32 bits to the given address,
ie. just this one address.

The address "255.0.0.8/29" specifies all addresses with a common prefix of 29 bits to the given address:
255.0.0.8 -> 11111111 00000000 00000000 00001000
Addresses with common prefix of 29 bits are:
11111111 00000000 00000000 00001000
11111111 00000000 00000000 00001001
11111111 00000000 00000000 00001010
11111111 00000000 00000000 00001011
11111111 00000000 00000000 00001100
11111111 00000000 00000000 00001101
11111111 00000000 00000000 00001110
11111111 00000000 00000000 00001111

The address "255.0.0.16/32" specifies all addresses with a common prefix of 32 bits to the given address,
ie. just 11111111 00000000 00000000 00010000.

In total, the answer specifies the range of 10 ips starting with the address 255.0.0.7 .

There were other representations, such as:
["255.0.0.7/32","255.0.0.8/30", "255.0.0.12/30", "255.0.0.16/32"],
but our answer was the shortest possible.

Also note that a representation beginning with say, "255.0.0.7/30" would be incorrect,
because it includes addresses like 255.0.0.4 = 11111111 00000000 00000000 00000100 
that are outside the specified range.

Note:

ip will be a valid IPv4 address.
Every implied address ip + x (for x < n) will be a valid IPv4 address.
n will be an integer in the range [1, 1000].

将起始ip转为int，遍历[ipInt, ipInt + range)

假设当前遍历到了第x个ip地址，记cIpInt = ipInt + x

计算cIpInt末尾0的个数，记为zeros，重复将zeros-1，直到x + 1<<zeros不大于range为止

将ipInt复原为IP地址 / 32 - zeros加入结果列表

https://felon03.github.io/2017/12/29/LeetCode-751-IP-to-CIDR/

这个问题是在给定的起始IP地址，求最少的CIDR正好覆盖n个IP地址。所求的地址要求是连续的，并且要在起始IP的后面。

先说明一下255.255.0.8/29中29的含义：
一个IPv4的地址总共有32位，可以表示29表示的是IP的前29为是固定的，后三位可以改变，因此可以覆盖

2^{3}

(8)个IP。那么要使CIDR尽量的少，就让固定的IP的位数尽量少，同时要保证IP是连续的。

比如我们以255.0.0.7开始，覆盖30个地址，那么就有：

255.0.0.7/32
只有一个IP地址剩余30 - 1 = 29

接下来的IP地址是 255.0.0.8，最后8位是: 00001000，还有3位可以更改
则有255.0.0.8/29 可以覆盖8个IP，剩余29 - 8 = 21

8个地址后的IP是255.0.0.16，最后8位是: 00010000，还有4位可以更改
则有255.0.0.16/28 可以覆盖16个IP，剩余21 - 16 = 5

接下来的IP地址是255.0.0.32，最后8位是： 00100000，还有5位可以更改，而剩余的要覆盖的IP只有5个，因此要小于5，否则覆盖的IP范围就会超过给定的个数，因此是4个，即对最后两位进行更改
则有255.0.0.32/30 可以覆盖4个IP，剩余5 - 4 = 1

那么最后一个要覆盖的就是255.0.0.36/32，剩余0个要覆盖
至此可以得到最少的CIDR。

http://www.cnblogs.com/grandyang/p/8440087.html

此题给了我们一个用字符串表示的ip地址，还有一个整数n，让我们以给定的ip地址为起点，需要覆盖n个ip地址。而这n个ip地址的写法使用无类别域间路由CIDR块来写，所谓的CIDR块，是由一个正常的ip地址，加上斜杠数字，斜杠后面的数字表示这些ip地址具有相同的前缀的个数，比如"255.0.0.7/32"，如果有32个相同的前缀，说明只有唯一的一个ip地址，因为IPv4总共就只有32位。再比如"255.0.0.8/29"，表示有29个相同的前缀，那么最后3位可以自由发挥，2的3次方为8，所以就共有8个ip地址。同理，"255.0.0.16/32"只表示一个地址，那么这三个CIDR块总共覆盖了10个地址，就是我们要求的结果。

由于题目中要求尽可能少的使用CIDR块，那么在n确定的情况下，CIDR块能覆盖的越多越好。根据我们前面的分析，当CIDR块斜杠后面的数字越小，该块覆盖的ip地址越多。那么就是说相同前缀的个数越少越好，但是我们的ip地址又不能小于给定的ip地址，所以我们只能将0变为1，而不能将1变为0。所以我们的选择就是有将最低位1后面的0进行变换，比如"255.0.0.8"末尾有3个0，可以变换出8个不同的地址。那么我们只要找出末尾1的位置，就知道能覆盖多少个地址了。找末尾1有个trick，就是利用 x & -x 来快速找到，这个trick在之前做的题中也有应用。知道了最多能覆盖地址的数量，还要考虑到n的大小，不能超过n，因为题目只要求覆盖n个。确定了覆盖的个数，我们就可以进行生成CIDR块的操作了，之前我们为了求 x & -x，将ip地址转为了一个十进制的数，现在我们要把每一块拆分出来，直接按对应位数量进行右移并与上255即可，斜杠后的数字计算通过覆盖的个数进行log2运算，再被32减去即可

    vector<string> ipToCIDR(string ip, int n) {
        vector<string> res;
        long x = 0;
        istringstream is(ip);
        string t;
        while (getline(is, t, '.')) {
            x = x * 256 + stoi(t);
        }
        while (n > 0) {
            long step = x & -x;
            while (step > n) step /= 2;
            res.push_back(convert(x, step));
            x += step;
            n -= step;
        }
        return res;
    }
    string convert(long x, int step) {
        return to_string((x >> 24) & 255) + "." + to_string((x >> 16) & 255) + "." + to_string((x >> 8) & 255) + "." + to_string(x & 255) + "/" + to_string(32 - (int)log2(step));
    }

https://zhuanlan.zhihu.com/p/35541808

 public static void main(String[] args) {
  IP2CIDR i2 = new IP2CIDR();
  System.out.println(i2.IC("255.0.0.7", 10));
 }
 
 public String IC(String ip,int n){
  //思路，找到这些IPs中从右往左第一位相同的二进制位
  // x & -x ;-x是x的补码，返回x与2^64的最大公约数，
  //即x最多能被n个2整除就返回2^n,如果x是奇数返回1;返回值为0 ，说明x=0;为其他数，表示x为x与2^64的最大公约数
  //一言以蔽之就是获取32位二进制表示中从右往左首次出现1的位置
  long x = 0;
  //以"."划分每个IP
  String[] ipsegment = ip.split("\\.");
  for(int i=0;i<ipsegment .length;i++){
   x = Integer.parseInt(ipsegment [i])+x*256;
  }
  String res = "";
  while(n>0){
   long temp = x & -x;//求得该IP用32位二进制表示中从右往左首次出现1的位置
   //-x才是x的补码，~x为反码
   //temp如果为奇数，则该IP为第一个CIDR块
   //如果偶数，则该IP用二进制表示下的最低有效位的位数能表示的地址的数量
   while(temp>n) {
    temp = temp/2;
   }
                        //到这里temp肯定是小于n的，这告诉我们包括此IP在内的temp个IPs可以用一个ICDR来表示
   //接下来求出这些IPs所处的CIDR
   res+=longToIP(x, (int)temp)+"  ";
   //x加上temp;
   x+=temp;//temp个ips考虑好了，接下来考虑从x+temp考虑
   n-=temp;//还有几个IPs要求ICDR的
  }
  return  res;
 }
 
 public String longToIP(long x,int temp){
  int netID = 32;
  while(temp>0){
   temp/=2;
   netID--;
  }
  
  int[] ans = new int[4];
  for(int i=0;i<ans.length-1;i++){
   ans[i] = (int)(x & 255);
           x>>=8;
  }
  ans[ans.length-1] = (int)x;
  netID++; //加1：比如说某些IPs有m位相同，是指0-m-1位相同
  return ans[3]+"."+ans[2]+"."+ans[1]+"."+ans[0]+"/"+netID;
 }

https://blog.csdn.net/qq_32832023/article/details/78891298

public List<String> ipToCIDR(java.lang.String ip, int range) {
long x = 0;
//获得一个ip地址每一部分
String[] ips = ip.split("\\.");
//将整ip地址看为一个整体，求出整体的int表示
for (int i = 0; i < ips.length; ++i) {
x = Integer.parseInt(ips[i]) + x * 256;
}
List<String> ans = new ArrayList<>();
while (range > 0) {
//求出二进制表示下的最低有效位的位数能表示的地址的数量
//如果为奇数，则=1，即以原单个起始ip地址为第一块
//如果为偶数，则二进制表示下的最低有效位的位数能表示的地址的数量
long step = x & -x;
//如果大于range，则需要缩小范围
while (step > range) step /= 2;
//不大于需要的range，开始处理
//求出现在能表示的step个地址的地址块
ans.add(longToIP(x, (int)step));
//x加上以求出的地址块
x += step;
//range减去以表示的地址块
range -= step;
}//直到range<0
return ans;
}
static String longToIP(long x, int step) {
int[] ans = new int[4];
//&255操作求出后8位十进制表示
ans[0] = (int) (x & 255);
//右移8位，即求下一个块
x >>= 8;
ans[1] = (int) (x & 255);
x >>= 8;
ans[2] = (int) (x & 255);
x >>= 8;
ans[3] = (int) x;
int len = 33;
//每一位就可以表示2个
while (step > 0) {
len --;
step /= 2;
}
return ans[3] + "." + ans[2] + "." + ans[1] + "." + ans[0] + "/" + len;
}

https://github.com/allaboutjst/airbnb/blob/master/src/main/java/ip_range_to_cidr/IPRangetoCIDR.java

        private long ipToLong(String strIP) {
            long[] ip = new long[4];
            String[] ipSec = strIP.split("\\.");
            for (int k = 0; k < 4; k++) {
                ip[k] = Long.valueOf(ipSec[k]);
            }

            return (ip[0] << 24) + (ip[1] << 16) + (ip[2] << 8) + ip[3];
        }

        private String longToIP(long longIP) {
            StringBuffer sb = new StringBuffer("");
            sb.append(String.valueOf(longIP >>> 24));
            sb.append(".");
            sb.append(String.valueOf((longIP & 0x00FFFFFF) >>> 16));
            sb.append(".");
            sb.append(String.valueOf((longIP & 0x0000FFFF) >>> 8));
            sb.append(".");
            sb.append(String.valueOf(longIP & 0x000000FF));

            return sb.toString();
        }

        public List<String> ipRange2Cidr(String startIp, int range) {
            // check parameters
            String a = "";
            long start = ipToLong(startIp);
            long end = start + range - 1;
            List<String> res = new ArrayList<>();
            while (start <= end) {
                // identify the location of first 1's from lower bit to higher bit of start IP
                // e.g. 00000001.00000001.00000001.01101100, return 4 (100)
                long locOfFirstOne = start & (-start);
                int curMask = 32 - (int) (Math.log(locOfFirstOne) / Math.log(2));

                // calculate how many IP addresses between the start and end
                // e.g. between 1.1.1.111 and 1.1.1.120, there are 10 IP address
                // 3 bits to represent 8 IPs, from 1.1.1.112 to 1.1.1.119 (119 - 112 + 1 = 8)
                double currRange = Math.log(end - start + 1) / Math.log(2);
                int currRangeMask = 32 - (int) Math.floor(currRange);

                // why max?
                // if the currRangeMask is larger than curMask
                // which means the numbers of IPs from start to end is smaller than mask range
                // so we can't use as many as bits we want to mask the start IP to avoid exceed the end IP
                // Otherwise, if currRangeMask is smaller than curMask, which means number of IPs is larger than mask range
                // in this case we can use curMask to mask as many as IPs from start we want.
                curMask = Math.max(currRangeMask, curMask);

                // Add to results
                String ip = longToIP(start);
                res.add(ip + "/" + curMask);
                // We have already included 2^(32 - curMask) numbers of IP into result
                // So the next roundUp start must insert that number
                start += Math.pow(2, (32 - curMask));
            }
            return res;
        }

https://blog.csdn.net/qq_32832023/article/details/78891298

做本题需要一些IP地址的知识，还要理解 16 行的x&-x 操作的含义。

！最好自己先思考一下，对基本的可能出现的情况有一个了解。
比如IP地址的最后一块是奇数/偶数的情况；IP地址块扩大时能容纳的数量和n的关系等。

public List<String> ipToCIDR(java.lang.String ip, int range) {

long x = 0;

// 获得一个ip地址每一部分

String[] ips = ip.split("\\.");

// 将整ip地址看为一个整体，求出整体的int表示

for (int i = 0; i < ips.length; ++i) {

x = Integer.parseInt(ips[i]) + x * 256;

}

List<String> ans = new ArrayList<>();

while (range > 0) {

// 求出二进制表示下的最低有效位的位数能表示的地址的数量

// 如果为奇数，则=1，即以原单个起始ip地址为第一块

// 如果为偶数，则二进制表示下的最低有效位的位数能表示的地址的数量

long step = x & -x;

// 如果大于range，则需要缩小范围

while (step > range)

step /= 2;

// 不大于需要的range，开始处理

// 求出现在能表示的step个地址的地址块

ans.add(longToIP(x, (int) step));

// x加上以求出的地址块

x += step;

// range减去以表示的地址块

range -= step;

} // 直到range<0

return ans;

}

static String longToIP(long x, int step) {

int[] ans = new int[4];

// &255操作求出后8位十进制表示

ans[0] = (int) (x & 255);

// 右移8位，即求下一个块

x >>= 8;

ans[1] = (int) (x & 255);

x >>= 8;

ans[2] = (int) (x & 255);

x >>= 8;

ans[3] = (int) x;

int len = 33;

// 每一位就可以表示2个

while (step > 0) {

len--;

step /= 2;

}

return ans[3] + "." + ans[2] + "." + ans[1] + "." + ans[0] + "/" + len;

}

https://uule.iteye.com/blog/2102484
https://freedomly.tk/2017/12/29/LeetCode-751-IP-to-CIDR/


vector<string> ipToCIDR(string ip, int range)

{

    vector<string> ret;

    unsigned num = ip2Num(ip);

    

    while (range)

    {

        int weight = 1;

        int i = 0;

        while (i < 32)

        {

            weight <<= 1;

            if ((1 << i & num) || (weight > range))

                break;

            ++i;

        }

        weight >>= 1;

        range -= weight;

        ret.emplace_back(num2Ip(num) + "/" + to_string(32 - i));

        num += weight;

    }

    return ret;

}

LeetCode 751 - IP to CIDR

Labels

Popular Posts