首页 > 代码库 > Snapchat - IPFilter

Snapchat - IPFilter

2024-08-16 16:55:03   223人阅读

这道题题意好难理解……

首先说一下IP，二进制表示的IP有32位，一般8位一分隔，转换成十进制，就是0.0.0.0 ~ 255.255.255.255

给你一些IP的规则，比如"7.7.7.7/8","123.2.67.3/8"，这个代表着比如7.7.7.7所对应的32位的表示，00000111*4，8表示取前8位，把所有以00000111开头的ip地址都看成一组，如果在这组内就被filter掉。

所以思路是：

1. 建立ipRule的trie，提供搜索的功能

2. 搜索

 

  1     public List<String> filter(List<String> rules, List<String> IPs) {  2         if(rules == null || rules.size() == 0 || IPs == null || IPs.size() == 0) {  3             return IPs;  4         }  5         Trie ruleTrie = new Trie();  6         prepareRule(ruleTrie, rules);  7         List<String> res = new ArrayList<String>();  8         filterIPs(IPs, ruleTrie, res);  9         return res; 10     } 11      12      13     private void prepareRule(Trie ruleTrie, List<String> rules) { 14         for(String rule: rules) { 15             StringBuilder sb = new StringBuilder(); 16             String[] parts = rule.split("/"); 17             int bits = Integer.parseInt(parts[1]); 18             String[] ipBlocks = parts[0].split("\\."); 19             for(String block: ipBlocks) { 20                 String blockStr = Integer.toBinaryString(Integer.parseInt(block)); 21                 int leadingZeros = 8 - blockStr.length(); 22                 while(leadingZeros-- > 0) { 23                     sb.append("0"); 24                 } 25                 sb.append(blockStr); 26             } 27             String curRule = sb.toString().substring(0, bits); 28             ruleTrie.insert(curRule); 29         } 30     } 31      32     private void filterIPs(List<String> IPs, Trie ruleTrie, List<String> res) { 33         for(String ip: IPs) { 34             StringBuilder sb = new StringBuilder(); 35             String[] ipBlocks = ip.split("\\."); 36             for(String block: ipBlocks) { 37                 String blockStr = Integer.toBinaryString(Integer.parseInt(block)); 38                 int leadingZeros = 8 - blockStr.length(); 39                 while(leadingZeros-- > 0) { 40                     sb.append("0"); 41                 } 42                 sb.append(blockStr); 43             } 44             String binaryIP = sb.toString(); 45             if(!ruleTrie.startsWith(binaryIP)) { 46                 res.add(ip); 47             } 48         } 49     } 50  51  52     class TrieNode { 53         char c; 54         boolean isLeaf; 55         TrieNode[] children; 56          57         public TrieNode() { 58             children = new TrieNode[2]; 59             isLeaf = false; 60         } 61     } 62      63     class Trie { 64         TrieNode root; 65          66         public Trie() { 67             root = new TrieNode(); 68         } 69          70         public void insert(String s) { 71             if(s == null || s.length() == 0) { 72                 return; 73             } 74             TrieNode cur = root; 75             for(int i = 0; i < s.length(); i++) { 76                 char c = s.charAt(i); 77                 int index = c - ‘0‘; 78                 if(cur.children[index] == null) { 79                     cur.children[index] = new TrieNode(); 80                 } 81                 cur.children[index].c = c; 82                 cur = cur.children[index]; 83             } 84             cur.isLeaf = true; 85         } 86          87         public boolean startsWith(String s) { 88             TrieNode cur = root; 89             for(int i = 0; i < s.length(); i++) { 90                 char c = s.charAt(i); 91                 int index = c - ‘0‘; 92                 if(cur.isLeaf == true) { 93                     return true; 94                 } 95                 if(cur.children[index] == null) { 96                     return false; 97                 } 98                 cur = cur.children[index]; 99             }100             return cur.isLeaf;101         }102     }103     104     public static void main(String[] args) {105         IPFilter sample = new IPFilter();106         List<String> rules = new ArrayList<String>(Arrays.asList("7.7.7.7/8","123.2.67.3/8"));107         List<String> IPs = new ArrayList<String>(Arrays.asList("23.2.4.1","7.3.4.1","5.1.2.3","123.2.67.3"));108         List<String> res = sample.filter(rules, IPs);109         System.out.println(res);110     }

 

Snapchat - IPFilter


联系
我们