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.
Friday, September 19, 2014
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
Subscribe to:
Posts
(
Atom
)