微软2016校园招聘4月在线笔试 B. 403 Forbidden 题解

Last Updated At: 2016-04-09

题目链接

初步解

顺序查找已经建立的规则,能够通过低级测试用例,对于规模较大的测试用例会出现超时。

#include<iostream>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include"stdlib.h"

void split(std::string& s, std::string delim,std::vector< std::string >* ret)
{
    size_t last = 0;
    size_t index = s.find_first_of(delim, last);
    while (index != std::string::npos) {
        ret->push_back(s.substr(last, index-last));
        last = index + 1;
        index=s.find_first_of(delim, last);
    }
    if (index-last > 0) {
        ret->push_back(s.substr(last, index - last));
    }
}

int main(void)
{
    int N, M;
    std::cin >> N >> M;
    std::vector<std::string> rules;
    std::vector<bool> rule_ctx;
    while(N--)
    {
        std::string rule;
        std::cin >> rule;

        std::string rule_text;
        std::cin >> rule_text;

        std::string bin_addr("");
        if(rule_text.find('/') == std::string::npos)
        {
            std::vector<std::string> rule_info;
            split(rule_text, ".", &rule_info);
            for(size_t i = 0; i < rule_info.size(); ++i)
            {
                bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string(                                                                  );
            }
        }
        else
        {
            std::vector<std::string> rule_meta_info;
            split(rule_text, "/", &rule_meta_info);
            std::vector<std::string> rule_info;
            split(rule_meta_info[0], ".", &rule_info);
            for(size_t i = 0; i < rule_info.size(); ++i)
            {
                bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string(                                                                  );
            }
            bin_addr = bin_addr.substr(0, atoi(rule_meta_info[1].c_str()));
        }
        rules.push_back(bin_addr);
        if(rule[0]=='a')
        {
            rule_ctx.push_back(true);
        }
        else
        {
            rule_ctx.push_back(false);
        }
    }
    while(M--)
    {
        bool is_match = false;
        std::string bin_addr("");
        std::string req;
        std::cin >> req;

        std::vector<std::string> rule_info;
        split(req, ".", &rule_info);

        for(size_t i = 0; i < rule_info.size(); ++i)
        {
            bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string();
        }

        for(size_t i = 0; i < rules.size(); ++i)
        {
            int len = rules[i].size();
            if (bin_addr.substr(0, len) == rules[i])
            {
                is_match = true;
                if(rule_ctx[i] == true)
                    std::cout << "YES" << std::endl;
                else
                    std::cout << "NO" << std::endl;
                break;
            }
        }
        if(!is_match)
            std::cout << "YES" << std::endl;
    }
    return 0;
}

优化解

既然顺序查找会超时,考虑使用树结构来进行查找。类似于字典树,编码为二进制形式的ip地址使用二叉树形式,左儿子为0,右儿子为1。

#include<iostream>
#include<climits>
#include<string>
#include<vector>
#include<bitset>
#include"stdlib.h"

typedef struct TreeNode *Node;

struct TreeNode
{
    int flag;
    Node Left;
    Node Right;
};

Node createNode(int flag)
{
    Node T = new TreeNode;
    T->Left = T->Right = NULL;
    T->flag = flag;
    return T;
}

void split(std::string& s, std::string delim,std::vector< std::string >* ret)
{
    size_t last = 0;
    size_t index = s.find_first_of(delim, last);
    while (index != std::string::npos) {
        ret->push_back(s.substr(last, index-last));
        last = index + 1;
        index=s.find_first_of(delim, last);
    }
    if (index-last > 0) {
        ret->push_back(s.substr(last, index - last));
    }
}

int main(void)
{
    int N, M;
    std::cin >> N >> M;
    Node rule_header = createNode(-1);
    std::vector<bool> rule_ctx;
    size_t rule_cnt = 0;
    bool default_rule = true;
    while(N--)
    {
        std::string rule;
        std::cin >> rule;

        std::string rule_text;
        std::cin >> rule_text;

        std::string bin_addr("");

        int mask = 0;
        if(rule_text.find('/') == std::string::npos)
        {
            std::vector<std::string> rule_info;
            split(rule_text, ".", &rule_info);
            for(size_t i = 0; i < rule_info.size(); ++i)
            {
                bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string();
            }
        }
        else
        {
            std::vector<std::string> rule_meta_info;
            split(rule_text, "/", &rule_meta_info);
            std::vector<std::string> rule_info;
            split(rule_meta_info[0], ".", &rule_info);
            for(size_t i = 0; i < rule_info.size(); ++i)
            {
                bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string();
            }
            bin_addr = bin_addr.substr(0, atoi(rule_meta_info[1].c_str()));
            if(atoi(rule_meta_info[1].c_str()) == 0)
                default_rule = false;
            else
                mask = atoi(rule_meta_info[1].c_str());
        }
        Node rule_node = rule_header;
        int level_cnt = 0;
        for(size_t i = 0; i < bin_addr.size(); ++i)
        {
            if(bin_addr[i] == '0')
            {
                if(rule_node->Left == NULL)
                {
                    rule_node->Left = createNode(-1);
                }
                rule_node = rule_node->Left;
            }
            else
            {
                if(rule_node->Right == NULL)
                {
                    rule_node->Right = createNode(-1);
                }
                rule_node = rule_node->Right;
            }
            if((mask > 0) && (++level_cnt == mask))
                break;
        }
        if(rule_node->flag == -1)
            rule_node->flag = rule_cnt;
        if(rule[0]=='a')
        {
            rule_ctx.push_back(true);
        }
        else
        {
            rule_ctx.push_back(false);
        }
        rule_cnt++;
    }
    while(M--)
    {
        size_t first_match = INT_MAX;
        std::string bin_addr("");
        std::string req;
        std::cin >> req;

        std::vector<std::string> rule_info;
        split(req, ".", &rule_info);

        for(size_t i = 0; i < rule_info.size(); ++i)
        {
            bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string();
        }

        Node search = rule_header;
        for(size_t i = 0; i < bin_addr.size(); ++i)
        {
            if (bin_addr[i] == '0')
            {
                if (search->Left == NULL)
                    break;
                if (search->Left->flag != -1)
                    first_match = search->Left->flag < first_match ? search->Left->flag:first_match;
                search = search->Left;
            }
            else
            {
                if (search->Right == NULL)
                    break;
                if (search->Right->flag != -1)
                    first_match = search->Right->flag < first_match ? search->Right->flag:first_match;
                search = search->Right;
            }
        }

        if(first_match == INT_MAX)
            std::cout << (default_rule ? "YES":"NO") << std::endl;
        else
            std::cout << (rule_ctx[first_match] ? "YES":"NO") << std::endl;
    }
    return 0;
}