```py# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defaddTwoNumbers(self,l1: ListNode,l2: ListNode) -> ListNode: c =0 res = []while(l1 or l2): s =0+ cif l1: s +=int(l1.val) l1 = l1.nextif l2: s +=int(l2.val) l2 = l2.nextprint(s) resa = s %10 res.append(resa) c = s //10if(c!=0): res.append(c) l3 =ListNode(0) head = l3for i inrange(0, len(res)): lt = res[i] l3.next =ListNode(lt) l3 = l3.nextreturn head.nextclass Solution:deffindContentChildren(self,g: List[int],s: List[int]) ->int: g =sorted(g) s =sorted(s) content =0while s and g:if s[-1]>= g[-1]: s.pop() content +=1 g.pop()return content# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:defconvertBST(self,root: TreeNode) -> TreeNode: self.ans =0defadd(node):ifnot node:returnadd(node.right) self.ans += node.val node.val = self.ansadd(node.left)add(root)return root## Recursive Solution# ------------------------------------------# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:definorderTraversal(self,root: TreeNode) -> List[int]: io = []if(root==None):return []definorder(x):if(x.left!=None):inorder(x.left) io.append(int(x.val))if(x.right!=None):inorder(x.right)inorder(root)return io# ------------------------------------------## Iterative Solution using Stack# ------------------------------------------# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:definorderTraversal(self,root: TreeNode) -> List[int]:if(root==None):return [] stack = [] io = [] c = rootwhile(c!=Noneorlen(stack)!=0):while(c!=None): stack.append(c) c = c.left c = stack.pop() io.append(c.val) c = c.rightreturn io# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = None# ------------------------------------------## Recursive SolutionclassSolution:defpostorderTraversal(self,root: TreeNode) -> List[int]:if (root==None):return [] po = []defpostorder(x):ifnot x:returnpostorder(x.left)postorder(x.right) po.append(x.val)postorder(root)return po# ------------------------------------------# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = None# ------------------------------------------## Recursive SolutionclassSolution: defpreorderTraversal(self,root: TreeNode) -> List[int]:if(root==None):return [] po = []defpreorder(x):if x: po.append(x.val)preorder(x.left)preorder(x.right)preorder(root)return po# ------------------------------------------## Iterative SolutionclassSolution: defpreorderTraversal(self,root: TreeNode) -> List[int]:if(root==None):return [] stack = [] po = [] c = rootwhile(c!=Noneorlen(stack)!=0):while(c!=None): stack.append(c) po.append(c.val) c = c.left c = stack.pop() c = c.rightreturn poclassSolution:defbackspaceCompare(self,S:str,T:str) ->bool:defdeleteBackSpace(X): stack = []for i in X:ifnot i=='#': stack.append(i)elif(len(stack)==0):continueelse: stack.pop()return stackreturndeleteBackSpace(S)==deleteBackSpace(T)# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:defbalanceBST(self,root: TreeNode) -> TreeNode: result = []definorder(node):if node:if node.left!=None:inorder(node.left) result.append(int(node.val))if node.right!=None:inorder(node.right)defconstructBalancedTree(arr):ifnot arr:returnNone mid =len(arr)//2 root =TreeNode(arr[mid]) root.left =constructBalancedTree(arr[:mid]) root.right =constructBalancedTree(arr[mid+1:])return rootinorder(root)# result = [int(x.val) for x in result]returnconstructBalancedTree(result)classSolution:defmaxProfit(self,prices: List[int]) ->int: profit =0for i inrange(0, len(prices)-1):if(prices[i+1]> prices[i]): profit += prices[i+1]- prices[i]return profitimport mathclassSolution:defrangeBitwiseAnd(self,m:int,n:int) ->int: ans = mifnot m==0: x = math.log2(m) x =int(x)+1 x =2**xelse:return0if(n>=x):return0for i inrange(m+1, n+1): ans = ans & i return ansfrom collections import CounterclassSolution:defcount(self,d1,d2): s =0for i in'abcdefghijklmnopqrstuvwxyz': s += d1[i]- d2[i]if s <0:returnFalsereturnTruedefcheckIfCanBreak(self,s1:str,s2:str) ->bool: d1 =Counter(s1) d2 =Counter(s2)return self.count(d1, d2)| self.count(d2, d1)class Solution:defmaxArea(self,height: List[int]) ->int: i =0 j =len(height)-1 maxarea =0while(i!=j): a = (j-i)*(min(height[i], height[j]))if(a>maxarea): maxarea = aif(height[i]>height[j]): j -=1else: i +=1return maxareaclass Solution:defcontainsDuplicate(self,nums: List[int]) ->bool:returnnotlen(nums)==len(set(nums))classSolution:deffindMaxLength(self,nums: List[int]) ->int: dic ={0:-1} ps =0 max_length =0for idx, number inenumerate(nums):if number: ps +=1else: ps -=1if ps in dic: max_length =max(max_length, idx-dic[ps])else: dic[ps]= idxreturn max_length# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:defcountNodes(self,root: TreeNode) ->int:ifnot root:return0 self.c =0defcount(node):if node:if node.left:count(node.left)if node.right:count(node.right) self.c +=1return self.ccount(root)return self.cclass Solution:defcountBits(self,num:int) -> List[int]: ans = [0] offset =1for i inrange(1, num+1):if(offset*2== i): offset = i ans.append(ans[i-offset]+1)return ansclass Solution:defcountElements(self,arr: List[int]) ->int: s =set() s =set(arr) c =0for i inrange(len(arr)):if(arr[i]+1in s): c +=1return cfrom collections import dequeclassSolution:defcanFinish(self,numCourses,prerequisites) ->bool: adjList = [[] for _ inrange(numCourses)] inDegree = [0for _ inrange(numCourses)] queue =deque() visited =0for i inrange(len(prerequisites)): adjList[prerequisites[i][0]].append(prerequisites[i][1])for i inrange(numCourses):for j in adjList[i]: inDegree[j]+=1for i inrange(len(inDegree)):if inDegree[i]==0: queue.append(i)while queue: el = queue.popleft()for i in adjList[el]: inDegree[i]-=1if inDegree[i]==0: queue.append(i) visited +=1if visited == numCourses:returnTrueelse:return Falseclass Solution:defminDeletionSize(self,A: List[str]) ->int: s =0for col inzip(*A):ifany(col[i] > col[i+1] for i inrange(len(col)-1)): s +=1return sclass Solution:defdeleteNode(self,root,key):ifnot root:returnif key > root.val: root.right = self.deleteNode(root.right, key)elif key < root.val: root.left = self.deleteNode(root.left, key)else:ifnot root.left:return root.rightelse: temp = root.leftwhile temp.right: temp = temp.right root.val = temp.val root.left = self.deleteNode(root.left, temp.val)return root# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defdeleteNode(self,node): node.val = node.next.val node.next = node.next.nextclass MyCircularDeque:def__init__(self,k:int):""" Initialize your data structure here. Set the size of the deque to be k. """ self.maxsize = k self.size =0 self.decq = [0]*k self.front = self.rear =-1definsertFront(self,value:int) ->bool:""" Adds an item at the front of Deque. Return true if the operation is successful. """if self.size == self.maxsize:returnFalseelse:if self.front ==-1: self.front = self.rear =0else: self.front = (self.front-1)%self.maxsize self.decq[self.front]= value self.size +=1returnTruedefinsertLast(self,value:int) ->bool:""" Adds an item at the rear of Deque. Return true if the operation is successful. """if self.size == self.maxsize:returnFalseelse:if self.rear ==-1: self.front = self.rear =0else: self.rear = (self.rear+1)%self.maxsize self.decq[self.rear]= value self.size +=1returnTruedefdeleteFront(self) ->bool:""" Deletes an item from the front of Deque. Return true if the operation is successful. """if self.size ==0:returnFalseelse:if self.front == self.rear: self.front = self.rear =-1else: self.decq[self.front]=0 self.front = (self.front+1)%self.maxsize self.size -=1returnTruedefdeleteLast(self) ->bool:""" Deletes an item from the rear of Deque. Return true if the operation is successful. """if self.size ==0:returnFalseelse:if self.front == self.rear: self.front = self.rear =-1else: self.decq[self.rear]=0 self.rear = (self.rear-1)%self.maxsize self.size -=1returnTruedefgetFront(self) ->int:""" Get the front item from the deque. """return self.decq[self.front]if self.size !=0else-1defgetRear(self) ->int:""" Get the last item from the deque. """return self.decq[self.rear]if self.size !=0else-1defisEmpty(self) ->bool:""" Checks whether the circular deque is empty or not. """return self.size ==0defisFull(self) ->bool:""" Checks whether the circular deque is full or not. """return self.size == self.maxsize# ------------------------------------------# Your MyCircularDeque object will be instantiated and called as such:# obj = MyCircularDeque(k)# param_1 = obj.insertFront(value)# param_2 = obj.insertLast(value)# param_3 = obj.deleteFront()# param_4 = obj.deleteLast()# param_5 = obj.getFront()# param_6 = obj.getRear()# param_7 = obj.isEmpty()# param_8 = obj.isFull()# ------------------------------------------# Another Optimized SolutionclassMyCircularDeque:def__init__(self,k:int):""" Initialize your data structure here. Set the size of the deque to be k. """ self.decq = [] self.maxsize = kdefinsertFront(self,value:int) ->bool:""" Adds an item at the front of Deque. Return true if the operation is successful. """iflen(self.decq)< self.maxsize: self.decq.append(value)returnTruedefinsertLast(self,value:int) ->bool:""" Adds an item at the rear of Deque. Return true if the operation is successful. """iflen(self.decq)< self.maxsize: self.decq.insert(0, value)returnTruedefdeleteFront(self) ->bool:""" Deletes an item from the front of Deque. Return true if the operation is successful. """if self.decq: self.decq.pop()returnTruedefdeleteLast(self) ->bool:""" Deletes an item from the rear of Deque. Return true if the operation is successful. """if self.decq:del self.decq[0]returnTruedefgetFront(self) ->int:""" Get the front item from the deque. """return self.decq[-1]if self.decq else-1defgetRear(self) ->int:""" Get the last item from the deque. """return self.decq[0]if self.decq else-1defisEmpty(self) ->bool:""" Checks whether the circular deque is empty or not. """returnlen(self.decq)==0defisFull(self) ->bool:""" Checks whether the circular deque is full or not. """returnlen(self.decq)==self.maxsize# ------------------------------------------# Your MyCircularDeque object will be instantiated and called as such:# obj = MyCircularDeque(k)# param_1 = obj.insertFront(value)# param_2 = obj.insertLast(value)# param_3 = obj.deleteFront()# param_4 = obj.deleteLast()# param_5 = obj.getFront()# param_6 = obj.getRear()# param_7 = obj.isEmpty()# param_8 = obj.isFull()class MyCircularQueue:def__init__(self,k:int): self.size =0 self.maxsize = k self.cq = [0]*k self.front = self.rear =-1defenQueue(self,value:int) ->bool:if self.size == self.maxsize:returnFalseelse:if self.rear ==-1: self.rear = self.front =0else: self.rear = (self.rear+1)%self.maxsize self.cq[self.rear]= value self.size +=1returnTruedefdeQueue(self) ->bool:if self.size ==0:returnFalseif self.front == self.rear: self.front = self.rear =-1else: self.front = (self.front+1)%self.maxsize self.size -=1returnTruedefFront(self) ->int:return self.cq[self.front]if self.size!=0else-1defRear(self) ->int:return self.cq[self.rear]if self.size!=0else-1defisEmpty(self) ->bool:return self.size ==0defisFull(self) ->bool:return self.size == self.maxsize# ------------------------------------------# Your MyCircularQueue object will be instantiated and called as such:# obj = MyCircularQueue(k)# param_1 = obj.enQueue(value)# param_2 = obj.deQueue()# param_3 = obj.Front()# param_4 = obj.Rear()# param_5 = obj.isEmpty()# param_6 = obj.isFull()# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:defdiameterOfBinaryTree(self,root: TreeNode) ->int: self.depth =1deffindDepth(first):ifnot first:return0 ld =findDepth(first.left) rd =findDepth(first.right) self.depth =max(self.depth, ld+rd+1)returnmax(ld,rd)+1findDepth(root)return self.depth - 1class Solution:deftrailingZeroes(self,n:int) ->int: count =0 m =5while (n/m >=1): count +=int(n/m) m *=5return count # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:deffindBottomLeftValue(self,root: TreeNode) ->int: queue =deque([root]) visited =set()while queue: size =len(queue) leftmost = math.inffor i inrange(size): node = queue.popleft()if leftmost == math.inf: leftmost = node.valif node.left: queue.append(node.left)if node.right: queue.append(node.right)ifnot queue:return leftmostreturn0# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:deffindDuplicateSubtrees(self,root: TreeNode) -> List[TreeNode]: tree = collections.defaultdict() tree.default_factory = tree.__len__ c = collections.Counter() anslist = []deffind(node):if node: tid = tree[node.val,find(node.left),find(node.right)] c[tid]+=1if c[tid]==2: anslist.append(node)return tidfind(root)return anslistfrom collections import CounterclassSolution:deffirstUniqChar(self,s:str) ->int: c =Counter(s)for i inrange(len(s)):if c[s[i]]==1:return ireturn-1class Solution:deffizzBuzz(self,n:int) -> List[str]: res = []for i inrange(1, n+1):if i %3==0and i %5==0: res.append("FizzBuzz")elif i %3==0: res.append("Fizz")elif i %5==0: res.append("Buzz")else: res.append(str(i))return resimport collectionsclassSolution:defgroupAnagrams(self,strs: List[str]) -> List[List[str]]: word = collections.defaultdict(list)for s in strs: word[tuple(sorted(s))].append(s)return word.values()class MyQueue:def__init__(self):""" Initialize your data structure here. """ self.s1 = [] self.s2 = []defpush(self,x:int) ->None:""" Push element x to the back of queue. """ self.s1.append(x)defpop(self) ->int:""" Removes the element from in front of queue and returns that element. """whilelen(self.s1)>1: self.s2.append(self.s1.pop()) temp = self.s1.pop()whilelen(self.s2): self.s1.append(self.s2.pop())return tempdefpeek(self) ->int:""" Get the front element. """return self.s1[0]defempty(self) ->bool:""" Returns whether the queue is empty. """returnFalseiflen(self.s1)elseTrue# ------------------------------------------# 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()## Implementation Using queue.Queue()## Faster than 67%from queue import QueueclassMyStack:def__init__(self):""" Initialize your data structure here. """ self.q1 =Queue(maxsize=0) self.q2 =Queue(maxsize=0)defpush(self,x:int) ->None:""" Push element x onto stack. """ self.q1.put(x)defpop(self) ->int:""" Removes the element on top of the stack and returns that element. """while(self.q1.qsize()>1): self.q2.put(self.q1.get()) temp = self.q1.get()while(self.q2.qsize()>0): self.q1.put(self.q2.get())return tempdeftop(self) ->int:""" Get the top element. """while(self.q1.qsize()>1): self.q2.put(self.q1.get()) temp = self.q1.get()while(self.q2.qsize()>0): self.q1.put(self.q2.get()) self.q1.put(temp)return tempdefempty(self) ->bool:""" Returns whether the stack is empty. """return self.q1.empty()# ------------------------------------------## Implementation using Deque## Faster than 100%from collections import dequeclassMyStack:def__init__(self):""" Initialize your data structure here. """ self.q =deque()defpush(self,x:int) ->None:""" Push element x onto stack. """ self.q.append(x)defpop(self) ->int:""" Removes the element on top of the stack and returns that element. """return self.q.pop()deftop(self) ->int:""" Get the top element. """ temp = self.q.pop() self.q.append(temp)return tempdefempty(self) ->bool:""" Returns whether the stack is empty. """returnFalseiflen(self.q)elseTrue# ------------------------------------------# Your MyStack object will be instantiated and called as such:# obj = MyStack()# obj.push(x)# param_2 = obj.pop()# param_3 = obj.top()# param_4 = obj.empty()class CustomStack:def__init__(self,maxSize:int): self.stack = [] self.maxSize = maxSizedefpush(self,x:int) ->None:if(len(self.stack)< self.maxSize): self.stack.append(x)defpop(self) ->int:if(len(self.stack)!=0):return self.stack.pop()else:return-1defincrement(self,k:int,val:int) ->None:for i inrange(min(k, len(self.stack))): self.stack[i]+= val # ------------------------------------------# Your CustomStack object will be instantiated and called as such:# obj = CustomStack(maxSize)# obj.push(x)# param_2 = obj.pop()# obj.increment(k,val)import mathclassSolution:defintegerReplacement(self,n:int) ->int: s =0while(n!=1):if(n%2==0): n //=2 s +=1continueif(n==3):return s+2else:if(math.ceil(math.log2(n-1))==math.floor(math.log2(n-1))): n -=1elif((math.ceil(math.log2(n+1))==math.floor(math.log2(n+1))) or ((n+1)%4==0)): n +=1else: n -=1 s +=1return sclass Solution:defintToRoman(self,num:int) ->str: dic = { 1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I' }
ans =''for i in dic:while num>=i: ans += dic[i] num -= ireturn ansclass Solution:defintersect(self,nums1: List[int],nums2: List[int]) -> List[int]:iflen(nums1)>len(nums2): i =0while i <len(nums2):if nums2[i]inset(nums1): nums1.remove(nums2[i]) i +=1else: nums2.remove(nums2[i])return nums2else: i =0while i <len(nums1):if nums1[i]inset(nums2): nums2.remove(nums1[i]) i +=1else: nums1.remove(nums1[i])return nums1# ------------------------------------------# Alternate Approachfrom collections import CounterclassSolution:defintersect(self,nums1: List[int],nums2: List[int]) -> List[int]:returnlist((Counter(nums1)&Counter(nums2)).elements())# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:definvertTree(self,root: TreeNode) -> TreeNode:definvert(node):if node.left:invert(node.left)if node.right:invert(node.right) temp = node.left node.left = node.right node.right = tempif root:invert(root)return rootclass Solution:defisSubsequence(self,s:str,t:str) ->bool:iflen(s)==0:returnTrueiflen(t)==0:returnFalse sp =0for tc in t:if s[sp]== tc: sp +=1if sp ==len(s):returnTruereturn Falseclass Solution:deflastStoneWeight(self,stones: List[int]) ->int:while(len(stones)!=1andlen(stones)!=0): stones =sorted(stones) t =abs(stones[-1]-stones[-2])if(t!=0): stones.pop() stones[-1]= telse: stones.pop() stones.pop()if(stones):return stones[0]return 0class Solution:deflemonadeChange(self,bills: List[int]) ->bool: denom ={5:0,10:0,20:0}for i inrange(len(bills)): denom[bills[i]]+=1if bills[i]>5: bal = bills[i]-5if bal %5==0and bal %10!=0:if denom[5]>0: denom[5]-=1 bal -=5if bal ==0:continueif bal %10==0and bal %20!=0:if denom[10]>0: denom[10]-=1 bal -=10if bal ==0:continueif denom[5]>1: denom[5]-=2 bal -=10if bal ==0:continueif bal >0:returnFalsereturn Trueclass Solution:deflongestCommonPrefix(self,strs: List[str]) ->str: x =0for i inzip(*strs): r =all(a == i[0] for a in i)if r: x +=1else:breakreturn strs[0][0:x] if x else''classSolution:deflargestSumAfterKNegations(self,A: List[int],K:int) ->int: A =sorted(A)for i inrange(len(A)):if A[i]<0: A[i]=-A[i] K -=1elif A[i]>=0:if K %2==0:breakelse: A[A.index(min(A))]=-A[A.index(min(A))]breakif K ==0:breakreturnsum(A)# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defmergeTwoLists(self,l1: ListNode,l2: ListNode) -> ListNode: dummy = l3 =ListNode(0)while l1 and l2:if l1.val > l2.val: l3.next =ListNode(l2.val) l3 = l3.next l2 = l2.nextelse: l3.next =ListNode(l1.val) l3 = l3.next l1 = l1.nextwhile l1: l3.next =ListNode(l1.val) l3 = l3.next l1 = l1.nextwhile l2: l3.next =ListNode(l2.val) l3 = l3.next l2 = l2.nextreturn dummy.next# ------------------------------------------# Slightly More Optimized# ------------------------------------------# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defmergeTwoLists(self,l1: ListNode,l2: ListNode) -> ListNode: head = l3 =ListNode()while l1 and l2:if l1.val < l2.val: l3.next =ListNode(l1.val) l1 = l1.next l3 = l3.nextelse: l3.next =ListNode(l2.val) l2 = l2.next l3 = l3.next l3.next = l1 or l2return head.next# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defmiddleNode(self,head: ListNode) -> ListNode: A = [head]while A[-1].next: A.append(A[-1].next)return A[len(A)//2]# ------------------------------------------# Solution using Slow and Fast PointersclassSolution:defmiddleNode(self,head: ListNode) -> ListNode: slowPointer = head fastPointer = headwhile(fastPointer and fastPointer.next): slowPointer = slowPointer.next fastPointer = fastPointer.next.nextreturn slowPointer import mathclassMinStack:def__init__(self):""" initialize your data structure here. """ self.stack = [] self.min = math.infdefpush(self,x:int) ->None: self.x = x self.stack.append(x)if(x < self.min): self.min = x defpop(self) ->None: t = self.stack.pop()if(t==self.min andlen(self.stack)): self.min =min(self.stack)elif(t==self.min andnotlen(self.stack)): self.min = math.infdeftop(self) ->int:return self.stack[-1]defgetMin(self) ->int:return self.min # ------------------------------------------# Your MinStack object will be instantiated and called as such:# obj = MinStack()# obj.push(x)# obj.pop()# param_3 = obj.top()# param_4 = obj.getMin()class Solution:defminSubsequence(self,nums: List[int]) -> List[int]: nums =sorted(nums)[::-1] x =sum(nums) s =0iflen(nums)==1:return numsfor i inrange(len(nums)+1): s += nums[i]if s > x-s:return nums[0:i+1]classSolution:defisMonotonic(self,A: List[int]) ->bool: inc =True dec =Truefor i inrange(0, len(A)-1):if(A[i]> A[i+1]): inc =Falseif(A[i]< A[i+1]): dec =Falsereturn inc or decclassSolution:defmoveZeroes(self,nums: List[int]) ->None:""" Do not return anything, modify nums in-place instead. """ t = nums.count(0) nzpos =0if(t==0):return numsfor i inrange(0, len(nums)):if(nums[i]!=0): nums[nzpos]= nums[i] nzpos = nzpos+1for i inrange(len(nums)-t, len(nums)): nums[i]=0from collections import dequeclassSolution:defnumIslands(self,grid) ->int:ifnot grid:return0 r =len(grid) c =len(grid[0]) queue =deque() islands =0for i inrange(r):for j inrange(c):if grid[i][j] =='1': islands +=1 grid[i][j] ='0' queue.append([i, j])while queue: el = queue.popleft() rs = el[0] cs = el[1]if rs -1>=0and grid[rs-1][cs] =='1': queue.append([rs-1, cs]) grid[rs-1][cs] ='0'if rs +1< r and grid[rs+1][cs] =='1': queue.append([rs+1, cs]) grid[rs+1][cs] ='0'if cs -1>=0and grid[rs][cs-1] =='1': queue.append([rs, cs-1]) grid[rs][cs-1] ='0'if cs +1< c and grid[rs][cs+1] =='1': queue.append([rs, cs+1]) grid[rs][cs+1] ='0'return islandsclass RecentCounter:def__init__(self): self.q = collections.deque()defping(self,t:int) ->int: self.q.append(t)while self.q[0]< t-3000: self.q.popleft()returnlen(self.q)classSolution:defhammingWeight(self,n:int) ->int:return (bin(n).count('1'))# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution1:defisPalindrome(self,head: ListNode) ->bool: temp = head stack = [] l =0while temp: l +=1 temp = temp.next temp = headfor i inrange(0, l//2): stack.append(temp.val) temp = temp.nextif l %2!=0: temp = temp.nextfor i inrange(0, l//2):if temp.val == stack.pop():continuereturnFalsereturnTrue# ------------------------------------------# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution2:defisPalindrome(self,head: ListNode) ->bool: el = []while head: el.append(head.val) head = head.nextfor i inrange(0, len(el)//2):ifnot el[i]== el[-i-1]:returnFalsereturn Trueclass Solution:defisPalindrome(self,x:int) ->bool: a = [] x =str(x) x =list(x) a = x[::-1]if (str(a)==str(x)):returnTrueelse:returnFalse"""This first solution uses the interval splitting methodThis is achieved by using a dp table.Time Complexity: O(n^1.5)"""classSolution1:defnumSquares(self,n) ->int:if n <=3:return n dp = [0for _ inrange(n+1)] dp[1], dp[2], dp[3]=1,2,3for i inrange(4, len(dp)): dp[i]= i j =1while j*j <= i: dp[i]=min(dp[i], 1+ dp[i - j*j]) j +=1return dp[-1]"""Lagrange's 4 square and 3 square theoremTheorem: Every natural number can be represented as the sum of 4 integer squares.N = a^2 + b^2 + c^2 + d^2Theorem: A natural number can be represented as sum of 3 squares of integers.N = a^2 + b^2 + c^2if and only if the N is not of the form,N = 4^a (8b + 7) -- (1)LOGIC: - if N is a perfect square, return 1- if N is of form (1), - keep dividing by 4 - divide by 8 - if rem == 7: return 4- check if N can be split into two perfect squares. If yes, return 2- if all fails, return 3"""classSolution:defnumSquares(self,n:int) ->int:ifceil(sqrt(n))==floor(sqrt(n)):return1while n %4==0: n /=4if n %8==7:return4 j =1while j*j <= n:ifceil(sqrt(n - j*j))==floor(sqrt(n - j*j)):return2 j +=1else:return 3class Solution:defstringShift(self,s:str,shift: List[List[int]]) ->str: amount =0for i inrange(len(shift)):if(shift[i][0]==0): amount += (-1)*shift[i][1]else: amount +=1*shift[i][1]print(amount)if amount ==0:return selif amount <0:return s[(abs(amount)%len(s)):]+ s[0:(abs(amount)%len(s))]else:return s[len(s)-(amount%len(s)):]+ s[0:len(s)-(amount%len(s))]classSolution:defplusOne(self,digits: List[int]) -> List[int]: carry =0for i inrange(len(digits)-1, -1, -1):if digits[i]!=9: digits[i]+=1breakelse: digits[i]=0if i ==0: digits.insert(0, 1)return digitsclass Solution:defisPowerOfThree(self,n:int) ->bool:if n <1:returnFalseif n ==1:returnTrueifsum(list(map(int, str(n))))%3!=0:returnFalseelse:while n >1:if n %3==0: n /=3else:returnFalseif n !=1:returnFalseelse:returnTrue# ------------------------------------------# Alternate ApproachclassSolution:defisPowerOfThree(self,n:int) ->bool:if n <1:returnFalseelse:return1162261467% n ==0# Classic SolutionclassSolution:defisPowerOfTwo(self,n:int) ->bool:if n ==1:returnTrueif n ==0:returnFalsewhile n %2==0: n = n /2if n ==1:returnTrueelse:returnFalse# ------------------------------------------# Solution Using Bit ManipulationclassSolution:defisPowerOfTwo(self,n:int) ->bool:return n >0andbin(n).count('1')== 1class Solution:defreconstructQueue(self,people: List[List[int]]) -> List[List[int]]: people.sort(key =lambdax: (-x[0], x[1])) rec = []for p in people: rec.insert(p[1], p)return recfrom random import choicesclassSolution:def__init__(self,w: List[int]): self.w = wdefpickIndex(self) ->int:returnchoices(range(len(self.w)), self.w)[0]# ------------------------------------------# Your Solution object will be instantiated and called as such:# obj = Solution(w)# param_1 = obj.pickIndex()class Solution:defremoveDuplicates(self,nums: List[int]) ->int: p =0while p <len(nums)-1:if nums[p]== nums[p+1]: nums.pop(p+1)continue p +=1returnlen(nums)# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defremoveElements(self,head: ListNode,val:int) -> ListNode: pointer =ListNode(0) pointer.next = head tempnode = pointerwhile tempnode.next !=None:if tempnode.next.val == val: tempnode.next = tempnode.next.nextelse: tempnode = tempnode.nextreturn pointer.next# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defremoveNthFromEnd(self,head: ListNode,n:int) -> ListNode: tail = head length =1while tail.next: length +=1 tail = tail.nextif(length==1):returnNoneif(length==n):return head.next tempnode = headfor _ inrange(0, length-n-1): tempnode = tempnode.next tempnode.next = tempnode.next.nextreturn head# ------------------------------------------# One Pass# ------------------------------------------# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defremoveNthFromEnd(self,head: ListNode,n:int) -> ListNode: dummy = fast = slow =ListNode() dummy.next = headifnot head.next:returnNonefor _ inrange(n+1): fast = fast.nextwhile fast: fast = fast.next slow = slow.next slow.next = slow.next.nextreturn dummy.nextclass Solution:defreorganizeString(self,S:str) ->str: l =len(S) A = []for k, v insorted((S.count(x), x) for x inset(S)):if k > (l+1) /2:return"" A.extend(k * v)# print(A) ans = [None] * l ans[::2], ans[1::2]= A[(l//2) :], A[: (l//2)]return''.join(ans)class Solution:deffindRepeatedDnaSequences(self,s:str) -> List[str]: dic ={} ans = []for i inrange(0, len(s)-9):if s[i:i+10]notin dic: dic[s[i:i+10]]=1else: dic[s[i:i+10]]+=1for k, v in dic.items():if v>1: ans.append(k)return ansclass Solution:defreverseBits(self,n:int) ->int: s =str(bin(n)) s = s[2:] s ='0'*(32-len(s)) + s s =int(s[::-1], 2)return sclass Solution:defreverse(self,x:int) ->int: x =str(x)if (x[0]=='-'): a = x[1:2147483648:1] a = a[::-1]if (int(a)>2147483648):return0returnint("-"+a)else: a = x[::-1]if (int(a)>2147483647):return0returnint(a)# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defreverseList(self,head: ListNode) -> ListNode: temp = head prev =Nonewhile(temp!=None):next= temp.next temp.next = prev prev = temp temp =nextreturn prevclass Solution:defreverseString(self,s: List[str]) ->None:""" Do not return anything, modify s in-place instead. """ head =0 temp ='' tail =len(s)-1while head < tail: temp = s[head] s[head]= s[tail] s[tail]= temp head +=1 tail -= 1class Solution:defreverseParentheses(self,s:str) ->str: stack = [] s =list(s)for i inrange(len(s)):if s[i]=='(': stack.append(i)continueif s[i]==')': idx = stack.pop() s[idx+1: i]= s[idx+1: i][::-1] ans =""for i in s:if i=="("or i==")":continue ans += ireturn ansclass Solution:defromanToInt(self,s:str) ->int: ans =0 prev =''for i inrange(len(s)):if(s[i]=='M'):if(prev=='C'): ans +=800 prev ='M'continue ans +=1000 prev ='M'continueif(s[i]=='D'):if(prev=='C'): ans +=300 prev ='D'continue ans +=500 prev ='D'continueif(s[i]=='C'):if(prev=='X'): ans +=80 prev ='C'continue ans +=100 prev ='C'continueif(s[i]=='L'):if(prev=='X'): ans +=30 prev ='L'continue ans +=50 prev ='L'continueif(s[i]=='X'):if(prev=='I'): ans +=8 prev ='X'continue ans +=10 prev ='X'continueif(s[i]=='V'):if(prev=='I'): ans +=3 prev ='V'continue ans +=5 prev ='V'continueif(s[i]=='I'): ans +=1 prev ='I'return ansclass Solution:defrotate(self,nums: List[int],k:int) ->None:""" Do not return anything, modify nums in-place instead. """ x =len(nums) A = [0]*xfor i inrange(0, x): A[(i+k)%x]= nums[i]for i inrange(0, x): nums[i]= A[i]classSolution:defrotate(self,matrix: List[List[int]]) ->None:""" Do not return anything, modify matrix in-place instead. """ n =len(matrix)for x inzip(*matrix): matrix.pop(0) matrix.append(x[::-1])# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defrotateRight(self,head: ListNode,k:int) -> ListNode:ifnot head:returnNoneifnot k==0: tail = head length =1while(tail.next): length +=1 tail = tail.next k = k % length tail.next = head tempnode = headfor _ inrange(0, length-k-1): tempnode = tempnode.next a = tempnode.next tempnode.next =Nonereturn areturn headclass Solution:defsearchInsert(self,nums: List[int],target:int) ->int:defbinary(nums,low,high,target):if low <= high: mid = low + (high - low) //2if nums[mid]== target:return midelif nums[mid]> target:returnbinary(nums, low, mid-1, target)else:returnbinary(nums, mid+1, high, target)else:return high+1returnbinary(nums, 0, len(nums)-1, target)# ------------------------------------------# Iterative Binary Search classSolution:defsearchInsert(self,nums: List[int],target:int) ->int: low =0 high =len(nums)-1while low <= high: mid = (low + high) //2if nums[mid]== target:return midelif nums[mid]> target: high = mid -1else: low = mid +1else:return high + 1class Solution:def__init__(self,nums: List[int]): self.nums = nums shuf = self.nums.copy() self.shuf = shufdefreset(self) -> List[int]:""" Resets the array to its original configuration and return it. """ self.shuf = self.nums.copy()return self.shufdefshuffle(self) -> List[int]:""" Returns a random shuffling of the array. """ x =len(self.nums)for i inrange(x): j = random.randrange(i, x) self.shuf[i], self.shuf[j]= self.shuf[j], self.shuf[i]return self.shuf# ------------------------------------------# Your Solution object will be instantiated and called as such:# obj = Solution(nums)# param_1 = obj.reset()# param_2 = obj.shuffle()# from collections import dequeclassSolution:defsimplifyPath(self,path:str) ->str:if(len(path)==0or path==Noneor path==''):return'/' p = path.split('/') stack = []for item in p:if (item=='..'):if(stack): stack.pop()continueif item=='.'orlen(item)==0:passelse: stack.append(item)return'/'+'/'.join(stack)classSolution:defsingleNumber(self,nums: List[int]) ->int:returnint(((sum(set(nums))*3) -sum(nums))/2)classSolution:defsingleNumber(self,nums: List[int]) -> List[int]: ans = []for i inset(nums):if nums.count(i)==1: ans.append(i)if(len(ans)==2):return ansreturn ansfrom collections import CounterclassSolution:defsortColors(self,nums: List[int]) ->None:""" Do not return anything, modify nums in-place instead. """ n =Counter(nums) nums.clear()for v inrange(3):for i inrange(n[v]): nums.append(v)class Solution:defbalancedStringSplit(self,s:str) ->int: c =0 rc =0 lc =0for i inrange(len(s)):if s[i]=='R': rc +=1if s[i]=='L': lc +=1if rc == lc: c +=1 rc =0 lc =0return cclass Solution:defmyAtoi(self,str:str) ->int:iflen(str)==0:return0str=list(str.strip())iflen(str)==0:return0if(str[0]=='-'): s =-1else: s =1if str[0]in ['-','+']:del str[0] i =0 exp =0while(i <len(str)and str[i].isdigit()): exp = exp*10+ord(str[i])-ord('0') i +=1returnmax(-2**31, min(exp*s, 2**31-1))classSolution:defleastInterval(self,tasks: List[str],n:int) ->int: tasksDict = collections.Counter(tasks) heap = [] c =0for k, v in tasksDict.items():heappush(heap, (-v,k))while heap: i =0 stack = []while i<=n:iflen(heap)>0: index, task =heappop(heap)if index!=-1: stack.append((index+1, task)) c +=1iflen(heap)==0andlen(stack)==0:break i +=1for i in stack:heappush(heap, i)return c## Naive Solution that runs in O(n^2)## Traverses the array, and finds the maximum left or right element.## rainwater that can be stored in the column = min(left, right) - height[i]classNaiveSolution:deftrap(self,height) ->int: res =0 n =len(height)for i inrange(1, n-1): left = height[i]for j inrange(i): left =max(left, height[j]) right = height[i]for j inrange(i+1, n): right =max(right, height[j]) res +=min(left, right)- height[i]return res# ------------------------------------------## Optimized solution that runs in O(N)## Stores the left and right maximum values in two dp arrays.## Space Complexity - O(N)classSolution:deftrap(self,height: List[int]) ->int:if height == []:return0 n =len(height) res =0 left = [0for _ inrange(n)] right = [0for _ inrange(n)] left[0]= height[0] right[n-1]= height[n-1]for i inrange(1, n): left[i]=max(left[i-1], height[i])for i inrange(n-2, -1, -1): right[i]=max(right[i+1], height[i])for i inrange(n): res +=min(left[i], right[i])- height[i]return res classSolution:defminimumTotal(self,triangle: List[List[int]]) ->int: dp = [0for _ inrange(len(triangle)+1)]for r in triangle[::-1]:for i inrange(len(r)): dp[i]= r[i]+min(dp[i], dp[i+1])return dp[0]classSolution:deftwoCitySchedCost(self,costs: List[List[int]]) ->int: costs =sorted(costs, key =lambdax: x[0] - x[1]) return sum(i[0] for i in costs[0:len(costs)//2]) + sum(j[1] for j in costs[len(costs)//2:len(costs)])class Solution:
defuniquePathsWithObstacles(self,obstacleGrid: List[List[int]]) ->int: m =len(obstacleGrid) n =len(obstacleGrid[0])if obstacleGrid[0][0] ==1:return0 obstacleGrid[0][0] =1for i inrange(1, m): obstacleGrid[i][0] =int(obstacleGrid[i][0] ==0and obstacleGrid[i-1][0] ==1)for i inrange(1, n): obstacleGrid[0][i] =int(obstacleGrid[0][i] ==0and obstacleGrid[0][i-1] ==1)for i inrange(1, m):for j inrange(1, n):if obstacleGrid[i][j] ==0: obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]else: obstacleGrid[i][j] =0return obstacleGrid[-1][-1] from collections import CounterclassSolution:defisAnagram(self,s:str,t:str) ->bool:returnCounter(s)==Counter(t)classSolution:defisPalindrome(self,s:str) ->bool: s =''.join(a for a in s if a.isalnum()).lower()return s == s[::-1]classSolution:defcheckValidString(self,s:str) ->bool: lb =0 rb =0for i in s:if(i=='('or i=='*'): lb +=1else: lb -=1if lb <0:returnFalseif(lb==0):returnTruefor i inrange(len(s)-1, -1, -1):if(s[i]==')'or s[i]=='*'): rb +=1else: rb -=1if rb <0:returnFalsereturn Trueclass Solution(object):defrobotSim(self,commands,obstacles): dx = [0,1,0,-1] dy = [1,0,-1,0] x = y = di =0 obstacleSet =set(map(tuple, obstacles)) ans =0for cmd in commands:if cmd ==-2:#left di = (di -1) %4elif cmd ==-1:#right di = (di +1) %4else:for k inrange(cmd):if (x+dx[di], y+dy[di]) notin obstacleSet: x += dx[di] y += dy[di] ans =max(ans, x*x + y*y)# ------------------------------------------# Solution for https://leetcode.com/problems/two-sum/# Language : Python3# ------------------------------------------# O(n^2) SolutionclassSolution:deftwoSum(self,nums,target):for i inrange(len(nums)):for j inrange(i+1,len(nums)):if(nums[i]+nums[j]==target):return i, j# O(n) SolutionclassSolution:deftwoSum(self,nums: List[int],target:int) -> List[int]:dict={ v:k for k, v inenumerate(nums)}for i inrange(len(nums)):if target - nums[i]indictand nums.index(target - nums[i])!= i:return i, nums.index(target-nums[i])# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# -------------------------------------------
```