Leetcode题解（11）- 2018 力扣 Leetcode CN 高频题汇总 part 7 数学&位运算
# 先简单补充下python的二进制操作
print 0b101 # 用 0b 开头表示二进制
bin(5) # 把十进制转换成二进制
# 位操作
>> #右移
<< #左移
| #位或
& #位与
^ #位异或
~ #非
2
3
4
5
6
7
8
9
# 只出现一次的数字
Leetcode 136题，已经做过了，参见Leetcode 题解 4 (opens new window)
这个题是说数组中只有一个只出现一次的数字，其他数字均出现两次，所以只要所有数字一直做xor操作，最后得到的就是只出现一次的数字了。
而剑指offer中有个题参见这里 (opens new window)，是有两个数字只出现一次，其他数字出现了偶数次。
# 直线上最多的点数
Leetcode 149题
# 问题
给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
示例
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
2
3
4
5
6
7
8
9
10
11
# 思路及代码
这个题好像挺无聊？？基本是暴力做了，需要注意处理（1）有完全重复的点的情况 （2）不能用除法做斜率（比如会存在垂直的线，无穷大斜率），转换成乘法来做。
class Solution:
def maxPoints(self, points):
n = len(points)
if n <= 2:
return n
max_ = 0
for i in range(n):
same = 1 # 计数重复点。先把点i算作1
for j in range(i+1,n):
cnt = 0
if points[j] == points[i]:
same += 1 # 重复点
else:
cnt += 1 # 计算在线上的点，先把点j算作1
dist_x = points[j][0] - points[i][0]
dist_y = points[j][1] - points[i][1]
# 检查是否有其他点在 ij 这条线上
for s in range(j+1, n):
dx = points[s][0] - points[i][0]
dy = points[s][1] - points[i][1]
if dist_x * dy == dist_y * dx:
cnt += 1
max_ = max(max_, cnt + same)
return max_
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 分数到小数
Leetcode 166 题
# 问题
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。
如果小数部分为循环小数，则将循环的部分括在括号内。
输入: numerator = 2, denominator = 1
输出: "2"
输入: numerator = 2, denominator = 3
输出: "0.(6)"
2
3
4
5
# 思路
直接相除然后转str就好了，所以关键是判断无限循环小数的情况。
例如 1/6， 首先补0变成 10/6， 商1余4， 再补0变成 40/6， 商6余4， 再补0变成 40/6…………当出现重复的余数时，说明出现了循环。
# 代码
class Solution(object):
def fractionToDecimal(self, numerator, denominator):
"""
难点在于如何判断是否是循环小数，以及找出循环节的位置
判断是循环: 跳出while循环的时候余数为0就不是循环小数
找出循环节的位置: 当同一个余数出现两次时，就找到了循环节
:type numerator: int
:type denominator: int
:rtype: str
"""
sign = '-' if numerator * denominator < 0 else ''
numerator, denominator = abs(numerator), abs(denominator)
m, n = divmod(numerator, denominator) # x//y,x%y
int_part = str(m)
if not n:
return sign + str(m)
decimal_part = []
dic = {} # 键:余数 值:出现余数的索引
i = 0
# 模拟除法,当余数为0或者余数在字典中有记录的时候跳出循环
while n and n not in dic:
dic[n] = i
i += 1
m, n = divmod(n * 10, denominator)
decimal_part.append(str(m))
if not n: # 不是循环小数
res = sign + int_part + '.' + ''.join(decimal_part)
else:
# 在循环节之前插入(
decimal_part.insert(dic[n], '(')
decimal_part.append(')')
res = sign + int_part + '.' + ''.join(decimal_part)
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 阶乘后的零
Leetcode 172题，之前做过啦，参考这里 (opens new window)，这个题代码非常简单，重点在分析。
# 颠倒二进制位
Leetcode 190 题
# 问题
颠倒给定的 32 位无符号整数的二进制位。（也就是反转）
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
2
# 思路
二进制移位，取出最低位，加入res中，n右移，res左移
# 代码
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
res = 0
count = 32
while count:
res <<= 1
# 取出 n 的最低位数加到 res 中
res += n&1
n >>= 1
count -= 1
return int(bin(res), 2)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 位1的个数
Leetcode 191 题
# 问题
返回二进制中1的个数（也被称为汉明重量）
（插句题外话，汉明距离：两个数二进制位有多少不相同，也就是先xor之后的结果的汉明重量）
# 思路
1）数字n与 1 做按位与，可以得到数字n的最低位数字，判断是否为1。然后把n右移一位，依次类推，直到n为0.
2）通过十进制来处理，每次对数字 % 2， 判断余数是否为1，是的话就++，直到n为0
3）通过 str(bin(n)) 把数字转换成二进制再转换成字符串，统计字符1的个数
# 代码
按1来写：
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
ans = 0
while n:
ans += n & 1
n >>= 1
return ans
2
3
4
5
6
7
8
9
10
11
# 计数质数
Leetcode 204题
# 问题
统计所有小于非负整数n的质数的数量。例如n=10，小于10的质数一共有 2，3，5，7 这四个。
# 思路
1）基础方法 外层从1到n，内层循环从2到sqrt(i)逐个判断i能否被比它小的数整除，如果都不能，则说明是质数。
为何从2判断到sqrt(i)就可以，而非判断到i呢。是因为一个数如果是合数，必然是由两数相乘，这两个数肯定有一个要小于或者等于sqrt(i)，不然的话如果都大于，乘积就比i大了。所以只要判断到sqrt(i)就行。
2）厄拉多塞筛法
介绍：该算法在寻找素数时，采用了一种与众不同的方法：先将 2－N 的各数放入表中，然后在 2 的上面画一个圆圈，然后划去 2 的其他倍数；第一个既未画圈又没有被划去的数是 3，将它画圈，再划去 3 的其他倍数；现在既未画圈又没有被划去的第一个数是 5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。
这时，表中画了圈的以及未划去的那些数正好就是小于 N 的素数。
# 代码
按照2来写的代码，有两个优化点：下面的【1】处，无需从2到n，只要到 sqrt(i) 就好了，【2】处是从 i*i 开始的，而非从i+i开始。 当然这两处也可以不优化，多跑一些循环。
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n < 3:
return 0
output = [1] * n
output[0], output[1] = 0, 0
for i in range(2, int(n**0.5)+1): #【1】
if output[i] == 1:
output[i*i:n:i] = [0] * len(output[i*i:n:i]) # 【2】
return sum(output)
2
3
4
5
6
7
8
9
10
11
12
13
14
# 缺失数字
Leetcode 268题
# 问题
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例
输入: [3,0,1]
输出: 2
2
3
能否使用线性时间复杂度、常数空间来实现
# 思路
1） 一种思路是， 0-n的序列我们可以通过公式 n(n+1)//2 直接算出和，这样的话只要从头到尾累加一遍，两个和相减，就能得到缺失的那个数了！
不过会遇到的问题是，万一数字很大，求和会溢出。
2） 一种思路是，由于数字是0到n，下标也可以处理成0到n（给定了n个数，所以下标是0到n-1，我们手动补一个n，这样数字和下标就能一一对应了），所以我们可以不单纯累加数字，而是累加 i - nums[i] ，这样的话，最终得到的就是缺失的那个数字，由于有加有减，也不容易溢出。
3） 另一种思路是利用二进制xor操作，也就是说在for循环中，xor i，xor nums[i]，其实类似于加减操作，数值和它的下标相互抵消，最后余下的就是缺失的数字，因为它没有和它的下标相互抵消。
这样说起来，下标和数字相互抵消，这个问题不就转换成了，数组中只出现一次的数字吗！只有缺失那个数字只出现了一次 ，其他数字都出现了两次。
# 代码
按2来做：
class Solution(object):
def missingNumber(self, nums):
s = 0
for i, n in enumerate(nums):
s += i - n
s += len(nums)
return s
2
3
4
5
6
7
按3来做：
class Solution(object):
def missingNumber(self, nums):
s = len(nums)
for i, n in enumerate(nums):
s ^= n
s ^= i
return s
2
3
4
5
6
7
# 3的幂
Leetcode 326题
# 问题
给定整数，判断它是否是3的幂
能否不使用循环或者递归
# 思路
累乘或者累除的方法是常规做法，但是需要用到递归或者循环。
一种做法是，因为整数范围内的3的幂次最大是 1162261467，所以用 1162261467 对 n 求模，如果等于0，说明 n 是 3 的幂。
还有做法是，把数字转换成3进制，判断是否第一位为1，其他位为0，符合条件则是3的幂。这就好比十进制里面，10的幂是 10， 100， 1000， 10000， 二进制里面二的幂是 10， 100， 1000 。三进制同理。
# 代码
class Solution(object):
def isPowerOfThree(self, n):
return n > 0 and 1162261467 % n == 0
2
3