C++怎么解决单独的数字问题


这篇文章主要介绍“C++怎么解决单独的数字问题”,在 香港云主机日常操作中,相信很多人在C++怎么解决单独的数字问题问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C++怎么解决单独的数字问题”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!Example 1:Input: [2,2,3,2]
Output: 3Example 2:Input: [0,1,0,1,0,1,99]
Output: 99这道题是之前那道 Single Number的延伸,那道题的解法就比较独特,是利用计算机按位储存数字的特性来做的,这道题就是除了一个单独的数字之外,数组中其他的数字都出现了三次,还是要利用位操作 Bit Manipulation 来解。可以建立一个 32 位的数字,来统计每一位上1出现的个数,如果某一位上为1的话,那么如果该整数出现了三次,对3取余为0,这样把每个数的对应位都加起来对3取余,最终剩下来的那个数就是单独的数字。代码如下:解法一:还有一种解法,思路很相似,用3个整数来表示 INT 的各位的出现次数情况,one 表示出现了1次,two 表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值。ones 代表第 ith位只出现一次的掩码变量twos 代表第 ith位只出现两次次的掩码变量threes 代表第 ith位只出现三次的掩码变量假设现在有一个数字1,更新 one 的方法就是 ‘亦或” 这个1,则 one 就变成了1,而 two 的更新方法是用上一个状态下的 one 去 ‘与” 上数字1,然后 ‘或” 上这个结果,这样假如之前 one 是1,那么此时 two 也会变成1,这 make sense,因为说明是当前位遇到两个1了;反之如果之前 one 是0,那么现在 two 也就是0。注意更新的顺序是先更新 two,再更新 one,不理解的话只要带个只有一个数字1的输入数组看一下就不难理解了。然后更新 three,如果此时 one 和 two 都是1了,由于先更新的 two,再更新的 one,two 为1,说明此时至少有两个数字1了,而此时 one 为1,说明了此时已经有了三个数字1,这块要仔细想清楚,因为 one 是要 ‘亦或” 一个1的,值能为1,说明之前 one 为0,实际情况是,当第二个1来的时候,two 先更新为1,此时 one 再更新为0,下面 three 就是0了,那么 ‘与” 上t hree 的相反数1不会改变 one 和 two 的值;那么当第三个1来的时候,two 还是1,此时 one 就更新为1了,那么 three 就更新为1了,此时就要清空 one 和 two 了,让它们 ‘与” 上 three 的相反数0即可,最终结果将会保存在 one 中,参见代码如下:解法二:下面这种解法思路也十分巧妙,根据上面解法的思路,我们把数组中数字的每一位累加起来对3取余,剩下的结果就是那个单独数组该位上的数字,由于累加的过程都要对3取余,那么每一位上累加的过程就是 0->1->2->0,换成二进制的表示为 00->01->10->00,可以写出对应关系:00 (+) 1 = 0101 (+) 1 = 1010 (+) 1 = 00 ( mod 3)用 ab 来表示开始的状态,对于加1操作后,得到的新状态的 ab 的算法如下:b = b xor r & ~a;a = a xor r & ~b;这里的 ab 就是上面的三种状态 00,01,10 的十位和各位,刚开始的时候,a和b都是0,当此时遇到数字1的时候,b更新为1,a更新为0,就是 01 的状态;再次遇到1的时候,b更新为0,a更新为1,就是 10 的状态;再次遇到1的时候,b更新为0,a更新为0,就是 00 的状态,相当于重置了;最后的结果保存在b中,明白了上面的分析过程,就能写出代码如下;解法三:到此,关于“C++怎么解决单独的数字问题”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注开发云网站,小编会继续努力为大家带来更多实用的文章!

相关推荐: Runtimebroker.exe进程占用CPU过高的解决方法

这篇文章主要为大家展示了“Runtimebroker.exe进程占用CPU过高的解决方法”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“Runtimebroker.exe进程占用CPU过高的解决方法”这篇文章吧。1.…

免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 07/14 16:22
下一篇 07/14 16:23

相关推荐