Trie树/字典树题目(2017今日头条笔试题:异或)

  1 /*
  2 本程序说明:
  3 
  4 [编程题] 异或
  5 时间限制:1秒
  6 空间限制:32768K
  7 给定整数m以及n个数字A1,A2,..An,将数列A中所有元素两两异或,共能得到n(n-1)/2个结果,请求出这些结果中大于m的有多少个。
  8 输入描述:
  9 第一行包含两个整数n,m.
 10 
 11 第二行给出n个整数A1,A2,...,An。
 12 
 13 数据范围
 14 
 15 对于30%的数据,1 <= n, m <= 1000
 16 
 17 对于100%的数据,1 <= n, m, Ai <= 10^5
 18 
 19 
 20 输出描述:
 21 输出仅包括一行,即所求的答案
 22 
 23 输入例子1:
 24 3 10
 25 6 5 10
 26 
 27 输出例子1:
 28 2
 29 
 30 
 31 链接:https://www.nowcoder.com/questionTerminal/fc05f68c5f47438db54c6923ef23cf4a
 32 来源:牛客网
 33 
 34 /*
 35 C++
 36 思路来源:牛客网“潇潇古月”,在此表示感谢。
 37 思路:
 38     直接计算肯定是超时的,所以这问题不能使用暴力破解,考虑到从高位到地位,依次进行位运算,
 39     如果两个数异或结果在某高位为1,而m的对应位为0,则肯定任何这两位异或结果为1的都会比m大。
 40     由此,考虑使用字典树(TrieTree)从高位到第位建立字典,再使用每个元素依次去字典中查对应
 41     高位异或为1, 而m为0的数的个数,相加在除以2既是最终的结果;直接贴出代码如下,非原创,欢迎讨论;
 42     补充:queryTrieTree在搜索的过程中,是从高位往低位搜索,那么,如果有一个数与字典中的数异或结果
 43     的第k位大于m的第k位,那么该数与对应分支中所有的数异或结果都会大于m, 否则,就要搜索在第k位异或
 44     相等的情况下,更低位的异或结果。queryTrieTree中四个分支的作用分别如下:
 45     1. aDigit=1, mDigit=1时,字典中第k位为0,异或结果为1,需要继续搜索更低位,第k位为1,异或结果为0,小于mDigit,不用理会;
 46     2. aDigit=0, mDigit=1时,字典中第k位为1,异或结果为1,需要继续搜索更低位,第k位为0,异或结果为0,小于mDigit,不用理会;
 47     3. aDigit=1, mDigit=0时,字典中第k位为0,异或结果为1,与对应分支所有数异或,结果都会大于m,第k位为1,异或结果为0,递归获得结果;
 48     4. aDigit=0, mDigit=0时,字典中第k位为1,异或结果为1,与对应分支所有数异或,结果都会大于m,第k位为0,异或结果为0,递归获得结果;
 49 
 50 改进:
 51     1.字典树17位即可保证大于100000,移位范围为1~16位,则字典树构建时从16~0即可。
 52        字典树第一层不占位,实际上是15~-1层有数据,这也是数据中next的用法。
 53     2.queryTrieTree函数需要考虑到index为-1时的返回值。
 54 
 55 时间复杂度:O(n);
 56 空间复杂度O(k),k为常数(trie树的高度),因此可以认为O(1)。
 57  */
 58 #include <iostream>
 59 #include <vector>
 60 using namespace std;
 61 
 62 struct TrieTree
 63 {
 64     int count;//每个节点存的次数
 65     struct TrieTree* next[2]{NULL,NULL};//每个节点存储两个节点指针
 66     TrieTree():count(1){}
 67 };
 68 
 69 TrieTree* buildTrieTree(const vector<int>& array)
 70 {
 71     TrieTree* trieTree = new TrieTree();
 72     for(int i=0;i<(int)array.size();++i)
 73     {
 74         TrieTree* cur = trieTree;
 75         for(int j=16;j>=0;--j)
 76         {
 77             int digit = (array[i] >> j) & 1;
 78             if(NULL == cur->next[digit])
 79                 cur->next[digit] = new TrieTree();
 80             else
 81                 ++(cur->next[digit]->count);
 82             cur = cur->next[digit];
 83         }
 84     }
 85     return trieTree;
 86 }
 87 
 88 //查询字典树
 89 long long queryTrieTree(TrieTree*& trieTree, const int a, const int m, const int index)
 90 {
 91     if(NULL == trieTree)
 92         return 0;
 93 
 94     TrieTree* cur = trieTree;
 95 
 96     for(int i=index;i>=0;--i)
 97     {
 98         int aDigit = (a >> i) & 1;
 99         int mDigit = (m >> i) & 1;
100 
101         if(1==aDigit && 1==mDigit)
102         {
103             if(NULL == cur->next[0])
104                 return 0;
105             cur = cur->next[0];
106         }
107         else if(0 == aDigit && 1==mDigit)
108         {
109             if(NULL == cur->next[1])
110                 return 0;
111             cur = cur->next[1];
112         }
113         else if(1 == aDigit && 0 == mDigit)
114         {
115             long long val0 =  (NULL == cur->next[0]) ? 0 : cur->next[0]->count;
116             long long val1 =  queryTrieTree(cur->next[1],a,m,i-1);
117             return val0+val1;
118         }
119         else if(0 == aDigit && 0 == mDigit)
120         {
121             long long val0 =  queryTrieTree(cur->next[0],a,m,i-1);
122             long long val1 =  (NULL == cur->next[1]) ? 0 : cur->next[1]->count;
123             return val0+val1;
124         }
125     }
126     return 0;//此时index==-1,这种情况肯定返回0(其他情况在循环体中都考虑到了)
127 }
128 
129 //结果可能超过了int范围,因此用long long
130 long long solve(const vector<int>& array, const int& m)
131 {
132     TrieTree* trieTree = buildTrieTree(array);
133     long long result = 0;
134     for(int i=0;i<(int)array.size();++i)
135     {
136         result += queryTrieTree(trieTree,array[i],m,16);
137     }
138     return result /2;
139 }
140 
141 int main()
142 {
143     int n,m;
144     while(cin>>n>>m)
145     {
146         vector<int> array(n);
147         for(int i=0;i<n;++i)
148             cin>>array[i];
149         cout<< solve(array,m) <<endl;
150     }
151     return 0;
152 }

关于trie数的其他应用,可参见http://www.cnblogs.com/dlutxm/archive/2011/10/26/2225660.html,感觉写的不错。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏运维技术迷

MySQL数据库(三):数据类型

安装环境: 操作系统版本:RHEL 6.5 版本:MYSQL 5.5 常见的信息种类: 数值型:一般用于体重、身高、成绩、工资 字符型:一般用于...

39350
来自专栏desperate633

第14课 组合查询创建组合查询union的使用规则

组合查询很容易理解就是讲多个查询的结果放在一起显示 使用UNION关键字进行查询的组合

9220
来自专栏测试开发架构之路

总结了一些指针易出错的常见问题(五)

指针与链表及其操作 //结构体定义 typedef struct _person{ char* firstname; char* lastna...

29150
来自专栏JavaQ

温故而知新-MySQL数据类型

选择数据类型的原则 MySQL支持多种数据类型,选择合适的数据类型存储数据对MySQL存储引擎来说至关重要,下面的一些原则可以在选择数据类型的时候做出更合适的选...

32070
来自专栏Clive的技术分享

PHP实现单例模式

<?php /** * 单例模式实现 */ class Singleton { //静态变量保存全局实例 private static $ins...

34070
来自专栏跟着阿笨一起玩NET

sql server 获取每一个类别中值最大的一条数据

SELECT  * FROM    (           SELECT    * ,                     ROW_NUMBER() OVE...

47510
来自专栏Laoqi's Linux运维专列

SQLAlchemy总结+

41330
来自专栏CodingToDie

MySql Hash 索引

Hash 索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 ...

34530
来自专栏Python爱好者

判断是否为小米MIUI系统

203120
来自专栏Python

Django中Q查询及Q()对象

问题 一般我们在Django程序中查询数据库操作都是在QuerySet里进行进行,例如下面代码: >>> q1 = Entry.objects.filter(h...

31450

扫码关注云+社区

领取腾讯云代金券