今天是小浩算法“365刷题计划”第62天。仍然分享一道关于位运算颇为简单的题型&＃xff0c;同时&＃xff0c;从明天开始将会提高难度&＃xff0c;大家做好准备。
01
PART
Single Number
这道题&＃xff0c;大家先想一想是用什么思路进行求解&＃xff1f;
第136题&＃xff1a;给定一个非空整数数组&＃xff0c;除了某个元素只出现一次以外&＃xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。
&＃xff08;瞪一瞪就全部掌握&＃xff09;
PS&＃xff1a;建议大家停留个两分钟先想一想...直接拉下去看题解就没什么意思了。
02
PART
题目分析
位运算的题目我们已经讲了好几道了&＃xff0c;这道也不例外&＃xff0c;也是其中一个非常典型的例子&＃xff01;属于必须掌握的题型。
直接分析&＃xff0c;我们要找只出现一次的数字&＃xff0c;并且已知了其他的数字都只出现了两次。那么这种一听其实就应该想到需使用位运算来进行求解。最好的&＃xff0c;就是在读完题目的瞬间&＃xff0c;直接条件反射&＃xff01;&＃xff08;当然&＃xff0c;如果你现在第一反应是想到 通过遍历统计&＃xff0c;或者其他如使用hashmap 等方式来进行求解&＃xff0c;那我觉得你的位运算这块&＃xff0c;是有必要加强练习力度的。如果你第一反应&＃xff0c;连思路都没有&＃xff0c;那我觉得对于整个算法的能力这块&＃xff0c;都是比较欠缺的&＃xff0c;需要下苦功&＃xff01;&＃xff09;
回到题目&＃xff0c;如何使用位运算进行求解呢&＃xff1f;对于任意两个数a和b&＃xff0c;我们对其使用 “异或”操作&＃xff0c;应该有以下性质&＃xff1a;
任意一个数和0异或仍然为自己&＃xff1a;
a⊕0&＃61;a
任意一个数和自己异或是0&＃xff1a;
a⊕a&＃61;0
异或操作满足交换律和结合律&＃xff1a;
a⊕b⊕a&＃61;(a⊕a)⊕b&＃61;0⊕b&＃61;b
可能有人直接都不知道异或是什么&＃xff0c;所以还是举个例子&＃xff0c;比如5异或3&＃xff0c;也就是5⊕3&＃xff0c;也就是5^3&＃xff0c;是下面这样&＃xff1a;
根据分析&＃xff0c;得出代码&＃xff1a;&＃xff08;c&＃43;&＃43;版本&＃xff09;
1//CPP2class Solution {3public:4 int singleNumber(vector& nums) {5 int ans &＃61; 0;6 for (int num : nums) {7 ans ^&＃61; num;8 }9 return ans;
10 }
11};
&＃xff08;java版本&＃xff09;
1//JAVA2class Solution {3 public int singleNumber(int[] nums) {4 int ans &＃61; nums[0];5 for (int i &＃61; 1; i < nums.length; i&＃43;&＃43;) {6 ans &＃61; ans ^ nums[i];7 }8 return ans;9 }
10}
(python版本)
1//py
2class Solution:
3 def singleNumber(self, nums: List[int]) -> int:
4 ans &＃61; 0
5 for i in range(len(nums)):
6 ans ^&＃61; nums[i]
7 return ans
郑重申明&＃xff08;读我的文章必看&＃xff09;&＃xff1a;
03
PART
题目进阶
如果修改上面的题目&＃xff0c;除了某个元素只出现一次&＃xff0c;其余元素都出现了3次以上&＃xff0c;那么该如何求解&＃xff1f;
修改一个条件之后&＃xff0c;本题的难度大幅度提升&＃xff01;“异或”的方式看起来似乎没办法运用在“其余数出现3次以上”的条件中。那对于这种问题又该如何求解&＃xff1f;我这里给出几种思路&＃xff0c;大家下去分析一下&＃xff0c;明天我会公布这道衍化题型的解决方案&＃xff1a;
思路1&＃xff1a;使用hashmap&＃xff0c;统计每个数字出现的次数&＃xff0c;最后返回次数为1的数字。。。然后等待一段时间&＃xff0c;接到很遗憾的通知。
思路2&＃xff1a;上面的题目&＃xff0c;对于相同的两个数&＃xff0c;进行异或运算&＃xff0c;我们可以进行“抵消”&＃xff0c;那是否可以找到一种方式&＃xff0c;来让相同的三个数进行相互抵消呢&＃xff1f;
思路3&＃xff1a;是不是可以通过数学的方式来进行计算&＃xff1f;
&＃xff08;这货就是不直接说出来&＃xff0c;你说气人不气人&＃xff01;&＃xff09;
想复习一下其他位运算题目的&＃xff0c;可以看&＃xff1a;
漫画&＃xff1a;三分钟学习一道位运算的面试题&＃xff0c;万一遇到了呢&＃xff1f;
漫画&＃xff1a;位运算技巧助你俘获offer
所以&＃xff0c;今天的问题你学会了吗&＃xff1f;评论区留下你的想法&＃xff01;
1. 全栈架构之打包推荐【建议收藏&＃xff0c;常读】
2. 一个空格引发的“惨案“
3. 分布式系统中Session共享的常用方案
4. Java语言“坑爹”排行榜TOP 10
5. 我是一个Java类&＃xff08;附带精彩吐槽&＃xff09;
6. mysql索引失效&＃xff0c;差点我的工作凉了
7. 既生synchronized&＃xff0c;何生volatile&＃xff1f;
8. 微服务一直火&＃xff0c;为什么服务化要搞懂&＃xff1f;
9. MySQL的COUNT语句&＃xff0c;不简单&＃xff01;
10. 漫画&＃xff1a;HashSet和TreeSet实现与原理
扫码二维码关注我
·end·
—如果本文有帮助&＃xff0c;请分享到朋友圈吧—
我们一起愉快的玩耍&＃xff01;
你点的每个赞&＃xff0c;我都认真当成了喜欢
京公网安备 11010802041100号