字节北美电面两题

请问第一题怎么做

自己写了个第二题题解，不过用到了排序，中间该融合的融合，肯定至少是nlogn了，不知道是不是比nlogn还要久。

1. public class Solution {
   
2. 
   
3.     public static void main(String[] args) {
   
4.         List<String> subnetsStrs = new ArrayList<>();
   
5.         subnetsStrs.add("11.23.1.0/24");
   
6.         subnetsStrs.add("11.23.0.0/24");
   
7.         subnetsStrs.add("11.23.7.0/24");
   
8.         subnetsStrs.add("11.23.6.0/24");
   
9.         subnetsStrs.add("11.23.3.0/24");
   
10.         subnetsStrs.add("11.23.2.0/24");
    
11.         List<String> res = mergeSubnets(subnetsStrs);
    
12.         System.out.println(res.toString());
    
13.     }
    
14. 
    
15.     static List<String> mergeSubnets(List<String> subnetStrs) {
    
16.         PriorityQueue<Subnet> subnets = new PriorityQueue<>(
    
17.             (a, b) -> a.maskLen == b.maskLen ? Long.compare(a.mask, b.mask)
    
18.                 : Integer.compare(b.maskLen, a.maskLen));
    
19.         for (String subnet : subnetStrs) {
    
20.             subnets.offer(parseSubnet(subnet));
    
21.         }
    
22.         List<String> res = new ArrayList<>();
    
23.         while (!subnets.isEmpty()) {
    
24.             Subnet subnet = subnets.poll();
    
25.             if (!subnets.isEmpty() && subnets.peek().maskLen == subnet.maskLen
    
26.                 && (subnet.mask ^ subnets.peek().mask) ==
    
27.                 1L << (32 - subnet.maskLen)) {
    
28.                 subnets.poll();
    
29.                 subnets.offer(
    
30.                     new Subnet(subnet.maskLen - 1, removeLastBit(subnet.mask, subnet.maskLen - 1)));
    
31.             } else {
    
32.                 res.add(subnet.toString());
    
33.             }
    
34.         }
    
35.         return res;
    
36.     }
    
37. 
    
38.     static private long removeLastBit(long mask, long newMaskLen) {
    
39.         long tmp = 0;
    
40.         for (int i = 0; i < 32; ++i) {
    
41.             tmp <<= 1;
    
42.             if (i < newMaskLen) {
    
43.                 ++tmp;
    
44.             }
    
45.         }
    
46.         return mask & tmp;
    
47.     }
    
48. 
    
49.     static private Subnet parseSubnet(String subnet) {
    
50.         String[] strs = subnet.split("/");
    
51.         long mask = 0;
    
52.         for (String num : strs[0].split("\\.")) {
    
53.             mask = mask * 256 + Long.parseLong(num);
    
54.         }
    
55.         return new Subnet(Integer.parseInt(strs[1]), mask);
    
56.     }
    
57. 
    
58.     private static class Subnet {
    
59. 
    
60.         int maskLen;
    
61.         long mask;
    
62. 
    
63.         public Subnet(int maskLen, long mask) {
    
64.             this.maskLen = maskLen;
    
65.             this.mask = mask;
    
66.         }
    
67. 
    
68.         @Override
    
69.         public String toString() {
    
70.             return String.valueOf(mask / (1 << 24)) + '.' + mask / (1 << 16) % 256 + '.'
    
71.                 + mask / (1 << 8) % 256 + '.' + mask % 256 + '/' + maskLen;
    
72.         }
    
73.     }
    
74. }

复制代码

Follow up: solve by time complexity O(NlogN).

第一题中的N指代什么？

woshilxd912 发表于 2020-12-6 06:35
自己写了个第二题题解，不过用到了排序，中间该融合的融合，肯定至少是nlogn了，不知道是不是比nlogn还要久 ...

感觉这个解法不对 如果subnet之间是包含关系呢?

treeguard 发表于 2020-12-25 19:08
感觉这个解法不对 如果subnet之间是包含关系呢?

可以举个例子验证一下吗，我也不是很清楚

感谢分享

woshilxd912 发表于 2020-12-26 01:51
可以举个例子验证一下吗，我也不是很清楚

比如说一个 是 1.1.1.0/24 和 1.1.0.0/22 那结果就是 1.1.0.0/22 感觉你的解法没有catch到?

treeguard 发表于 2020-12-25 13:20:55
比如说一个 是 1.1.1.0/24 和 1.1.0.0/22 那结果就是 1.1.0.0/22 感觉你的解法没有catch到?

你这个例子也没法融合，输入是什么，输出就是什么，我的程序跑出来是什么样呢，电脑现在不在身边

woshilxd912 发表于 2020-12-26 05:35
你这个例子也没法融合，输入是什么，输出就是什么，我的程序跑出来是什么样呢，电脑现在不在身边

1.1.0.0/22 已经包含了 1.1.1.0/24所能包含的所有IP地址了

前两轮蠡口