class Solution:
def getSum(self, a: int, b: int) -> int:
# 位运算
MAX = 0x7fffffff
MIN = 0x80000000
mask = 0xFFFFFFFF
while b != 0:
a, b = (a ^ b) & mask, ((a & b) << 1)
return a if a <= MAX else ~(a ^ mask)
class Solution:
def isPerfectSquare(self, num: int) -> bool:
return num**0.5 == int(num**0.5)
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
inter = set(nums1) & set(nums2)
l = []
for i in inter:
l += [i] * min(nums1.count(i), nums2.count(i))
return l
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))
class Solution:
def reverseVowels(self, s: str) -> str:
word = 'aeiouAEIOU'
filter_word = [i for i in s if i in word]
ret = list(s)
for idx, val in enumerate(ret):
if val in word:
ret[idx] = filter_word.pop()
return ''.join(ret)
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
#删除插入
#for i in range(len(s)):
# now = s[0]
# del s[0]
# s.insert(len(s)-i, now)
#双指针
i, j = 0, len(s)-1
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
class Solution:
def isPowerOfFour(self, num: int) -> bool:
while num and not (num & 0b11):
num >>= 2
return (num == 1)
class Solution:
def isPowerOfThree(self, n: int) -> bool:
res = 1
while res < n:
res *= 3
return res == n
class NumArray:
def __init__(self, nums: List[int]):
self.nums = nums
for i in range(len(self.nums)):
if i > 0:
self.nums[i] = self.nums[i]+self.nums[i-1]
def sumRange(self, i: int, j: int) -> int:
if i>0:
return self.nums[j]-self.nums[i-1]
else:
return self.nums[j]
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)
class Solution:
def getHint(self, secret: str, guess: str) -> str:
c1=Counter(secret)
c2=Counter(guess)
B=sum([min(c1[x],c2[x]) for x in c1 if x in c2])
A=0
for i in range(len(secret)):
if int(secret[i])-int(guess[i])==0:
B-=1
A+=1
return str(A)+"A"+str(B)+"B"
class Solution:
def canWinNim(self, n: int) -> bool:
return n % 4 != 0
class Solution:
def wordPattern(self, pattern: str, str: str) -> bool:
# 分别构建pattern->str和str->pattern的哈希映射表; 2.仅当key值不在字典时对字典做添加; 3.然后根据映射表规则生成新的pattern和str,并且和原来的比较,当且仅当两者都为True时,结果才为True.
str1 = str.split(" ")
dic_a=dict()
dic_b=dict()
if len(pattern)!=len(str1):
return(False)
else:
for i in range (len(str1)):
if str1[i] not in dic_a:
dic_a[str1[i]]=pattern[i]
if pattern[i] not in dic_b:
dic_b[pattern[i]]=str1[i]
print(dic_a,dic_b)
return("".join([dic_a[i]for i in str1]) == pattern and "".join([dic_b[i]for i in pattern]) == str.replace(" ","") )
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
for i in range(nums.count(0)):
nums.remove(0)
nums.append(0)
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
l, r = 0, n
while(l < r):
mid = l + (r - l) // 2
if isBadVersion(mid + 1) == True:
r = mid
else:
l = mid + 1
if l == n:
return(-1)
else:
return(l + 1)
class Solution:
def missingNumber(self, nums: List[int]) -> int:
# 前N项和
return len(nums) * (len(nums) + 1) // 2 - sum((nums))
class Solution:
def isUgly(self, num: int) -> bool:
for p in 2, 3, 5:
while num % p == 0 < num:
num //= p
return num == 1
class Solution:
def addDigits(self, num: int) -> int:
if num > 9:
num = num % 9
if num == 0:
return 9
return num
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if not root:
return []
if not root.left and not root.right:
return [str(root.val)]
paths = []
if root.left:
for i in self.binaryTreePaths(root.left):
paths.append(str(root.val) + '->' + i)
if root.right:
for i in self.binaryTreePaths(root.right):
paths.append(str(root.val) + '->' + i)
return paths
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# python3 利用二叉搜索树的特点,如果p、q的值都小于root,说明p q 肯定在root的左子树中;如果p q都大于root,说明肯定在root的右子树中,如果一个在左一个在右 则说明此时的root记为对应的最近公共祖先 //python3
if p.val<root.val and q.val<root.val:
return self.lowestCommonAncestor(root.left,p,q)
if p.val>root.val and q.val>root.val:
return self.lowestCommonAncestor(root.right,p,q)
return root
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
s1=0
s2=0
t=1
while head!=None:
s1=s1*10+head.val
s2=s2+t*head.val
t=t*10
head=head.next
return s1==s2
class MyQueue(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.instack = []
self.outstack = []
def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: None
"""
self.instack.append(x)
def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
if len(self.outstack) == 0:
while self.instack:
self.outstack.append(self.instack.pop())
return self.outstack.pop()
def peek(self):
"""
Get the front element.
:rtype: int
"""
if len(self.outstack) == 0:
while self.instack:
self.outstack.append(self.instack.pop())
return self.outstack[-1]
def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return len(self.instack) == 0 and len(self.outstack) == 0
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and not (n & (n - 1))
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
root.left,root.right=self.invertTree(root.right),self.invertTree(root.left)
return root