文章目录
  1. 1. 题意
  2. 2. 思路
    1. 2.1. 数据结构
    2. 2.2. 建树
    3. 2.3. 匹配

题意

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;
}

完整代码

文章目录
  1. 1. 题意
  2. 2. 思路
    1. 2.1. 数据结构
    2. 2.2. 建树
    3. 2.3. 匹配