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
Leetcode: Word Ladder II @Python
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dict):
alph = [chr(c) for c in range(97, 123)]
def buildpath(path, word):
if len(prevMap[word])==0:
path.append(word); currPath=path[:]
currPath.reverse(); result.append(currPath)
path.pop();
return
path.append(word)
for iter in prevMap[word]:
buildpath(path, iter)
path.pop()
result=[]
prevMap={}
dict.add(end)
dict.add(start)
length=len(start)
for i in dict:
prevMap[i]=[]
candidates=[set(),set()]; current=0; previous=1
candidates[current].add(start)
while end not in candidates[current]:
current, previous=previous, current
for i in candidates[previous]: dict.remove(i)
candidates[current].clear()
for word in candidates[previous]:
for i in range(length):
part1=word[:i]; part2=word[i+1:]
for j in alph:
if word[i]!=j:
nextword=part1+j+part2
if nextword in dict:
prevMap[nextword].append(word)
candidates[current].add(nextword)
if len(candidates[current])==0: return result
buildpath([], end)
return result
Leetcode: Wildcard Matching @Python
class Solution:
# @param s, an input string
# @param p, a pattern string
# @return a boolean
def isMatch(self, s, p):
n=len(s)
m=len(p)
i=0
j=0
star=0
s_coor=None
while i<n:
if j<m and (s[i]==p[j] or p[j]=='?'):
j+=1
i+=1
elif j<m and p[j]=='*':
s_coor=i
star=j
j+=1
elif s_coor!=None:
i=s_coor+1
j=star+1
s_coor+=1
else:
return False
while j<m and p[j]=='*':
j+=1
if j==m:
return True
else:
return False
Leetcode: Text Justification @Python
class Solution:
# @param words, a list of strings
# @param L, an integer
# @return a list of strings
def fullJustify(self, words, L):
def gen(queue,num,blanks):
line=[]
if num==1:
item=queue.pop()
line=item+''.join([' ']*(L-len(item)))
rst.append(line)
return
spare=blanks%(num-1)
while queue:
word=queue.popleft()
space=blanks//(num-1)+1 if spare>0 else blanks//(num-1)
spare-=1
if queue:
line.append(word+''.join([' ']*space))
else:
line.append(word)
rst.append(''.join(line))
queue=collections.deque([])
rst=[]
n=0
num=0
while words:
if n+len(words[0])<=L:
queue.append(words[0])
n+=len(words[0])+1
num+=1
words.pop(0)
else:
blanks=L-n+num if n<=L else num-1
gen(queue,num,blanks)
num=0
n=0
line=' '.join(list(queue))
rst.append(line+''.join([' ']*(L-len(line))))
return rst
Leetcode: LRU Cache @Python
class LRUCache:
# @param capacity, an integer
def __init__(self, capacity):
LRUCache.dic=collections.OrderedDict()
LRUCache.capacity=capacity
LRUCache.size=0
# @return an integer
def get(self, key):
try:
value=LRUCache.dic[key]
del LRUCache.dic[key]
LRUCache.dic[key]=value
return value
except KeyError:
return -1
# @param key, an integer
# @param value, an integer
# @return nothing
def set(self, key, value):
try:
del LRUCache.dic[key]
LRUCache.dic[key]=value
except:
if LRUCache.size==LRUCache.capacity:
LRUCache.dic.popitem(False)
LRUCache.dic[key]=value
else:
LRUCache.size+=1
LRUCache.dic[key]=value
Leetcode: Reverse Words in a String @Python
class Solution:
# @param s, a string
# @return a string
def reverseWords(self, s):
return " ".join(s.split()[::-1])
Leetcode: Surrounded Regions @Python
class Solution:
# @param board, a 9x9 2D array
# Capture all regions by modifying the input board in-place.
# Do not return any value.
def solve(self, board):
def fill(x, y):
if x<0 or x>m-1 or y<0 or y>n-1 or board[x][y] != 'O': return
queue.append((x,y))
board[x][y]='D'
def bfs(x, y):
if board[x][y]=='O':queue.append((x,y)); fill(x,y)
while queue:
curr=queue.pop(0); i=curr[0]; j=curr[1]
fill(i+1,j);fill(i-1,j);fill(i,j+1);fill(i,j-1)
if len(board)==0: return
m=len(board); n=len(board[0]); queue=[]
for i in range(n):
bfs(0,i); bfs(m-1,i)
for j in range(1, m-1):
bfs(j,0); bfs(j,n-1)
for i in range(m):
for j in range(n):
if board[i][j] == 'D': board[i][j] = 'O'
elif board[i][j] == 'O': board[i][j] = 'X'
Leetcode: String to Integer (atoi) @Python
Cheating with int():
class Solution:
# @return an integer
def atoi(self, str):
str = str.strip()
newStr = []
for i in range(len(str)):
if '0' <= str[i] <= '9' or (str[i] in ('+', '-') and i == 0):
newStr.append(str[i])
else:
break
if newStr in ([], ['+'], ['-']):
return 0
elif -2147483648 <= int(''.join(newStr)) <= 2147483647:
return int(''.join(newStr))
elif int(''.join(newStr)) > 2147483647:
return 2147483647
else:
return -2147483648
Without cheating:
class Solution:
# @return an integer
def atoi(self, Str):
dic={"0":0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9}
rst=0
validset='+-0123456789'
numberset='0123456789'
INT_MAX="2147483647"
INT_MIN="2147483648"
Str=Str.lstrip(' ')
for i in range(len(Str)):
if Str[i] not in validset:
Str=Str[:i]
break
if (len(Str)==1 and Str in '+-') or ('-' in Str[1:] or '+' in Str[1:]) or len(Str)==0:
return 0
sign=1
if Str[0]=='-':
sign=-1
Str=Str[1:]
elif Str[0]=='+':
Str=Str[1:]
if len(Str)>10:
return -2147483648 if sign==-1 else 2147483647
elif len(Str)==10:
overflow=True
if sign==-1:
for i in range(10):
if Str[i]<INT_MIN[i]:
overflow=False
break
if overflow:
return -2147483648
else:
for i in range(10):
if Str[i]<INT_MAX[i]:
overflow=False
break
if overflow:
return 2147483647
for i in range(len(Str)):
if sign==1:
rst+=dic[Str[i]]*(10**(len(Str)-i-1))
else:
rst-=dic[Str[i]]*(10**(len(Str)-i-1))
return rst
else:
for i in range(len(Str)):
rst+=dic[Str[i]]*(10**(len(Str)-i-1))
return rst*sign
Leetcode: Decode Ways @Python
class Solution:
# @param s, a string
# @return an integer
def numDecodings(self, s):
n=len(s)
dp=[0]*(n)
if n==0: return 0
if s[0]!='0':
dp[0]=1
else:
return 0
for i in range(1,n):
if s[i]=='0':
if s[i-1] in '12':
if i<2:
dp[i]=1
else:
dp[i]=dp[i-2]
else:
return 0
elif s[i-1]=='0':
dp[i]=dp[i-1]
else:
if int(s[i-1:i+1])<=26:
if i<2:
dp[i]=2
else:
dp[i]=dp[i-1]+dp[i-2]
else:
dp[i]=dp[i-1]
return dp[n-1]
Leetcode: Divide Two Integers @Python
class Solution:
# @return an integer
def divide(self, dividend, divisor):
sign = 1 if (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0) else -1
dividend = abs(dividend)
divisor = abs(divisor)
quotient = 0
while dividend >= divisor:
k = 0; tmp = divisor
while dividend >= tmp:
quotient += 1 << k
dividend -= tmp
tmp <<= 1
k += 1
return quotient if sign==1 else -quotient
Leetcode: Word Break II @Python
class Solution:
# @param s, a string
# @param dict, a set of string
# @return a list of strings
def wordBreak(self, s, dict):
n=len(s)
A=[[] for i in range(n)]
i=n-1
while i>=0:
if s[i:n] in dict:
A[i].append(n)
for j in range(i+1,n):
if A[j] and s[i:j] in dict:
A[i]+=[j]
i-=1
path=[[0]]
rst=[]
while path:
new_path=[]
for i in path:
if i[-1]==n:
temp=[s[i[k]:i[k+1]] for k in range(len(i)-1)]
rst.append(' '.join(temp))
else:
for node in A[i[-1]]:
new_path.append(i+[node])
path=new_path
return rst
Leetcode: 3Sum @Python
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
A=sorted(num)
n=len(A)
rst=[]
for k in range(n-2):
a=A[k]
if k>0 and a==A[k-1]:
continue
i=k+1
j=n-1
while j>i:
s2=A[i]+A[j]
if s2==-A[k]:
rst.append([A[k],A[i],A[j]])
while j>i:
i+=1
j-=1
if A[i]!=A[i-1] or A[j]!=A[j+1]:
break
elif A[k]+s2>0:
while j>i:
j-=1
if A[j]!=A[j+1]:
break
else:
while j>i:
i+=1
if A[i]!=A[i-1]:
break
return rst
Leetcode: Median of Two Sorted Arrays @Python
class Solution:
# @return a float
def getMedian(self, A, B, k):
# return kth smallest number of arrays A and B, assume len(A) <= len(B)
lenA = len(A); lenB = len(B)
if lenA > lenB: return self.getMedian(B, A, k)
if lenA == 0: return B[k-1]
if k == 1: return min(A[0], B[0])
pa = min(k/2, lenA); pb = k - pa
return self.getMedian(A[pa:], B, k - pa) if A[pa - 1] <= B[pb - 1] else self.getMedian(A, B[pb:], k - pb)
def findMedianSortedArrays(self, A, B):
lenA = len(A); lenB = len(B)
if (lenA + lenB) % 2 == 1:
return self.getMedian(A, B, (lenA + lenB) / 2 + 1)
else:
return 0.5 * ( self.getMedian(A, B, (lenA + lenB) / 2) + self.getMedian(A, B, (lenA + lenB) / 2 + 1) )
Leetcode: Substring with Concatenation of All Words @Python
class Solution:
# @param S, a string
# @param L, a list of string
# @return a list of integer
def findSubstring(self, S, L):
n,m,w=len(S),len(L),len(L[0])
rst=[]
for index in xrange(n-m*w+1):
seg=[S[i:i+w] for i in xrange(index,index+m*w,w)]
for item in L:
if item in seg:
seg.remove(item)
else:
break
if seg==[]:rst.append(index)
return rst
Subscribe to:
Posts
(
Atom
)