如何在建设厅网站投诉,枣阳网站建设吧,宁夏网站建设推广,火车头自动发布wordpress标签我这里总结了几道位运算的题目分享给大家#xff0c;分别是 136 和 137#xff0c; 260 和 645#xff0c; 总共加起来四道题。 四道题全部都是位运算的套路#xff0c;如果你想练习位运算的话#xff0c;不要错过哦#xff5e;#xff5e;
前菜
开始之前我们先了解下…我这里总结了几道位运算的题目分享给大家分别是 136 和 137 260 和 645 总共加起来四道题。 四道题全部都是位运算的套路如果你想练习位运算的话不要错过哦
前菜
开始之前我们先了解下异或后面会用到。
异或的性质 两个数字异或的结果a^b是将 a 和 b 的二进制每一位进行运算得出的数字。 运算的逻辑是果同一位的数字相同则为 0不同则为 1。
异或的规律
任何数和本身异或则为0任何数和 0 异或是本身异或运算满足交换律即a ^ b ^ c a ^ c ^ b
OK我们来看下这三道题吧。
136. 只出现一次的数字 1
题目大意是除了一个数字出现一次其他都出现了两次让我们找到出现一次的数。我们执行一次全员异或即可。
class Solution:def singleNumber(self, nums: List[int]) - int:single_number 0for num in nums:single_number ^ numreturn single_number复杂度分析 时间复杂度 O ( N ) O(N) O(N)其中 N 为数组长度。 空间复杂度 O ( 1 ) O(1) O(1)
137. 只出现一次的数字 2
题目大意是除了一个数字出现一次其他都出现了三次让我们找到出现一次的数。 灵活运用位运算是本题的关键。
Python3:
class Solution:def singleNumber(self, nums: List[int]) - int:res 0for i in range(32):cnt 0 # 记录当前 bit 有多少个1**加粗样式** bit 1 i # 记录当前要操作的 bitfor num in nums:if num bit ! 0:cnt 1if cnt % 3 ! 0:# 不等于0说明唯一出现的数字在这个 bit 上是1res | bitreturn res - 2 ** 32 if res 2 ** 31 - 1 else res为什么 Python 最后需要对返回值进行判断
如果不这么做的话测试用例是[-2,-2,1,1,-3,1,-3,-3,-4,-2] 的时候就会输出 4294967292。 其原因在于 Python 是动态类型语言在这种情况下其会将符号位置的 1 看成了值而不是当作符号“负数”。 这是不对的。 正确答案应该是 - 4-4 的二进制码是 1111…100就变成 2^32-44294967292解决办法就是 减去 2 ** 32 。 之所以这样不会有问题的原因还在于题目限定的数组范围不会超过 2 ** 32 JavaScript:
var singleNumber function (nums) {let res 0;for (let i 0; i 32; i) {let cnt 0;let bit 1 i;for (let j 0; j nums.length; j) {if (nums[j] bit) cnt;}if (cnt % 3 ! 0) res res | bit;}return res;
};复杂度分析 时间复杂度 O ( N ) O(N) O(N)其中 N 为数组长度。 空间复杂度 O ( 1 ) O(1) O(1)
上述感觉这种方法他没说清楚特此补充完整
方法二依次确定每一个二进制位
思路与算法 细节 代码
class Solution {public int singleNumber(int[] nums) {int ans 0;for (int i 0; i 32; i) {int total 0;for (int num: nums) {total ((num i) 1);}if (total % 3 ! 0) {ans | (1 i);}}return ans;}
}作者LeetCode-Solution
链接https://leetcode.cn/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetc-23t6/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。645. 错误的集合
和上面的137. 只出现一次的数字2思路一样。这题没有限制空间复杂度因此直接 hashmap 存储一下没问题。 不多说了我们来看一种空间复杂度 O ( 1 ) O(1) O(1)的解法。
由于和137. 只出现一次的数字2思路基本一样我直接复用了代码。具体思路是将 nums 的所有索引提取出一个数组 idx那么由 idx 和 nums 组成的数组构成 singleNumbers 的输入其输出是唯二不同的两个数。
但是我们不知道哪个是缺失的哪个是重复的因此我们需要重新进行一次遍历判断出哪个是缺失的哪个是重复的。
class Solution:def singleNumbers(self, nums: List[int]) - List[int]:ret 0 # 所有数字异或的结果a 0b 0for n in nums:ret ^ n# 找到第一位不是0的h 1while(ret h 0):h 1for n in nums:# 根据该位是否为0将其分为两组if (h n 0):a ^ nelse:b ^ nreturn [a, b]def findErrorNums(self, nums: List[int]) - List[int]:nums [0] numsidx []for i in range(len(nums)):idx.append(i)a, b self.singleNumbers(nums idx)for num in nums:if a num:return [a, b]return [b, a]复杂度分析 时间复杂度 O ( N ) O(N) O(N) 空间复杂度 O ( 1 ) O(1) O(1)
260. 只出现一次的数字 3
题目大意是除了两个数字出现一次其他都出现了两次让我们找到这个两个数。
我们进行一次全员异或操作得到的结果就是那两个只出现一次的不同的数字的异或结果。
我们刚才讲了异或的规律中有一个任何数和本身异或则为0 因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。 分组需要满足两个条件.
两个独特的的数字分成不同组相同的数字分成相同组
这样每一组的数据进行异或即可得到那两个数字。
问题的关键点是我们怎么进行分组呢
由于异或的性质是同一位相同则为 0不同则为 1. 我们将所有数字异或的结果一定不是 0也就是说至少有一位是 1.
我们随便取一个 分组的依据就来了 就是你取的那一位是 0 分成 1 组那一位是 1 的分成一组。 这样肯定能保证2. 相同的数字分成相同组, 不同的数字会被分成不同组么。 很明显当然可以 因此我们选择是 1也就是 说两个独特的的数字在那一位一定是不同的因此两个独特元素一定会被分成不同组。
class Solution:def singleNumbers(self, nums: List[int]) - List[int]:ret 0 # 所有数字异或的结果a 0b 0for n in nums:ret ^ n# 找到第一位不是0的h 1while(ret h 0):h 1for n in nums:# 根据该位是否为0将其分为两组if (h n 0):a ^ nelse:b ^ nreturn [a, b]复杂度分析 时间复杂度 O ( N ) O(N) O(N)其中 N 为数组长度。 空间复杂度 O ( 1 ) O(1) O(1) 方法二位运算
思路与算法 代码
class Solution {public int[] singleNumber(int[] nums) {int xorsum 0;for (int num : nums) {xorsum ^ num;}// 防止溢出int lsb (xorsum Integer.MIN_VALUE ? xorsum : xorsum (-xorsum));int type1 0, type2 0;for (int num : nums) {if ((num lsb) ! 0) {type1 ^ num;} else {type2 ^ num;}}return new int[]{type1, type2};}
}作者LeetCode-Solution
链接https://leetcode.cn/problems/single-number-iii/solution/zhi-chu-xian-yi-ci-de-shu-zi-iii-by-leet-4i8e/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
