201. Bitwise AND of Numbers Range
看答案才想到，其实是找到共同前缀
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
cnt=0
while left!=right:
left>>=1
right>>=1
cnt+=1
return left<<cnt
231. Power of Two
之前背过，经典位运算
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n==0:return False
return not n&(n-1)
136. Single Number
简单到无聊
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res=set()
for i in nums:
if i in res:
res.remove(i)
else:
res.add(i)
return list(res)[0]
137. Single Number II
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return (sum(set(nums))*3 - sum(nums))//2
260. Single Number III
作弊：
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
res=set()
for num in nums:
if num in res:
res.remove(num)
else:
res.add(num)
return list(res)
正经解法：
- 假设答案是 a, b
- 所有数据做异或，得到结果n
- n的某位数为1，那么a, b 在这个位上必然不一样。按这个位，把所有的数分为两类
- a和b必然分别在两个类中，每个类中单独异或得到结果。
解法如下：
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xorsum = type1 = type2 = 0
for num in nums:
xorsum ^= num
lsb = xorsum & (-xorsum)
for num in nums:
if num & lsb:
type1 ^= num
else:
type2 ^= num
return [type1, type2]
268. Missing Number
这个题就利用 n^n=0 的特点
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res=0
for num in nums:
res^=num
for i in range(len(nums)+1):
res^=i
return res
338. Counting Bits
- 解法1:
i&(i-1)的效果是去掉最后一个1， - 解法2:
i>>1的效果是去掉最后一位，不过需要判断最后1位是1还是0
# 解法1
res=[0]*(n+1)
for i in range(1,n+1):
res[i]=res[i&(i-1)]+1
# 解法2
res=[0]*(n+1)
for i in range(1,n+1):
res[i]=res[i>>1]+(i&1)
342. Power of Four
- 2**n 判断标准是 n&(n-1)==0
- 4次方这个靠移位
class Solution:
def isPowerOfFour(self, n: int) -> bool:
if n&(n-1):return False
while n:
if n==1:
return True
n>>=2
return False
389. Find the Difference
!!!参考“求多出来的n个数字”那个题
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
res = 0
for i in t:
res += ord(i)
for i in s:
res -= ord(i)
return chr(res)
287. Find the Duplicate Number
我又作弊了
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
nums.sort()
for i in range(len(nums)-1):
if nums[i]==nums[i+1]:
return nums[i]
hash 也算作弊
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
nums_set=set()
for num in nums:
if num in nums_set:
return num
else:
nums_set.add(num)
318. Maximum Product of Word Lengths
思路：
- 位运算，把1个词映射到1个长度位26的二进制上
x&y==0表示两者没有重复
class Solution:
def __init__(self):
self.masks = {"a": 1,
"b": 2,
"c": 4,
"d": 8,
"e": 16,
"f": 32,
"g": 64,
"h": 128,
"i": 256,
"j": 512,
"k": 1024,
"l": 2048,
"m": 4096,
"n": 8192,
"o": 16384,
"p": 32768,
"q": 65536,
"r": 131072,
"s": 262144,
"t": 524288,
"u": 1048576,
"v": 2097152,
"w": 4194304,
"x": 8388608,
"y": 16777216,
"z": 33554432}
def maxProduct(self, words) -> int:
for idx, word in enumerate(words):
val_word = 0
len_word = len(word)
for char in word:
val_word |= self.masks[char]
words[idx] = (val_word, len_word)
res = 0
for i in range(1, len(words)):
for j in range(i):
if words[i][0] & words[j][0] == 0:
res = max(res, words[i][1] * words[j][1])
return res
405. Convert a Number to Hexadecimal
负号也要照顾到
class Solution:
def toHex(self, num: int) -> str:
if num==0:
return '0'
hex_char="0123456789abcdef"
res=""
while num and len(res)<8:
res=hex_char[num&0xf]+res
num>>=4
return res
421. Maximum XOR of Two Numbers in an Array
这个题用 Trie
class TrieNode:
def __init__(self):
self.children = dict()
self.is_word = False
class Solution:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_word = True
def insert_words(self, words):
for word in words:
self.insert(word)
def findMaximumXOR(self, nums):
nums = [bin(i)[2:] for i in nums]
max_len = max(len(i) for i in nums)
nums = ['0' * (max_len - len(i)) + i for i in nums]
self.insert_words(nums)
res = [0]
def dfs(node, idx, res_num, num):
if node.is_word:
res[0] = max(res[0], int(res_num, base=2))
return
if num[idx] == '0':
choose = '1'
else: # num[idx]=='1'
choose = '0'
if choose in node.children:
dfs(node.children[choose], idx + 1, res_num + '1', num)
else:
dfs(node.children[num[idx]], idx + 1, res_num + '0', num)
for num in nums:
dfs(self.root, 0, '', num)
return res[0]
476. Number Complement
int(''.join(['0' if i == '1' else '1' for i in bin(num)[2:]]), base=2)
645. Set Mismatch
distinct_sum_nums=sum(set(nums))
return [sum(nums)-distinct_sum_nums,
sum(range(1,len(nums)+1))-distinct_sum_nums]
693. Binary Number with Alternating Bits
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
if n&3==1: #01/01/01
while n:
if n&3!=1:
return False
else:
n>>=2
return True
elif n&3==2: #10/10/10
while n:
if n&3!=2:
return False
else:
n>>=2
return True
return False
更优秀的方法：
- 010101 右移一位得到 001010
- 二者异或之后得到011111 (这一步是关键,只有交替出现01，异或后才能得到结果0111111…11)
- 为了判断 异或后的结果是否满足(0111111…11)类型的结果 可以用如下方法
- 011111 加上1 为100000
- 011111 与 100000按位相与 结果为000000 ， 也就是0;
477. Total Hamming Distance
O(N**2) 的算法肯定超时，想想有没有其它方法
- 第一想到的是 Trie，很多二进制方法与 Trie 有关
- 某一层有m个1和n个0，汉明距离和对应 mn
- 所以其实也不用 Trie 了
class Solution:
def totalHammingDistance(self, nums: List[int]) -> int:
res = 0
while True:
if not any(nums):
break
m = n = 0
for idx, num in enumerate(nums):
if num & 1:
m += 1
else:
n += 1
nums[idx] >>= 1
res += (m * n)
return res
491. Increasing Subsequences
思路：dfs
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
len_nums = len(nums)
res = set()
def dfs(idx, res_array):
if idx == len_nums:
if len(res_array) > 1:
res.add(tuple(res_array))
return
if len(res_array) > 0 and nums[idx] < res_array[-1]:
dfs(idx + 1, res_array)
else:
dfs(idx + 1, res_array + [nums[idx]])
dfs(idx + 1, res_array)
dfs(0, [])
return [list(i) for i in res]
473. Matchsticks to Square
思路：
- 相当于把一堆数平均分为4份
- dfs
- 但是超时，必须剪枝
- sum%4==0，否则肯定就不可能
- sum/4，如果超过这个值，就不用算下去了
- 把第一个数放到第一个桶里（否则会碰撞4倍）
- 从大到小排序，剪枝越早越好
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
matchsticks.sort(reverse=True)
res = [False]
sum_matchsticks = sum(matchsticks)
if sum_matchsticks % 4 != 0:
return False
edge = sum_matchsticks / 4
def dfs(idx, n1, n2, n3, n4):
if res[0]:
return
if idx == len(matchsticks):
if n1 == n2 == n3 == n4:
res[0] = True
return
if n1 + matchsticks[idx] <= edge:
dfs(idx + 1, n1 + matchsticks[idx], n2, n3, n4)
if n2 + matchsticks[idx] <= edge:
dfs(idx + 1, n1, n2 + matchsticks[idx], n3, n4)
if n3 + matchsticks[idx] <= edge:
dfs(idx + 1, n1, n2, n3 + matchsticks[idx], n4)
if n4 + matchsticks[idx] <= edge:
dfs(idx + 1, n1, n2, n3, n4 + matchsticks[idx])
dfs(1, matchsticks[0], 0, 0, 0)
return res[0]
526. Beautiful Arrangement
- 1,2,…n 肯定符合条件，cnt+1
-
1和任意位置换，也肯定符合条件，cnt+（n-1）
不用做了的
393. UTF-8 Validation
无聊的题，不用再做了
'''
0xxxxxxx i<=127
10xxxxxx 191>=i>=128
110xxxxx 192<=i<=223
1110xxxx 224<=i<=239
11110xxx 240<=i<=247
'''
class Solution:
def validUtf8(self, data) -> bool:
later_num = 0
for i in data:
if later_num == 0:
if 191 >= i > 127:
return False
elif i <= 127:
pass
elif 192 <= i <= 223:
later_num = 1
elif 224 <= i <= 239:
later_num = 2
elif 240 <= i <= 247:
later_num = 3
else:
return False
else:
if 191 >= i >= 128:
later_num -= 1
else:
return False
if later_num < 0:
return False
return later_num == 0
397. Integer Replacement
level order 超时
思路：
- 11 结尾，n+=1然后n»2
- 01 结尾，n-=1，然后 n»2
- 0 结尾，n»1
- 但是遇到3直接返回2，遇到1直接返回0
class Solution:
def integerReplacement(self, n: int) -> int:
cnt = 0
while True:
if n == 1:
return cnt
if n == 3:
return cnt + 2
tail = n & 3
if tail == 0:
n >>= 2
cnt += 2
elif tail == 1:
n -= 1
cnt += 1
elif tail == 2:
n >>= 1
cnt += 1
else:
n += 1
cnt += 1
return cnt
401. Binary Watch
class Solution:
def possible_hour(self, n):
if n < 0 or n >= 4:
return []
if n == 0:
return ['0']
if n == 1:
return ['1', '2', '4', '8']
if n == 2:
return ['10', '9', '6', '5', '3']
if n == 3:
return ['11', '7']
def possible_min(self, m):
possible_min_res = []
def dfs(vec, i, n):
if n == 0:
tmp = int(''.join(vec), base=2)
if 10 <= tmp < 60:
possible_min_res.append(str(tmp))
elif tmp < 10:
possible_min_res.append('0' + str(tmp))
return
if i >= 6:
return
vec[i] = '1'
dfs(vec, i + 1, n - 1)
vec[i] = '0'
dfs(vec, i + 1, n)
dfs(['0'] * 6, 0, m)
return possible_min_res
def readBinaryWatch(self, turnedOn: int):
res = []
for i in range(turnedOn + 1):
res.extend(
[hour + ':' + mins for hour in self.possible_hour(i) for mins in self.possible_min(turnedOn - i)])
return res
