文档章节

hdoj_2095_Find your present (2) (位异或)

電泡泡
 電泡泡
发布于 2013/10/11 17:09
字数 391
阅读 14
收藏 0

题意:

给你n个数字,已知只有一个数字出现了奇数次,其他数字都出现了偶数次,要求你找出这个特别的数字。

解题思路:

题目内存限制:1024K,所以不能简单地用数组存然后再处理。

为了节约内存,可以用STL里面的set,map等容器。

当容器里没有这个元素的时候,就插入这个元素,否则,删除这个元素。

最后,容器中肯定只剩下一个元素,便是我们所要的结果。

[cpp]  view plain copy
  1. #include <set>  
  2. #include <stdio.h>  
  3. using namespace std;  
  4. int main()  
  5. {  
  6.     int n,x;  
  7.     set <int> S;  
  8.     while(scanf("%d",&n),n)  
  9.     {  
  10.         while(n--)  
  11.         {  
  12.             scanf("%d",&x);  
  13.             if(S.find(x) == S.end())    //没找到,插入  
  14.                 S.insert(x);  
  15.             else                        //找到了,删除  
  16.                 S.erase(x);  
  17.         }  
  18.         printf("%d\n",*S.begin());  
  19.         S.clear();  
  20.     }  
  21.     return 0;  
  22. }  

其实,这题还有个更好的方法————位异或。

我们先了解一下位异或的运算法则吧:

1、a^b = b^a。

2、(a^b)^c = a^(b^c)。

3、a^b^a = b。

对于一个任意一个数n,它有几个特殊的性质:

1、0^n = n。

2、n^n = 0。

所以可以通过每次异或运算,最后剩下的值就是出现奇数次的那个数字。

[cpp]  view plain copy
  1. #include <stdio.h>  
  2. int main()  
  3. {  
  4.     int n,x,ans;  
  5.     while(scanf("%d",&n),n)  
  6.     {  
  7.         ans = 0;  
  8.         while(n--)  
  9.         {  
  10.             scanf("%d",&x);  
  11.             ans ^= x;  
  12.         }  
  13.         printf("%d\n",ans);  
  14.     }  
  15.     return 0;  
  16. }  
PS:话说通过位运算的这些性质,可以通过不借用中间变量实现a,b的值的交换。
[cpp]  view plain copy
  1. void swap(int &a,int &b)  
  2. {  
  3.     a ^= b;  
  4.     b ^= a;  
  5.     a ^= b;  
  6. }  

本文转载自:http://blog.csdn.net/dgq8211/article/details/7455722

共有 人打赏支持
下一篇: begin
電泡泡
粉丝 24
博文 183
码字总数 69717
作品 0
衡阳
私信 提问
hdoj题目分类

基础题: 1000、1001、1004、1005、1008、1012、1013、1014、1017、1019、1021、1028、1029、1032、1037、1040、1048、1056、1058、1061、1070、1076、1089、1090、1091、1092、1093、1094、...

小代码2016
2016/02/04
93
0
java中的位运算

位运算表达式由操作数和位运算符组成,实现对整数类型的二进制数进行位运算。位运算符可以分为逻辑运算符(包括~、&、|和^)及移位运算符(包括>>、<<和>>>)。 1)左移位运算符(<<)能将运算符...

tsmyk0715
2016/08/04
41
0
使用valgrind检查cache命中率

Valgrind为一个debugging 和 profiling的工具包,检查内存问题只是其最知名的一个用途。今天介绍一下,valgrind工具包中的cachegrind。关于cachegrind的具体介绍,请参见valgrind的在线文档h...

有些服务器
2015/10/01
342
0
位运算小结

位操作基础 位运算符 Java还有一个无符号右移运算符>>>,强行右移,左侧补零。以及还有相应的复合运算符。 位操作只能用于整形数据,对 float 和 double 类型进行位操作会被编译器报错。 注意...

有苦向瓜诉说
2017/11/19
0
0
使用valgrind检查cache命中率,提高程序性能

作者:gfree.wind@gmail.com 博客:blog.focus-linux.net linuxfocus.blog.chinaunix.net 本文的copyleft归gfree.wind@gmail.com所有,使用GPL发布,可以自由拷贝,转载。但转载请保持文档的...

nothingfinal
01/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

80后阿里P10,“关老板”如何带着MaxCompute一路升级?

我是个幸运的人。虽然幸运不能被复制,但是眼光和努力可以。 关涛/关老板,80后的阿里P10,阿里巴巴通用计算平台负责人,阿里巴巴计算平台研究员。12年职场人生,微软和阿里的选择。 关涛的花...

阿里云官方博客
17分钟前
0
0
开源软件和开源模式面临的生存危机

开源模式可能正面临一场危机。越来越多的开源软件和平台被大型云计算服务商融入自家的云服务体系,并以此获利颇丰,但并不支付费用,也没有对开源社区做出相应的回馈。而实际上,大部分开源软...

Linux就该这么学
17分钟前
0
0
统一服务消息返回错误:{"errcode":40165,"errmsg":"invalid weapp pagepath hint: [bsAWua0201ge30]"}

{"errcode":40165,"errmsg":"invalid weapp pagepath hint: [bsAWua0201ge30]"} 原因:pagepath参数为所需跳转到小程序的具体页面路径,支持带参数,(示例index?foo=bar), 以前配置的是:m...

tianma3798
19分钟前
0
0
ElasticSearch实战:Linux日志对接Kibana

本文由云+社区发表 ElasticSearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于RESTFul web接口。ElasticSearch是用Java开发的,并作为Apache许可条款下...

腾讯云加社区
22分钟前
0
0
FeignClient超时配置

1前沿 使用Feign调用接口分两层,ribbon的调用和hystrix的调用,所以ribbon的超时时间和Hystrix的超时时间的结合就是Feign的超时时间 1.1ribbon配置 ribbon: OkToRetryOnAllOperations: f...

lovelan1314
25分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部