class Solution: def bitwiseComplement(self, N: int) -> int: if N==0: return 1 cur=1 rep=0 while N>0: if N&1==1: cur*=2 N>>=1 else: rep+=cur cur*=2 N>>=1 return rep
Category Archives: leetcode
1010. Pairs of Songs With Total Durations Divisible by 60
class Solution: def numPairsDivisibleBy60(self, time: List[int]) -> int: dict_t={} for t in time: if t%60 not in dict_t: dict_t[t%60]=1 else: dict_t[t%60]+=1 cnt=0 if 0 in dict_t and dict_t[0]>1: cnt+=dict_t[0]*(dict_t[0]-1)//2 if 30 in dict_t and dict_t[30]>1: cnt+=dict_t[30]*(dict_t[30]-1)//2 for i in range(1,30): if i in dict_t and 60-i in dict_t: cnt+=dict_t[i]*dict_t[60-i] return cnt
1013. Partition Array Into Three Parts With Equal Sum
class Solution: def canThreePartsEqualSum(self, A: List[int]) -> bool: A_sum=sum(A) if A_sum%3!=0: return False target=A_sum//3 cur=0 for i in range(len(A)): cur+=A[i] if cur==target: if self.canTwoPartsEqualSum(A[i+1:],target): return True return False def canTwoPartsEqualSum(self,A,target): cur=0 for i in range(len(A)): cur+=A[i] if cur==target: return True return False
1018. Binary Prefix Divisible By 5
class Solution: def prefixesDivBy5(self, A: List[int]) -> List[bool]: rep=[] cur=0 for num in A: cur=cur*2+int(num) if cur%5==0: rep.append(True) else: rep.append(False) return rep
1021. Remove Outermost Parentheses
class Solution: def removeOuterParentheses(self, S: str) -> str: flag=0 rep=”” k=0 while k<len(S): if flag==0: flag+=1 k+=1 elif flag==1 and S[k]==”)”: flag-=1 k+=1 elif S[k]==”(“: rep+=S[k] flag+=1 k+=1 elif S[k]==”)”: rep+=S[k] flag-=1 k+=1 return rep
1025. Divisor Game
class Solution: def divisorGame(self, N: int) -> bool: if N==1: return False if N==2: return True dp=[False,True] for i in range(3,N+1): flag=False for k in range(1,i): if i%k==0 and dp[-k]==False: dp.append(True) flag=True break if flag==False: dp.append(False) return dp[-1]
1038. Binary Search Tree to Greater Sum Tree
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def bstToGst(self, root: TreeNode) -> TreeNode: if not root: return if root.right: self.bstToGst(root.right) cur=root.right while cur.left: cur=cur.left root.val+=cur.val if root.left: cur=root.left while cur.right: cur=cur.right cur.val+=root.val self.bstToGst(root.left) returnContinueContinue reading “1038. Binary Search Tree to Greater Sum Tree”
1051. Height Checker
class Solution: def heightChecker(self, heights: List[int]) -> int: tmp=sorted(heights) rep=0 for k in range(len(heights)): if heights[k]!=tmp[k]: rep+=1 return rep
1089. Duplicate Zeros
class Solution: def duplicateZeros(self, arr: List[int]) -> None: “”” Do not return anything, modify arr in-place instead. “”” r=len(arr) cur=0 l=0 while cur<r: if arr[l]!=0: cur+=1 elif arr[l]==0: cur+=2 if cur>=r: break l+=1 if cur>r: arr[r-1]=0 r-=1 l-=1 r-=1 while l>=0: if arr[l]!=0: arr[r]=arr[l] r-=1 l-=1 else: arr[r]=0 arr[r-1]=0 r-=2 l-=1
1108. Defanging an IP Address
class Solution: def defangIPaddr(self, address: str) -> str: cur=address.split(‘.’) rep=”” for str in cur: rep+=”[.]”+str return rep[3:]