IPtoCIDR [source code]
public class IPtoCIDR {
static
/******************************************************************************/
class Solution {
public List<String> ipToCIDR(String ip, int n) {
/* Parse IP, multiply into a LONG value */
String[] tokens = ip.split ("\\.");
assert tokens.length == 4;
List<String> res_ls = new ArrayList<String> ();
Integer token = null;
long addr = 0;
for (int i = 0; i < 4; i++) {
try {
token = Integer.parseInt (tokens[i]);
} catch (Exception e) {
e.printStackTrace ();
return res_ls;
}
addr *= 256;
addr += token;
}
String bin_addr_str = long_to_bin_str (addr);
/* Find a block at each iteration, by finding the maximum number of trailing 0s, satisfying:
1. not overflow 32 bit limit
2. has to be a 0 bit
3. does not exceed N, which is the number of IPs we need. Creating a block that is bigger
than necessary can be troublesome to process later */
while (true) {
int i = 0;
char[] chs = bin_addr_str.toCharArray ();
while (i < 32 && chs[31 - i] == '0' && (1 << (i + 1)) <= n) {
/* Move I, flip the 0 bit to 1: to make calculating the new START address easier later */
chs[31 - i++] = '1';
}
String next_bin_addr_str = String.valueOf (chs);
long next_addr = Long.parseLong (next_bin_addr_str, 2);
// Number of IPs to store in this block
int interval_len = (int) (next_addr - addr) + 1;
n -= interval_len;
res_ls.add (num_to_string (addr) + '/' + (32 - i));
if (n == 0) {
break;
}
// Now NEXT_ADDR has trailing 11..11, add 1 to find next start with 00..00
addr = next_addr + 1;
bin_addr_str = long_to_bin_str (addr);
assert addr < (1L << 32);
}
return res_ls;
}
/* Easy utility to turn 32-bit binary into something like 2.3.3.4 */
public String num_to_string (long addr) {
int pos = 3;
long[] res_ar = new long[4];
while (addr > 0) {
long digit = addr & 0xff;
res_ar[pos--] = digit;
addr >>= 8;
}
StringBuilder sb = new StringBuilder ();
for (int i = 0; i < 4; i++) {
sb.append (res_ar[i] + (i < 3 ? "." : ""));
}
return sb.toString ();
}
/* Easy wrapper around toBinaryString to make sure result is strictly 32-bit */
public String long_to_bin_str (long l) {
StringBuilder sb = new StringBuilder ();
String lstr = Long.toBinaryString (l);
while (32 - sb.length () - lstr.length () > 0)
sb.append ('0');
sb.append (lstr);
assert sb.length () == 32;
return sb.toString ();
}
}
/******************************************************************************/
public static void main(String[] args) {
IPtoCIDR.Solution tester = new IPtoCIDR.Solution();
String[] inputs = {
"255.0.0.8", "6",
"255.0.0.8", "8",
"255.0.0.7", "10",
"117.145.102.62", "8",
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
String ip = inputs[2 * i];
int n = Integer.parseInt (inputs[2 * i + 1]);
List<String> output = tester.ipToCIDR (ip, n);
System.out.printf (
"%s, %d->\t%s\n",
ip, n, output
);
}
}
public static String bin_to_string (String ip) {
char[] chs = ip.toCharArray ();
StringBuilder sb = new StringBuilder ();
int i = 0;
while (chs.length - i > 32) {
sb.append (chs[i++]);
}
if (i > 0)
sb.append ('\t');
int ip_len = chs.length;
while (ip_len - i < 32) {
sb.append ('0');
ip_len++;
}
if (ip_len > chs.length)
sb.append ('\t');
for (; i < chs.length; i++) {
sb.append (chs[i]);
if ((i + 1) % 8 == 0)
sb.append ('\t');
}
return sb.toString ();
}
}
题目比较长, 读起来还是挺费时间的, 关键是读完了之后并不是特别理解到底怎么做; 大概理解题目的意思, 但是没有什么思路, 就连笨办法都几乎没有什么头绪. 比较奇怪的是好像普遍大家都认为这个题目很简单, AC率倒是很高;
感觉这个题目必须要自己动笔, 但是手头并没有纸笔, 这个很头疼;
规定时间以内没有想到一个合理的解法; 大概规定时间结束之后, 才大概好像有点想法了; 我用来思考的两个例子是{255.0.0.7, 10} and {255.0.0.8, 8}, {255.0.0.8, 6};
这题如果有unsigned可以用, 是很好的, 但是java好像不支持这个. 这个帖子里面有一些关于unsigned的讨论, 但是好像并不解决我的问题; java对于unsigned的支持并没有一个type的支持, 只有一些type内的method的支持, 这个并不够, 因为我这里最后需要的其实是一个可以做arithmetic的操作, 只是单纯的在parse和toString的时候才提供unsigned的支持, 好像完全不够用, 不能让int本身具有完成arithmetic的能力;
在java里面, declare成unsigned什么的时候, 好像在java里面并没有太大的作用; 上面的那个帖子里面有提到过;
这题最后几乎就要放弃了, 因为实在是花了太多时间了; 最后好歹是AC了, 速度是27ms, 暂时不知道百分比, 答案太少;
这个题目一个奇怪的地方是downvote特别厉害; 我自己做的时候, 感觉花点时间还是能想到答案的, 但是感觉这个题目难度还是不同于一般的easy; 之所以这个题目最后没有能够评到更高的难度的一个原因, 可能是因为这个难度本身的思路还是很清晰的, 就是写起来的时候可能不那么简单, 很容易犯错误; 我写这个题目的时候, 各种debug手段都用上了, 都让我回想起来当时写Pintos的感觉了;
另外, 我是没有太依赖于给的这个hint的; 不过感觉这个hint给出的应该是一个很特例的做法, 而且依赖于any integer can be disassembled into a sum of powers of 2这样的性质; 也就是最后的tag里面给的bit操作的提示; 我自己的这个答案其实是没有太依赖与bit操作的; 这个题目的downvote我估计可能也跟这个有关系: 答案的局限性比较强;
Single Case Development
就跟在写Pintos的时候一样, 我还是意识到了我自己的一个问题, 就是我在写一个算法的flow的时候, 在设计的时候, 经常喜欢想要一下子能写一个兼顾所有case的flow; 这种习惯真的很致命. 也许以后等我变强了以后, 可以这样做; 但是我目前的臭水平, 强行用这种高手才能驾驭的方式来写代码, 最后真的是给自己减速;
以后写flow的时候, 最好的办法, 就是盯准一个不是特别special的case, 然后就用这个case来develop; 然后写出一个能过这个case的代码之后, 再找下一个case, 看看哪里被break了, 再来做相应的patch; 不要想着一下子就能写出一个万无一失的解法. 这个真的是一个非常有问题的习惯; 就算是Guoye写代码的时候, 他其实也是习惯从concrete case出发;
toBinaryString 不对齐问题的处理: wrapper
在整体代码成型之后, 一个问题出现就是我之前从long到string的转换, 几乎是依赖于toBinaryString这个函数, 但是这个函数有一个问题, 会自从delete leading 0, 但是我这里需要这个0. 这个就有点烦人. 解决方案其实也是可以说收到Pintos的启发, 就是用一个wrapper来加强这个API就行了: Interface Enhancement. enhance之后的这个toString保证一定输出32位, 就可以了; 然后把所有原来对toBinaryString的reference改一下就行了;
总体来说, 这个题目确实花的时间太多了, 但是不可谓学到了很多东西; 不仅包括写算法的习惯, 还包括对java语言个性的理解, 包括1L << 32这个东西, 以前也是没有注意到过; 不过这个其实有点类似之前写Pintos的时候, undefined literal arithmetic问题的解决方法;
这个是editorial的解法:
class Solution {
public List<String> ipToCIDR(String ip, int n) {
long start = ipToLong(ip);
List<String> ans = new ArrayList();
while (n > 0) {
int mask = Math.max(33 - bitLength(Long.lowestOneBit(start)),
33 - bitLength(n));
ans.add(longToIP(start) + "/" + mask);
start += 1 << (32 - mask);
n -= 1 << (32 - mask);
}
return ans;
}
private long ipToLong(String ip) {
long ans = 0;
for (String x: ip.split("\\.")) {
ans = 256 * ans + Integer.valueOf(x);
}
return ans;
}
private String longToIP(long x) {
return String.format("%s.%s.%s.%s",
x >> 24, (x >> 16) % 256, (x >> 8) % 256, x % 256);
}
private int bitLength(long x) {
if (x == 0) return 1;
int ans = 0;
while (x > 0) {
x >>= 1;
ans++;
}
return ans;
}
}
他这里用到了一个函数: lowestOneBit:
java> Integer.lowestOneBit(12)
java.lang.Integer res1 = 4
java> Integer.toBinaryString(12)
java.lang.String res2 = "1100"
java> Integer.toBinaryString(4)
java.lang.String res3 = "100"
这个解法其实应该就是根据hint的思路的那种解法了, 跟我的解法比起来, 一个很明显的优势就是, 他不依赖于string操作, 而我的解法则非常依赖于先convert到string然后再来操作; 他这样的做法的好处在于, 首先避免了这个多于的string转换带来的overhead, 其次是, 因为java的toBinaryString操作有一个自动delete heading zero的操作, 所以最后得到的结果是veriable length, 这个问题也被他给避免了; 他避免string操作的一个手段就是依赖于lowestOneBit这样的函数; discussion里面其他答案里面用其他的API来避免string操作的做法; 说白了, 还是知道的API越多, 越有利; 好像Stefan的tip文章里面提到了这个问题;
总体来说这个答案是非常优秀的, 思路是最优的, 而且这个作者的代码写的也是非常的漂亮, 无论是结构还是style, 都完全没有的挑剔;
how to read hard algorithm
但是虽然看完了代码, 还是感觉对这个算法的正确性有些不太有把握; 这个时候我的意识其实发呆了一会儿, 但是是没有必要的; 每当这种没有办法彻底读懂别人的算法的时候, 直接一个trace跑一遍就行了; 虽然这题的test case看起来都有点复杂, 但是你跑了就知道, 其实一点都不复杂; 而且, 不要因为只跑了一个trace所以担心对算法的理解不彻底, 这个担心是完全没有必要的, 因为只要你把一个相对general的trace彻底理解了, 那么其他的trace可以直接用variation的方式来理解, 完全不会需要多少的额外时间; 关键是从0到1的这个过程;
所以这题, 我决定还是用我写自己的算法的时候的三个例子来帮助理解;
这一行:
int mask = Math.max(33 - bitLength(Long.lowestOneBit(start)), 33 - bitLength(n));
决定了每一个block的capacity/count; 注意, 这一行如果写成33 - Math.min (bitLength (Long.lowestOneBit (start)), bitLength (n))可能会更好理解一些, 也跟hint的表达更加一致; 假设我们的IP就是255.0.0.8, 那么最后8bit就是1000, 这个得到的bitLength的结果就是8;
关键来了, 你怎么理解n的bitLength? 这里其实用了一个很巧妙的技巧, 就是两个数字, 他们的bitLength的大小关系跟他们自己实际上的value的大小关系之间的对应性; 我们这里1000, 表示最后实际上这个block最多只能装8个, 但是最后我们是否需要装满这8个, 还取决于n有多大; 这题这里其实是可以直接这个8明确的算出来, 然后跟n比较的, 这个就很像我自己的做法了; 但是利用bitLength的大小关系的对应性, 我们可以看到, 假如n是6, 那么6的bitLength肯定小于8的bitlength; 反过来, 如果n是10, 那么n的bitlength肯定是>=1000对应的8, 所以我们直接取8; 综合起来, 就是取这个bitlength的最小值就行了; 这个insight可以帮助我们省略掉大量的代码量;
后面的start += 1 << (32 - mask);是另外一个关键; 首先注意到一点, 这个代码的作者有一个想法跟我是共通的, 就是每一个block要从00..00的位置开始计算, 更加方便; 这里他更新start的方式, 其实就非常类似于在Pintos里面, load_segment或者inode_read/write里面的block advance技术; 因为你要注意到, 我们这里的mask, 是上面已经用一次类似alignment计算得到的结果(一般这个alignment实际的实现方式就是一个最值操作). 当然, 这里实际上的结算过程比Pintos里面的要稍微复杂一点, 但是核心思路是一致的; 在下面advance的时候, 最好的思路就是用这个calculated result来进行advance, 而不是重新从raw的结果来重新计算;
总体来说这个题目, 我个人认为还是非常有启发意义的, 非常考虑一个程序员刷题之外的基本功, 事实上, 你最后写出来的代码漂亮不漂亮, 很大程度上能够暴露出你真实的软实力; 这个editorial代码就真的是没有什么可以调提的了;
avoid generic
一个我个人需要吸取的经验教训就是, 我太过于在乎代码是否漂亮, 所以经常一个很简单的事情, 都追求要写的很generic, 很万金油, 最后浪费了很多的时间; 比如这里longToIP这个函数, 其实就是很好写的一个东西, 但是我强行追求用循环来写, 最后你看看, 代码量比人家的的多太多了, 人家真的就是一行就写完了, 我还吭哧吭哧两个循环; 自己知道这个东西的长度了, 就不用追求用一个很automatic的循环来做了;
discussion:
@chrislzm said in Java Solution (18ms):
Maximize the number of trailing zeros, which will give us the largest block of IP addresses possible and optimal answer.
We can increase the number of trailing zeros by creating a CIDR block that uses all the current trailing zeros available. E.g.
IP address bits:
...0010 = Block of 2 IP addresses available
So we create a block of 2 IP addresses and add that range to the IP = ...0010 + 0010 =
...0100 = Now a block of 4 IP addresses is available. And so forth.In the case of the example from the problem:
...0111 = Only 1 IP address available to start. 0 trailing zeros = Block of 1 address available.
After we add 1 to the IP address:
...1000 = 3 trailing zeros = Block of 8 IP addresses available. etc.
class Solution {
public List<String> ipToCIDR(String ipString, int range) {
int ip = convertStringIPtoNum(ipString);
List<String> cidrBlocks = new ArrayList<>();
while(range > 0) {
int zeros = getZeros(ip);
int thisRange = 1 << zeros;
thisRange = Math.min(range,thisRange);
getCidrBlocks(ip, thisRange, cidrBlocks);
ip += thisRange;
range -= thisRange;
}
return cidrBlocks;
}
private int getZeros(int ip) {
int zeros = 0;
for(int i = 0; i<32; i++) {
if((ip & (1 << i)) == 0) {
zeros++;
} else break;
}
return zeros;
}
private void getCidrBlocks(int ip, int range, List<String> cidrBlocks) {
if(range <= 0) return;
int i = 0;
while((1 << i+1) <= range) i++; // Get power of 2 within range
int prefixLength = 32-i;
int thisRange = 1 << i;
String ipString = convertNumToIPString(ip) + "/" + prefixLength;
cidrBlocks.add(ipString);
getCidrBlocks(ip+thisRange,range-thisRange,cidrBlocks);
}
private String convertNumToIPString(int num) {
StringBuilder sb = new StringBuilder();
for(int i=0; i<4; i++) {
if(i>0) sb.insert(0, '.');
sb.insert(0,(num & 255));
num >>= 8;
}
return sb.toString();
}
private int convertStringIPtoNum(String ipstring) {
String[] ipArray = ipstring.split("[.]");
int ip = 0;
for(int i=0; i<4; i++) {
ip += Integer.parseInt(ipArray[i]) * (1 << (8*(3-i)));
}
return ip;
}
}
这个算法大概扫了一眼, 整体思路还是类似的, 不过他的方法跟我一样, 更手动, 不同的是, 他没有依赖于string操作, 全程用数学来做;
另外他这个 getZeros 函数写的稍微有点蠢, 不过更加general;
几个utility函数的思路还是很直接的;
另外一个:
class Solution {
public List<String> ipToCIDR(String ip, int range) {
ArrayList<String> result = new ArrayList<>();
int origin = str2Int(ip), lastCount = Integer.numberOfTrailingZeros(origin);
while (range != 0) {
int segment = (int) Math.pow(2.0, (double) lastCount);
if (segment <= range) {
result.add(int2Str(origin) + "/" + String.valueOf(32 - lastCount));
origin += segment;
range -= segment;
lastCount = Integer.numberOfTrailingZeros(origin);
} else {
lastCount--;
}
}
return result;
}
private String int2Str(int ip) {
return ((ip >> 24) & 0xFF) + "." + ((ip >> 16) & 0xFF) + "." + ((ip >> 8) & 0xFF) + "." + (ip & 0xFF);
}
private int str2Int(String ip) {
int result = 0;
String[] inArray = ip.split("\\.");
for (int i = 3; i >= 0; i--) {
result |= Integer.parseInt(inArray[3 - i]) << (i * 8);
}
return result;
}
}
这里他用的函数是 numberOfTrailingZeros, 完成的功能是类似的;
不过他这个算法有一个小细节值得注意一下. 首先, 他的 lastCount代表的是0的count; 但是他的算法有一个小问题, 直接用 numberOfTrailingZeros函数得到的这个count, 可能会出现过大的问题; 在我自己写算法的时候, 我当时是有意识的避免了这个问题, 但是他这里看来, 这个问题是不好避免的(除非完全用editorial的 bitLength比较来做, 但是那个技巧比较tricky, 他这里决定block(segment)大小的时候, 实际上用的还是简单的value比较). 随后他对于这个oversize问题的解决方法还算可以接受, 当发现segment太大的时候, 直接缩小就行了;
总体来说, 这个算法写的还是不错的;
另外, 这个人的代码里面值得学习的一个东西, 就是你看他的naming里面, To全都换成了2; 这个其实是一个比较trivial的技巧, 但是如果你用习惯了underline, 突然转换到camel, 可能会忘记这个小技巧; 在camel style里面, 这个写法是非常有必要的;
这个是discussion另外一个:
public List<String> ipToCIDR(String ip, int range) {
long x = 0;
String[] ips = ip.split("\\.");
for (int i = 0; i < ips.length; ++i) {
x = Integer.parseInt(ips[i]) + x * 256;
}
List<String> ans = new ArrayList<>();
while (range > 0) {
long step = x & -x;
while (step > range) step /= 2;
ans.add(longToIP(x, (int)step));
x += step;
range -= step;
}
return ans;
}
String longToIP(long x, int step) {
int[] ans = new int[4];
ans[0] = (int) (x & 255); x >>= 8;
ans[1] = (int) (x & 255); x >>= 8;
ans[2] = (int) (x & 255); x >>= 8;
ans[3] = (int) x;
int len = 33;
while (step > 0) {
len --;
step /= 2;
}
return ans[3] + "." + ans[2] + "." + ans[1] + "." + ans[0] + "/" + len;
}
总体的思路其实还是类似的, 而且这个算法也有oversize的问题, 但是优雅的解决掉了;
这个算法一个值得学习的亮点: x & -x, 实际实验了一下, 这个好像就是 lowestOneBit函数的实际实现方式; 这个还真的是没有想到;
除开这个东西以外的地方, 其实做法就都差不多了; 他同样没有意识到editorial里面 bitLength的技巧;
总体来说这题是一个非常有教育意义的题目, 也反应出了airbnb的题目真的是不简单, 就算是easy的题目, 最后也是分量十足;
另外, 这题其实严格来说也是可以用我自己的笨办法人逻辑的心法来攻略的, 但是这个题目的一个难点在于, 笨办法本身并不是那么容易发现; 一旦当你理解到block长度来自于trailing zeros这样的东西的时候, 然后总结一个笨办法就不是很难了;
事实上, 这个题目最后让你写出来的代码就是这样一个笨办法而已; 至于最后能写到多漂亮, 就是你自己的本事了;
Problem Description
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].
Difficulty:Easy
Total Accepted:956
Total Submissions:1.8K
Contributor:1337c0d3r
Companies
airbnb
Related Topics
bit manipulation
Similar Questions
Restore IP AddressesValidate IP Address
Hide Hint 1
Convert the ip addresses to and from (long) integers. You want to know what is the most addresses you can put in this block starting from the "start" ip, up to n. It is the smallest between the lowest bit of start and the highest bit of n. Then, repeat this process with a new start and n.