[leetcode刷题笔记]数学与位运算 - 简书
source link: https://www.jianshu.com/p/2bb5bd9a52b0?
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[leetcode刷题笔记]数学与位运算
位运算是二进制中比较常见的运算，包括按位与&，按位或｜，非～，异或∧ 等，本文记录LeetCode刷题一些知识点，水平有限还望多多指正
1.只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
根据异或运算的三个特点：
- 1.交换律：
- 2.任何数于0异或为任何数:
- 3.相同的数异或为0:
若输入，则
即为所求
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for i in nums:
res^=i
return res
2.只出现一次的数字II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
在上一题中，除了某元素外其他元素均出现两次，消除规则为0 -> 1 -> 0，因此使用一个二进制位即可。在本题中其他数字出现三次，需要两个二进制位完成 00 -> 01 -> 10 -> 00。如何使某位在0与1之间转换，可以根据以下公式。
设b,a代表两个二进制位，当出现3次是，其他元素归零，最后仅剩b,a = 0,1，即a此时位元素值。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
a, b = 0, 0
for num in nums:
a = a ^ num & ~b
b = b ^ num & ~a
return a
3.只出现一次的数字III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
首先通过异或运算能够求出这两个数字的异或，可以用
作为标记来分离
和
。
如何求数字,考虑异或结果的某个非 0 位如最后一个非 0 位, 因为我们知道只有当
、
在该位不一样的时候才会出现异或结果为 1,我们通过
保留
最右边的 1，这个 1 要么来自
，要么来自
,所以我们以该位是否为 1 对数组进行划分, 只要该位为 1 就和 x 异或, 只要该位为 0就和 y异或, 这样最终得到就是只出现过一次的两个数。
下面清楚的说明的作用，因为
，故：
class Solution:
def singleNumber(self, nums: List[int]) -> int:
diff, x,y = 0,0,0
for i in nums:
diff ^=i
diff&=(~ diff+1)
for i in nums:
if diff&i==0:
x ^=i
else:
y ^=i
return x,y
4.缺失数字
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
若输入,其中i为下标，num为数值，将其异或运算，该题就变成了数组中只有一个数字出现一次，如表
| i | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| num | 0 | 1 | 3 | 4 |
可以将结果的初始值设为n，再对数组中的每一个数以及它的下标进行一个异或运算，即：
即为所求
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res = len(nums)
for i,num in enumerate(nums):
res ^= i^num
return res
5.消失的两个数字
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
将问题转换为nums数组的所有数和1~N的数一同构成的集合特征为——该集合内只有2个数字出现过1次，而其余数字都出现2次，请找出这2个只出现1次的数字。
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
diff, x,y = 0,0,0
N = len(nums) + 2
for i in range(1, N+1):
diff ^= i
for i in nums:
diff ^= i
diff&=~ diff
for i in nums:
if i & diff:
x ^= i
else:
y ^= i
for i in range(1, N+1):
if i & diff:
x ^= i
else:
y ^= i
return [x, y]
6.不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
∧异或 ----相当于 无进位的求和， 想象10进制下的模拟情况：（如:19+1=20；无进位求和就是10，而非20；因为它不管进位情况）
& 与 ----相当于求每位的进位数， 先看定义：；
；
；即都为1的时候才为1，正好可以模拟进位数的情况,还是想象10进制下模拟情况：（9+1=10，如果是用&的思路来处理，则9+1得到的进位数为1，而不是10，所以要用<<1向左再移动一位，这样就变为10了）；
这样公式就是： 即：每次无进位求 + 每次得到的进位数--------我们需要不断重复这个过程，直到进位数为0为止；
class Solution:
def add(self, a: int, b: int) -> int:
while b:
a, b = (a ^ b) & 0xFFFFFFFF, ((a & b) << 1) & 0xFFFFFFFF
return a if a <= 0x7FFFFFFF else ~ a ^ 0xFFFFFFFF
[注]为什么要加 0xFFFFFFFF,在leetcode解析上,作者jyd给出了如下解释。
由于 Python 的数字存储特点，需要做一些特殊处理，以下详细介绍。
Python 负数的存储：
Python / Java 中的数字都是以 补码 形式存储的。但 Python 没有 int , long 等不同长度变量，即没有变量位数的概念。
获取负数的补码： 需要将数字与十六进制数 0xffffffff 相与。可理解为舍去此数字 32 位以上的数字，从无限长度变为一个 32位整数。
返回前数字还原： 若补码 a 为负数（0x7fffffff 是最大的正数的补码 ），需执行~(a ^ x)操作，将补码还原至 Python 的存储格式。a ^ x运算将 1至 32 位按位取反； ~ 运算是将整个数字取反；因此，~(a ^ x) 是将 32 位以上的位取反，即由 0 变为 1， 1 至 32 位不变。
print(hex(1)) # = 0x1 补码
print(hex(-1)) # = -0x1 负号 + 原码 （ Python 特色，Java 会直接输出补码）
print(hex(1 & 0xffffffff)) # = 0x1 正数补码
print(hex(-1 & 0xffffffff)) # = 0xffffffff 负数补码
print(-1 & 0xffffffff) # = 4294967295 （ Python 将其认为正数）
7.数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
ret=0
for num in nums:
ret ^= num
div = 1
while div & ret == 0:
div <<= 1
a, b = 0, 0
for num in nums:
if num & div:
a ^= num
else:
b ^= num
return [a, b]
8.3的幂
给定一个整数，写一个函数来判断它是否是 3 的幂次方。你能不使用循环或者递归来完成本题吗？
使用log,若n为3的幂次方，则为整数，根据换底公式
判断是否为整数只需判断i%1是否为0即可
class Solution:
def isPowerOfThree(self, n: int) -> bool:
from math import log10
if n <= 0:
return False
return (log10(n)/log10(3))%1 == 0
再次注意，由于精度问题，在此使用log10()而非log()。
9.2的幂
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
可以使用上题求对数，也可根据二进制的性质，若n为2的幂，则
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n < 1:
return False
return n&(n-1) == 0
题目和部分解析来源力扣（LeetCode）,更多内容后续补充，欢迎指正。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK