题解 | #字典树的实现#

两数最大异或值

http://www.nowcoder.com/practice/2db2a8c399ef415cbb8e92ba1032f131

利用Trie树,存储每一位的值进行对比

  class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型
     */
    int son[300010][2],idx=0;
    void insert(int x)
    {
        int p=0;
        for(int i=30;i>=0;i--)
        {
            int u = x>>i&1;
            if(son[p][u]==0)
            {
                son[p][u]=++idx;
            }
            p=son[p][u];
        }
    }
    int query(int x)
    {
        int p=0,res=0;
        for(int i=30;i>=0;i--)
        {
            int u = x>>i&1;
            if(son[p][!u])
            {
                res+=1<<i;
                p=son[p][!u];
            }
            else
            {
                p=son[p][u];
            }
        }
        return res;
    }
    int maxXOR(vector<int>& array) {
        // write code here
        int ans=0;
        for(int num:array)
        {
            insert(num);
        }
        for(int num:array)
        {
            ans=max(ans,query(num));
        }
        return ans;
        
    }
};
全部评论

相关推荐

小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 18:35
简历上把1个月实习写成了3个月,会进行背调吗?
码农索隆:一个月有一个月的实习经历,三个月有三个月的实习经历
简历当中有水分算不算造假...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务