Snapchat - IPFilter
这道题题意好难理解……
首先说一下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掉。
所以思路是:
建立ipRule的trie,提供搜索的功能
搜索
分析& 代码
public List<String> filter(List<String> rules, List<String> IPs) {
if(rules == null || rules.size() == 0 || IPs == null || IPs.size() == 0) {
return IPs;
}
Trie ruleTrie = new Trie();
prepareRule(ruleTrie, rules);
List<String> res = new ArrayList<String>();
filterIPs(IPs, ruleTrie, res);
return res;
}
private void prepareRule(Trie ruleTrie, List<String> rules) {
for(String rule: rules) {
StringBuilder sb = new StringBuilder();
String[] parts = rule.split("/");
int bits = Integer.parseInt(parts[1]);
String[] ipBlocks = parts[0].split("\\.");
for(String block: ipBlocks) {
String blockStr = Integer.toBinaryString(Integer.parseInt(block));
int leadingZeros = 8 - blockStr.length();
while(leadingZeros-- > 0) {
sb.append("0");
}
sb.append(blockStr);
}
String curRule = sb.toString().substring(0, bits);
ruleTrie.insert(curRule);
}
}
private void filterIPs(List<String> IPs, Trie ruleTrie, List<String> res) {
for(String ip: IPs) {
StringBuilder sb = new StringBuilder();
String[] ipBlocks = ip.split("\\.");
for(String block: ipBlocks) {
String blockStr = Integer.toBinaryString(Integer.parseInt(block));
int leadingZeros = 8 - blockStr.length();
while(leadingZeros-- > 0) {
sb.append("0");
}
sb.append(blockStr);
}
String binaryIP = sb.toString();
if(!ruleTrie.startsWith(binaryIP)) {
res.add(ip);
}
}
}
class TrieNode {
char c;
boolean isLeaf;
TrieNode[] children;
public TrieNode() {
children = new TrieNode[2];
isLeaf = false;
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String s) {
if(s == null || s.length() == 0) {
return;
}
TrieNode cur = root;
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int index = c - '0';
if(cur.children[index] == null) {
cur.children[index] = new TrieNode();
}
cur.children[index].c = c;
cur = cur.children[index];
}
cur.isLeaf = true;
}
public boolean startsWith(String s) {
TrieNode cur = root;
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int index = c - '0';
if(cur.isLeaf == true) {
return true;
}
if(cur.children[index] == null) {
return false;
}
cur = cur.children[index];
}
return cur.isLeaf;
}
}
public static void main(String[] args) {
IPFilter sample = new IPFilter();
List<String> rules = new ArrayList<String>(Arrays.asList("7.7.7.7/8","123.2.67.3/8"));
List<String> IPs = new ArrayList<String>(Arrays.asList("23.2.4.1","7.3.4.1","5.1.2.3","123.2.67.3"));
List<String> res = sample.filter(rules, IPs);
System.out.println(res);
}