先举道简单的题:
有一些筷子,长短不一,长度一样的能组成一双。现在刚好有一堆筷子,数量为奇数,而且刚好只有一只筷子落单,其余都成双。
请找出这只落单的筷子的长度。
在acm的书看到有类似的题目,是用位运算解的,挺巧妙的。
有几种办法:
- 先排序,再扫描一次。如果扫描到长度相同的连续一段个数为奇数,则输出解。例如1,1,2,2,2,3。。。 2出现的次数为3,奇数,输出2,可以停了。O(NlogN) (用于排序)
- 筷子长度的范围比较小的话,可以开个数组。a[i] 记录长度为i的筷子出现的次数,累加后,a[i]=a[i]%2, 最后扫描一遍,找出a[i]为一的那个下标i。O(N)
而书里提供了一个巧妙的办法,对每个长度x,求ans ^=x
^是xor,异或运算,可以理解成 对x中的位为1的取反。比如数字 1111 1111(2) 如果想翻转后面四位,可以这样 1111 1111 ^ 0000 1111=1111 0000
好了,现在只要一双筷子出现xor两次之后,位翻转就抵消掉了,所以~ans最后保存出现一次的筷子长度.
今天群里有人发了另外一道题
是易总状态里的一道题目,状态回复写程序会格式错乱,于是发篇日志贴一下程序。
题目如下:一个全是32位整数的大数组,除了其中一个数字出现2次外,其余的数字都出现了3次。如何找出那个只出现了两次的数字?
这道题我以前看过,那个版本是其中一个数字出现1次,不过都是一样的,不影响算法。当时看到解答的程序感觉非常惊艳,为其简洁与精妙赞叹了许久,以下为程序部分:
其中ones记录了所有出现了(模3余1)次的bit,twos记录的是余2的。not_threes是当一个bit出现第3次的时候,把它清掉。
我首先想到的也是位运算。不过这道题出现次数改了,处理起来会麻烦点,但思路还是一样的。
要点:
1. 一个数字每出现3次,我们就要把它消掉。拓展一下,我们只要对每个位置的1每出现3次就消掉。(数据保证其他数字出现3次,所以才能这么做)
比如:
100
101
100
第一位(左起)的1出现3次,第二位0次,第三位1次。消掉后为001
2. x%3 可以为0,1,2。上面的步骤去掉了0的情况,所以我们还要保存1,2的情况。
然后我们回过头来理解那个程序
先看 ones ^= x,如果循环里面只有这一句的话,ones求的就是取反1次,3次,5次。。。,因为每满3次要清掉,所以循环就变成1,1,1。。了。
而这一块就是每满3就清除的代码。注意这一块 ( ones & twos ),ones求的是余1,twos求的是余2,原本交集是空的,但这里ones还没过滤3的情况,而开头 twos |= ones & x 求的其实是之前2(现在可能变3了)或者本轮确定为2的情况。所以 ( ones & twos )取到3的情况(即ones的3和twos变成3的部分)
瞎了。。这个程序真TM难啊。。。
附:我自己调试的代码
分享到:
相关推荐
注意这一块 ( ones & twos ),ones求的是余1,twos求的是余2,原本交集是空的,但这里ones还没过滤3的情况,而开头 twos |= on
58巧解相同元素的排列问题[归类].pdf
c# 链环 问题 巧解结构和函数的应用 (2,3)与(3,2)类似的环节的个数并输出
3.巧解数学运算七大方法.rar
用数学模型巧解排列组合问题.doc
如何运用十字交叉法巧解数学运算题参照.pdf
用运动图象巧解直线运动问题测试[精选].doc
2018年秋八年级数学上册第十四章整式的乘法与因式分解小专题五运用幂的运算法则巧解计算题试题新版新人教版20180823144
巧解cpu温度过高问题.docx
四年级奥数巧解追及问题教案.doc
巧解XP升Win8磁盘问题.docx
公务员考试行测:巧解青蛙跳井问题.pdf
导数结合洛必达法则巧解恒成立问题.doc
齐次平移巧解一类圆锥曲线问题.pdf
利用题目本身的归整性,穷举可能出现的元素配比 操作流程:输入一定量信息(质量,元素种类,式量),信息越全面增根越少 如:m=6.66,M=?,Na=0.06,Fe=?,O=? 推出NaFeO2以及一些其它组合,再根据相关常识筛选出最有可能的...
用份数法巧解应用题.doc
化学计算题巧解十法及混合物中各元素质量分数计算技巧.pdf
2018高中物理第七章机械能守恒定律7.8动能定理巧解变力做功问题练习新人教版必修220180820267
熟用质量守恒 巧解化学计算.pdf
奥林匹克竞赛千题巧解·初中一年级数学