class MinStack:
# @param x, an integer
def __init__(self):
# the stack it self
self.A = []
self.minS=[]
# @return an integer
def push(self, x):
n=len(self.A)
if n==0:
self.minS.append(x)
else:
lastmin=self.minS[-1]
if x%lt;=lastmin:
self.minS.append(x)
self.A.append(x)
# @return nothing
def pop(self):
if len(self.A)>0 and self.A.pop()==self.minS[-1]:
self.minS.pop()
# @return an integer
def top(self):
return self.A[-1]
# @return an integer
def getMin(self):
return self.minS[-1]
Monday, November 10, 2014
Leetcode: Min Stack @Python
Use another stack to keep track of the min value so far.
Wednesday, October 22, 2014
Leetcode: Find Minimum in Rotated Sorted Array @Python
Pay attention to the ending condition and edge cases.
class Solution:
# @param num, a list of integer
# @return an integer
def findMin(self, num):
n=len(num)
strt=0
nd=n-1
while num[strt]>num[nd]:
mid=(strt+nd)//2
if num[strt]>num[mid]:
nd=mid
elif num[strt]<num[mid]:
strt=mid
else:
return num[nd]
return num[strt]
Leetcode: Find Minimum in Rotated Sorted Array II @Python
class Solution:
# @param num, a list of integer
# @return an integer
def findMin(self, num):
n=len(num)
strt=0
nd=n-1
while nd-strt>1:
mid=(strt+nd)//2
if num[strt]<num[nd]:
return num[strt]
elif num[strt]>num[nd]:
if num[strt]>num[mid]:
nd=mid
else:
strt=mid
else:
strt+=1
return num[strt] if num[strt]<num[nd] else num[nd]
Wednesday, October 8, 2014
Leetcode: Maximum Product Subarray @Python
Dynamic Programming, O(n) time complexity and O(1) space complexity.
Scan the list once,keep updating two variables mincrt and maxcrt.
mincrt is the minimum product end with the last element scanned. maxcrt is the maximum counterpart.
rst is used to store the maximal product so far.
Every time when updating with the new element, mincrt and maxcrt are from either the product with the new element ,or breaking up multiplication and starting from the new element.
Scan the list once,keep updating two variables mincrt and maxcrt.
mincrt is the minimum product end with the last element scanned. maxcrt is the maximum counterpart.
rst is used to store the maximal product so far.
Every time when updating with the new element, mincrt and maxcrt are from either the product with the new element ,or breaking up multiplication and starting from the new element.
class Solution:
# @param A, a list of integers
# @return an integer
def maxProduct(self, A):
mincrt=maxcrt=rst=A[0]
for i in range(1,len(A)):
mincrt,maxcrt=min(A[i],A[i]*mincrt,A[i]*maxcrt),max(A[i],A[i]*mincrt,A[i]*maxcrt)
rst=max(rst,maxcrt)
return rst
Friday, September 19, 2014
Solutions to All Leetcode Problems with Python
I finally finished all the 154 Leetcode problems in Python.
In my blog, I try to post the most succinct and effective Python solutions to Leetcode problems. You are more than welcome to post your solutions in the comments if you think yours are better.
I will add on explanations to the solutions later.
I also want to thank the following two bloggers. 水中的鱼 explains the algorithms in a clear and succinct way. Kitt's blog is the best Python leetcode solution blog so far.
In my blog, I try to post the most succinct and effective Python solutions to Leetcode problems. You are more than welcome to post your solutions in the comments if you think yours are better.
I will add on explanations to the solutions later.
I also want to thank the following two bloggers. 水中的鱼 explains the algorithms in a clear and succinct way. Kitt's blog is the best Python leetcode solution blog so far.
Leetcode: Max Points on a Line @Python
# Definition for a point
# class Point:
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b
class Solution:
# @param points, a list of Points
# @return an integer
def maxPoints(self, points):
if len(points)==0: return 0
n=len(points)
maxnum=1
for i in range(n):
dic={'inf':0}
same=0
for j in range(n):
if points[i].x==points[j].x and points[i].y==points[j].y:
same+=1
else:
slope='inf' if points[i].x==points[j].x else 1.0*(points[i].y-points[j].y)/(points[i].x-points[j].x)
if slope not in dic:
dic[slope]=1
else:
dic[slope]+=1
maxnum=max(maxnum,max(dic.values())+same)
return maxnum
Leetcode: Valid Number @Python
Finite State Machine Solution:
class Solution:
# @param s, a string
# @return a boolean
def isNumber(self, s):
s=s.rstrip(' ')
s=s.lstrip(' ')
trans=[[1,2,3,-1], #state 0:start
[1,-1,7,4], #state 1:digit
[1,-1,3,-1], #state 2: +/-
[7,-1,-1,-1], #state 3:.dot
[5,6,-1,-1], #state 4:e/E
[5,-1,-1,-1], #state 5: exponent
[5,-1,-1,-1], #state 6: exponent+/-
[7,-1,-1,4]] #state 7: .digits
state=0
for char in s:
if char in '0123456789':
inputs=1
elif char in '+-':
inputs=2
elif char=='.':
inputs=3
elif char in 'eE':
inputs=4
else:
return False
state=trans[state][inputs-1]
if state==-1:return False
if state==1 or state==5 or state==7:
return True
else:
return False
You can use the following code to find all corner cases.
Cheat Code:
class Solution:
# @param s, a string
# @return a boolean
def isNumber(self, s):
try:
float(s) # If error is shown then print False else True
return True
except:
return False
Subscribe to:
Posts
(
Atom
)