神刀安全网

Hiho 1289 403 Forbidden(微软编程题)

allow 1.2.3.4/30 deny 1.1.1.1 allow 127.0.0.1 allow 123.234.12.23/3 deny 0.0.0.0/0 

输入 ip 按顺序匹配规则,优先匹配前面的规则,如果没有规则可以匹配则视为合法。注意:掩码为 0 的时候表示匹配所有 ip。

思路

一开始做的时候用遍历匹配的方法,直接超时了。后来才想到用字典树的方法来做,这道题本质上是一道字典树变形。

数据结构

class Node {         byte flag;//0代表普通节点,1代表允许规则终点,2代表禁止规则终点         int seq;//规则顺序         Node[] next = new Node[2];          Node(byte flag){             this.flag = flag;     } } 

建树

  1. seq 自增,记录规则的顺序
  2. 解析掩码:如果输入的 ip 没有 mask,则默认 mask = 32
  3. 把ip地址转化为二进制形式
  4. 插入节点:如果该节点不存在,则新建;否则沿着节点往下走
  5. 设置节点的 flag 和 seq:后面的规则不能覆盖前面的规则,所以要查看当前节点是否为某规则的终点。

代码如下:

public void insert(String ip, byte flag) {     seq++;     int mask = 32;     int index = ip.indexOf('/');     //检测是否有掩码     if (index != -1) {         mask = Integer.parseInt(ip.substring(index + 1));     } else {         index = ip.length();     }      //把ip地址转化为二进制形式     String binary = toBinary(ip.substring(0, index));      char[] binarys = binary.toCharArray();      Node node = root;      for (int i = 0; i < mask; i++) {         int pos = binarys[i] - '0';         if (node.next[pos] == null){             node.next[pos] = new Node((byte) 0);         }         node = node.next[pos];     }     //后面的规则不能覆盖前面的     if (node.flag == 0){         node.flag = flag;     }     if (node.seq == 0) {         node.seq = seq;     } } 

匹配

  1. 把ip地址转化为二进制形式
  2. 遍历字典树
  3. 如果当前节点为规则的终点,则需要比较该规则的顺序,seq 小的优先匹配
  4. 遍历完字典树之后,isAllow 的值就是该 ip 最先匹配到的规则所规定的权限

代码如下:

public boolean isAllow(String ip){     String binary = toBinary(ip);     char[] binarys = binary.toCharArray();      Node node = root;     int seq = Integer.MAX_VALUE;     boolean isAllow = true;     int i = 0;     int pos = 0;     while (node != null){         //字典树最多会有33个节点,而ip的二进制最多只有32位         //另一种避免判断的方法是在ip的二进制后面补一个0         if (i < binarys.length){             pos = binarys[i] - '0';         }         if (node.flag == 1){             if (node.seq < seq){                 isAllow = true;                 seq = node.seq;             }         } else if (node.flag == 2){             if (node.seq < seq){                 isAllow = false;                 seq = node.seq;             }         } else {             //flag=0说明是普通节点,直接跳过即可。         }         node = node.next[pos];         i++;     }     return isAllow; } 

完整代码

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Hiho 1289 403 Forbidden(微软编程题)

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮