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
Leetcode: Minimum Window Substring @Python
class Solution:
# @return a string
def minWindow(self, S, T):
count1={};
for char in T:
if char not in count1: count1[char]=1
else: count1[char]+=1
count=len(T)
start=0; minSize=len(S)+1; minStart=0
for end in range(len(S)):
if S[end] in count1:
count1[S[end]]-=1
if count1[S[end]]>=0:
count-=1
if count==0:
while True:
if S[start] in count1:
if count1[S[start]]<0:
count1[S[start]]+=1
else:
break
start+=1
if minSize>end-start+1:
minSize=end-start+1; minStart=start
if minSize==len(S)+1: return ''
else:
return S[minStart:minStart+minSize]
Leetcode: Palindrome Partitioning II @Python
Use Manacher's algorithm with O(n)
O(n^2) Dynamic Programming is not optimal.
My Manacher's algorithm implementation got TLE.
I learn from the solution here.
class Solution:
# @param s, s string
# @return an array
def _buildPalindromeCache(self, s):
transformed = "#" + "#".join(s) + "#"
palindrome_len = [1] * len(transformed)
center = 0
farest = 0
for index in xrange(1, len(transformed)):
if farest <= index:
tryingLen = 1
else:
preComputedLen = palindrome_len[2*center-index]
if preComputedLen + index > farest:
tryingLen = farest + 1 - index
else:
palindrome_len[index] = preComputedLen
continue
while index + tryingLen < len(transformed) and \
index - tryingLen >= 0:
if transformed[index + tryingLen] == \
transformed[index - tryingLen]:
tryingLen += 1
else:
break
if index + tryingLen -1 > farest:
farest = index + tryingLen -1
center = index
palindrome_len[index] = tryingLen
return palindrome_len
# @param begin, an integer
# @param end, an integer
# @param palindromeCache, an array
# @return a boolean
#def _isPalindrome(self, begin, end, palindromeCache):
''' In palindromeCache, the index for s[index] and s[end] are
index*2+1 and end*2+1 respectively. So in palindromeCache, the
middle point of s[index] and s[end] is (index*2+1 + end*2+1) // 2,
that is (index + end + 1).
IF you remove this function and use a single statement instead, you
could get a 30%-40% performance improvement or even more.
'''
# return palindromeCache[begin + end + 1] - 1 >= (end - begin + 1)
# @param s, a string
# @return an integer
def minCut(self, s):
''' Solve it in a dynamic programming method.
'''
if len(s) == 0: return 0
palindromeCache = self._buildPalindromeCache(s)
minCutEndingHere = [0] * len(s)
for index in xrange(1, len(s)):
if palindromeCache[index + 1] - 1 >= (index + 1):
# The substring from beginning to here is a palindrome. No
# cut is needed.
minCut = 0
else:
# We could add a cut between index and index - 1.
minCut = 1 + minCutEndingHere[index-1]
# Or the cut could be tried between tryingToCut and
# tryingToCut - 1.
for tryingToCut in xrange(1, index):
# Only when s[tryingToCut : index+1] is palindrome, the
# cut could be done.
if palindromeCache[tryingToCut + index + 1] - 1 >= (index - tryingToCut + 1):
minCut = min(minCut, \
1 + minCutEndingHere[tryingToCut-1])
minCutEndingHere[index] = minCut
return minCutEndingHere[-1]
Leetcode: Word Ladder @Python
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return an integer
def ladderLength(self, start, end, dic):
alph = [chr(c) for c in range(97, 123)]
dic.add(end)
n,m=len(dic),len(start)
que=collections.deque([[start,1]])
while que:
crt=que.popleft()
crtword,crtlen=crt[0],crt[1]
if crtword==end: return crtlen
for i in range(m):
s1=crtword[:i]
s2=crtword[i+1:]
for c in alph:
nextword=s1+c+s2
if nextword in dic and c!=crtword[i]:
dic.remove(nextword)
que.append([nextword,crtlen+1])
return 0
Leetcode: Two Sum @Python
class Solution:
# @return a tuple, (index1, index2)
def twoSum(self, num, target):
dict={}
for i in range(len(num)):
res=target-num[i]
if res in dict:
return (dict[res],i+1)
else:
dict[num[i]]=i+1
return (-1,-1)
Leetcode: Candy @Python
class Solution:
# @param ratings, a list of integer
# @return an integer
def candy(self, ratings):
n=len(ratings)
candynum=[1]*n
for i in range(1,n):
if ratings[i]>ratings[i-1]:
candynum[i]=candynum[i-1]+1
for i in reversed(range(n-1)):
if ratings[i]>ratings[i+1] and candynum[i]<=candynum[i+1]:
candynum[i]=candynum[i+1]+1
return sum(candynum)
Leetcode: Interleaving String @Python
class Solution:
# @return a boolean
def isInterleave(self, s1, s2, s3):
n=len(s1)
m=len(s2)
l=len(s3)
if l!=n+m:return False
match=[[True]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
match[i][0]=match[i-1][0] and s1[i-1]==s3[i-1]
for j in range(1,m+1):
match[0][j]=match[0][j-1] and s2[j-1]==s3[j-1]
for i in range(1,n+1):
for j in range(1,m+1):
match[i][j]=(s3[i+j-1]==s1[i-1] and match[i-1][j]) or (s3[i+j-1]==s2[j-1] and match[i][j-1])
return match[n][m]
Leetcode: Longest Valid Parentheses @Python
class Solution:
# @param s, a string
# @return an integer
def longestValidParentheses(self, s):
n=len(s)
stack=[(')',-1)]
maxlen=0
for i in range(n):
if s[i]==')' and stack[-1][0]=='(':
stack.pop()
maxlen=max(maxlen,i-stack[-1][1])
else:
stack.append((s[i],i))
return maxlen
Leetcode: Simplify Path @Python
class Solution:
# @param path, a string
# @return a string
def simplifyPath(self, path):
stack=[]
pathlist=path.split('/')
for i in pathlist:
if i==''or i=='.':
continue
elif i=='..':
if len(stack)>=1:
stack.pop()
else:
stack.append(i)
rst='/'+'/'.join(stack)
if rst=='':
return '/'
return rst
Thursday, September 18, 2014
Leetcode: Word Search @Python
class Solution:
# @param board, a list of lists of 1 length string
# @param word, a string
# @return a boolean
def exist(self, board, word):
self.totalRow, self.totalCol = len(board), len(board[0])
for i in xrange(self.totalRow):
for j in xrange(self.totalCol):
if board[i][j] == word[0]:
if self.dfs(board, i, j, word[1:]): return True
return False
def dfs(self, board, r, c, word):
if len(word) == 0: return True
increm=[[1,0],[-1,0],[0,1],[0,-1]]
for [i,j] in increm:
if self.totalRow>r+i>=0 and self.totalCol>c+j>=0 and board[r+i][c+j] == word[0]:
ch, board[r][c] = board[r][c], '#'
if self.dfs(board, r+i, c+j, word[1:]): return True
board[r][c] = ch
return False
Leetcode: Evaluate Reverse Polish Notation @Python
class Solution:
# @param tokens, a list of string
# @return an integer
def evalRPN(self, tokens):
stack = []
for i in tokens:
if i not in ('+', '-', '*', '/'):
stack.append(int(i))
else:
op2 = stack.pop()
op1 = stack.pop()
if i == '+': stack.append(op1 + op2)
elif i == '-': stack.append(op1 - op2)
elif i == '*': stack.append(op1 * op2)
else: stack.append(int(op1 * 1.0 / op2))
return stack[0]
Leetcode: Regular Expression Matching @Python
class Solution:
# @return a boolean
def isMatch(self, s, p):
dp=[[False for i in range(len(p)+1)] for j in range(len(s)+1)]
dp[0][0]=True
for i in range(1,len(p)+1):
if p[i-1]=='*':
if i>=2:
dp[0][i]=dp[0][i-2]
for i in range(1,len(s)+1):
for j in range(1,len(p)+1):
if p[j-1]=='.':
dp[i][j]=dp[i-1][j-1]
elif p[j-1]=='*':
dp[i][j]=dp[i][j-1] or dp[i][j-2] or (dp[i-1][j] and (s[i-1]==p[j-2] or p[j-2]=='.'))
else:
dp[i][j]=dp[i-1][j-1] and s[i-1]==p[j-1]
return dp[len(s)][len(p)]
Leetcode: Binary Tree Maximum Path Sum @Python
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return an integer
pathsum=-2**31
def sumpath(self,root):
subsum=-2**31
if not root:
return 0
else:
lsum=self.sumpath(root.left)
rsum=self.sumpath(root.right)
subsum=max(lsum+root.val,rsum+root.val,root.val)
self.pathsum=max(subsum,lsum+rsum+root.val,self.pathsum)
return subsum
def maxPathSum(self, root):
if not root: return None
self.sumpath(root)
return self.pathsum
Leetcode: Reorder List @Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @return nothing
def reorderList(self, head):
if not head or not head.next: return head
#find the middle node
slow=fast=ListNode(0)
slow.next=head
n=0#length of the rear half of the linked list
while fast and fast.next:
n+=1
slow=slow.next
fast=fast.next.next
if not fast:
n=n-1
mid=slow
rear=mid.next
mid.next=None
dummy=ListNode(0)
for i in range(n):
temp=dummy.next
dummy.next=rear
rear=rear.next
dummy.next.next=temp
crt=head
insert_node=dummy.next
for i in reversed(range(n)):
temp=crt.next
crt.next=insert_node
insert_node=insert_node.next
crt.next.next=temp
crt=temp
return head
Leetcode: Restore IP Addresses @Python
class Solution:
# @param s, a string
# @return a list of strings
def restoreIpAddresses(self, s):
n=len(s)
rst=[(0,[])]
for i in range(4):
newlist=[]
for elem in rst:
if (4-i)*3>=n-elem[0]:
for k in range(1,4):
if elem[0]+k<=n and (s[elem[0]]!='0' or k==1) and 0<=int(s[elem[0]:elem[0]+k])<=255:
newlist.append((k+elem[0],elem[1]+[s[elem[0]:elem[0]+k]]))
rst=newlist
res=[]
for elem in rst:
if elem[0]==n:
res.append('.'.join(elem[1]))
return res
Leetcode: Multiply Strings @Python
class Solution:
# @param num1, a string
# @param num2, a string
# @return a string
def multiply(self, num1, num2):
n=len(num1)
m=len(num2)
num1=[int(i) for i in reversed(num1)]
num2=[int(i) for i in reversed(num2)]
if n*m==0:
return None
elif num1==[0] or num2==[0]:
return '0'
rst=[0]*(m+n)
for i in range(n):
for j in range(m):
a2,a1=divmod(num1[i]*num2[j],10) #c1,c2<=1
c1,rst[i+j]=divmod(a1+rst[i+j],10)
c2,rst[i+j+1]=divmod(a2+c1+rst[i+j+1],10)
k=2
while c2:
c2,rst[i+j+k]=divmod(c2+rst[i+j+k],10)
k+=1
if rst[n+m-1]:
return ''.join(map(str,reversed(rst)))
else:
return ''.join(map(str,reversed(rst[:n+m-1])))
Leetcode: Sort List @Python
class Solution:
def sortList(self, head):
# QuickSort
len = 0
tail = head
while tail != None:
len += 1
tail = tail.next
pivot = head
return self.partition(head, len)
def partition(self, head, len):
if len<2:
return head
pivot = head
r_pivot = pivot
tail = head
head = ListNode(0)
left = head
l = 0
lr = 0
stall = 0
l_len = 0
r_len = len-1
while tail.next != None and l<len-1:
if tail.next.val < pivot.val:
left.next = tail.next
left = left.next
tail.next = tail.next.next
r_len -= 1
l_len += 1
lr += 1
left.next = pivot
elif tail.next.val > pivot.val:
tail = tail.next
elif tail.next.val == pivot.val:
self.swap_nodes(r_pivot, r_pivot.next, tail, tail.next)
lr += 1
stall = l-lr
if r_pivot == tail:
tail = r_pivot.next
r_pivot = r_pivot.next
r_len -= 1
if stall>0:
stall -= 1
else:
l += 1
left.next = pivot
head_l = self.partition(head.next, l_len)
head_r = self.partition(r_pivot.next, r_len)
head.next = head_l
r_pivot.next = head_r
return head.next
def swap_nodes(self, x, a, y, b):
x.next = b
y.next = a
temp = a.next
a.next = b.next
b.next = temp
Leetcode: Insert Interval @Python
class Solution:
# @param intervals, a list of Intervals
# @param newInterval, a Interval
# @return a list of Interval
def insert(self, intervals, newInterval):
ans, inserted = [], False
for i in range(len(intervals)):
if intervals[i].end < newInterval.start:
ans.append(intervals[i])
elif intervals[i].start > newInterval.end:
if not inserted:
inserted = True
ans.append(newInterval)
ans.append(intervals[i])
else:
newInterval.start = min(newInterval.start, intervals[i].start)
newInterval.end = max(newInterval.end, intervals[i].end)
if len(ans) == 0 or newInterval.start > ans[-1].end:
ans.append(newInterval)
return ans
Leetcode: Spiral Matrix @Python
class Solution:
# @param matrix, a list of lists of integers
# @return a list of integers
def spiralOrder(self, matrix):
rst=[]
m=len(matrix)
if m>0:
n=len(matrix[0])
else:
return rst
up=0
down=m-1
left=0
right=n-1
while up<=down and left<=right:
rst.extend(matrix[up][left:right+1])
up+=1
if up<=down:
for i in range(up,down+1): rst.append(matrix[i][right])
right-=1
else:
break
if left<=right:
for i in reversed(range(left,right+1)): rst.append(matrix[down][i])
down-=1
else:
break
if down>=up:
for i in reversed(range(up,down+1)): rst.append(matrix[i][left])
left+=1
else:
break
return rst
Leetcode: Longest Palindromic Substring @Python
class Solution:
# @return a string
def longestPalindrome(self, s):
n=len(s)
inputstr=s
s=list(s)
i=0
L=2*n+1
#insert '#' into the string so that the even and odd palidrome are the same
while i<L:
s.insert(i,'#')
i+=2
right=0
P=[0]*L
mid=0
for i in range(1,L):
if i<right:
mirror=2*mid-i
if i+P[mirror]<right:
P[i]=P[mirror]
continue
else:
P[i]=right-i
j=P[i]+1
while 0<=i-j and i+j<L and s[i-j]==s[i+j]:
P[i]+=1
j+=1
mid=i
right=mid+P[i]
index,maxlen=max(enumerate(P),key=operator.itemgetter(1))
seq=int(index//2-P[index]// 2)
rst=inputstr[seq:seq+P[index]]
return rst
Leetcode: Merge Intervals @Python
# Definition for an interval.
# class Interval:
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution:
# @param intervals, a list of Interval
# @return a list of Interval
def merge(self, intervals):
intervals=sorted(intervals,key=lambda x:x.start)
n=len(intervals)
if not n: return []
rst=[intervals[0]]
i=0
for i in range(1,n):
if rst[-1].end<intervals[i].start:
rst.append(intervals[i])
else:
temp=Interval(rst[-1].start,max(rst[-1].end,intervals[i].end))
rst.pop()
rst.append(temp)
return rst
Leetcode: Sudoku Solver @Python
class Solution:
# @param board, a 9x9 2D array
# Solve the Sudoku by modifying the input board in-place.
# Do not return any value.
def solveSudoku(self, board):
lt, rt, bt = [0] * 9, [0] * 9, [0] * 9
self.dt = {}
for i in range(9): self.dt[1<<i] = chr(ord('1')+i)
for i in range(9):
board[i] = list(board[i])
for j in range(9):
if (board[i][j] == '.'):
continue;
num = ord(board[i][j]) - ord('1')
lt[i] |= 1 << num
rt[j] |= 1 << num
bt[j//3*3+i//3] |= 1 << num
self.dfs(board, 0, lt, rt, bt)
board = [''.join(s) for s in board]
def dfs(self, board, p, lt, rt, bt):
while p < 81 and board[p//9][p%9] != '.':
p += 1
if p == 81:
return True
i, j, k = p//9, p%9, p%9//3*3+p//9//3
can = (~(lt[i]|rt[j]|bt[k])) & ((1<<9)-1)
while can:
num = can&-can
board[i][j] = self.dt[num]
lt[i] |= num
rt[j] |= num
bt[k] |= num
if self.dfs(board, p + 1, lt, rt , bt):
return True
board[i][j] = '.'
lt[i] &= ~num
rt[j] &= ~num
bt[k] &= ~num
can -= num
return False
Leetcode: Word Break @Python
class Solution:
# @param s, a string
# @param dict, a set of string
# @return a boolean
def wordBreak(self, s, dict):
n=len(s)
dp=[False for i in range(n)]
for i in range(1,n+1):
if s[:i] in dict:
dp[i-1]=True
for j in range(1,i):
if dp[j-1] and s[j:i] in dict:
dp[i-1]=True
return dp[n-1] if n>0 else '' in dict
Leetcode: Largest Rectangle in Histogram @Python
class Solution:
# @param height, a list of integer
# @return an integer
def largestRectangleArea(self, height):
height.insert(0,0)
height.append(0)
n=len(height)
stack=[0]
maxRec=0
for i in range(1,n):
while height[i]<height[stack[-1]]:
k=stack.pop()
newarea=(i-1-stack[-1])*height[k]
if newarea>maxRec:
maxRec=newarea
stack.append(i)
return maxRec
Leetcode: Maximal Rectangle @Python
class Solution:
# @param matrix, a list of lists of 1 length string
# @return an integer
def largestRectangleArea(self, height):
height.insert(0,0)
height.append(0)
n=len(height)
stack=[0]
maxRec=0
for i in range(1,n):
while height[i]<height[stack[-1]]:
k=stack.pop()
newarea=(i-1-stack[-1])*height[k]
if newarea>maxRec:
maxRec=newarea
stack.append(i)
height.pop()
height.pop(0)
return maxRec
def maximalRectangle(self, matrix):
maxRec=0
m=len(matrix)
if m>0:
n=len(matrix[0])
else:
return 0
height=[[0 for i in range(n)] for j in range(m)]
for i in range(m):
for j in range(n):
if i==0:
height[i][j]=int(matrix[i][j])
elif matrix[i][j]=='0':
height[i][j]=0
else :
height[i][j]=height[i-1][j]+1
maxRec=max(maxRec,self.largestRectangleArea(height[i]))
return maxRec
Leetcode: 4Sum @Python
class Solution:
# @return a list of lists of length 4, [[val1,val2,val3,val4]]
def fourSum(self, num, target):
n=len(num)
D={}
A=sorted(num)
rst=[]
for i in range(n-1):
for j in range(i+1,n):
psum=A[i]+A[j]
if psum in D:
if [i,j] not in D[psum]:
D[psum]+=[[i,j]]
else:
D[psum]=[[i,j]]
if target-psum in D:
for elem in D[target-psum]:
if (i not in elem) and (j not in elem):
temp=sorted([A[i],A[j],A[elem[0]],A[elem[1]]])
if temp not in rst:
rst.append(temp)
return rst
Leetcode: Implement strStr() @Python
class Solution:
# @param haystack, a string
# @param needle, a string
# @return a string or None
# @KMP algorithms
def ComputePrefixFunction(self, needle):
Pi = [0 for i in range(len(needle))]
m = len(needle)
Pi[0] = 0
k = 0
for q in range(1, m):
while k > 0 and needle[k] != needle[q]:
k = Pi[k - 1]
if needle[k] == needle[q]:
k = k + 1
Pi[q] = k
return Pi
def strStr(self, haystack, needle):
n = len(haystack)
m = len(needle)
if m == 0:
return haystack
Pi = self.ComputePrefixFunction(needle)
q = 0
for i in range(0, n):
while q > 0 and needle[q] != haystack[i]:
q = Pi[q - 1]
if needle[q] == haystack[i]:
q = q + 1
if q == m:
return haystack[i - m + 1:]
return None
Leetcode: Merge k Sorted Lists @Python
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param a list of ListNode
# @return a ListNode
def mergeKLists(self, lists):
heap = [(node.val, node) for node in lists if node]
heapq.heapify(heap)
curr=head = ListNode(0)
while heap:
curr.next= heapq.heappop(heap)[1]
curr = curr.next
if curr.next: heapq.heappush(heap, (curr.next.val, curr.next))
return head.next
Leetcode: Permutation Sequence @Python
class Solution:
# @return a string
def getPermutation(self, n, k):
rst=''
crt=k-1
num=[str(i+1) for i in range(n)]
for i in reversed(range(n)):
digit=num[crt//math.factorial(i)]
if crt!=0:
rst=rst+digit
num.remove(digit)
else:
rst=rst+''.join(num)
break
crt=crt%math.factorial(i)
return rst
Leetcode: Rotate List @Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @param k, an integer
# @return a ListNode
def rotateRight(self, head, k):
if not head: return None
test=head
n=1
while test.next:
test=test.next
n+=1
test.next=head
for i in range(n-k%n):
test=test.next
rst=test.next
test.next=None
return rst
Leetcode: Best Time to Buy and Sell Stock III @Python
Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Recall that the problem Best Time Buy and Sell Stock solved the problem with one transaction. This problem is just the sum of the previous problem for day 1 to day i and that for day i to the end. Recording the maximum of all the sum profits for each i-th day will render the result. For each sub-problem of the i-th day, the time complex is O(n), and the problem III is O(n^2). We can optimize by construct two arrays of the maximum one-transaction profit for day 1 to day i and that for day i to the end. Thus, we do not need to re-calculate two parts of the summation every single time. The optimized time complexity is O(n).
class Solution:
# @param prices, a list of integer
# @return an integer
def maxProfit(self, prices):
n=len(prices)
if not prices: return 0
mpf=[0 for i in range(n)] #max profit for the first transaction. forward
mpb=[0 for i in range(n)] #max profit for the last transaction. backwrd
low_price=prices[0]
high_price=prices[-1]
for i in range(1,n):
low_price=min(low_price,prices[i])
mpf[i]=max(mpf[i-1],prices[i]-low_price)
for i in reversed(range(n-1)):
high_price=max(high_price,prices[i])
mpb[i]=max(mpb[i+1],high_price-prices[i])
Mprofit=0
for i in range(n-1):
Mprofit=max(Mprofit,mpf[i]+mpb[i])
return Mprofit
Leetcode: Longest Substring Without Repeating Characters @Python
class Solution:
# @return an integer
def lengthOfLongestSubstring(self, s):
start=0
n=len(s)
substr=''
maxlen=0
for end in range(n):
if s[end] not in substr:
substr+=s[end]
else:
substr=''
maxlen=max(maxlen,end-start)
for i in xrange(start,end):
if s[end]==s[i]:
start=i+1
substr=s[start:end+1]
break
maxlen=max(maxlen,n-start)
return maxlen
Leetcode: Sqrt(x) @Python
class Solution:
# @param x, an integer
# @return an integer
def sqrt(self, x):
a=1000.0#guess
new_a=(a*1.0+x/a)/2
while int(new_a)!=int(a):
a=new_a
new_a=(a*1.0+x/a)/2
return int(a)
Leetcode: First Missing Positive @Python
class Solution:
# @param A, a list of integers
# @return an integer
def firstMissingPositive(self, A):
n=len(A)
if n==0: return 1
for i in xrange(n):
while A[i]>0 and A[i]<=n and A[i]!=i+1 and A[i]!=A[A[i]-1]:
temp=A[i]
A[i]=A[A[i]-1]
A[temp-1]=temp
for i in xrange(n):
if A[i]!=i+1:
missing=i+1
return missing
return n+1
Leetcode: Scramble String @Python
class Solution:
# @return a boolean
def isScramble(self, s1, s2):
if len(s1)!=len(s2): return False
if s1==s2: return True
l1=list(s1); l2=list(s2)
l1.sort();l2.sort()
if l1!=l2: return False
length=len(s1)
for i in range(1,length):
if self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:]): return True
if self.isScramble(s1[:i],s2[length-i:]) and self.isScramble(s1[i:],s2[:length-i]): return True
return False
Leetcode: Clone Graph @Python
# Definition for a undirected graph node
# class UndirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
# dps
def cloneGraph(self, node):
if not node: return None
def dfs(input, dic):
if input in dic: return dic[input]
newnode=UndirectedGraphNode(input.label)
dic[input]=newnode
for neighbor in input.neighbors:
newnode.neighbors.append(dfs(neighbor,dic))
return newnode
return dfs(node,{})
Leetcode: Valid Palindrome @Python
class Solution:
# @param s, a string
# @return a boolean
def isPalindrome(self, s):
pattern = re.compile('[\W_]+')
A=pattern.sub('', s.lower())
if A==A[::-1]:
return True
else:
return False
Leetcode: Add Two Numbers @Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @return a ListNode
def addTwoNumbers(self, l1, l2):
num1,num2=0,0
digit=0
while l1:
num1+=l1.val*(10**digit)
l1=l1.next
digit+=1
digit=0
while l2:
num2+=l2.val*(10**digit)
l2=l2.next
digit+=1
numsum=num1+num2
numsum,val=divmod(numsum,10)
keephead=head=ListNode(val)
while numsum:
numsum,val=divmod(numsum,10)
crt=ListNode(val)
head.next=crt
head=crt
return keephead
Friday, September 12, 2014
Leetcode: Copy List with Random Pointer @Python
# Definition for singly-linked list with a random pointer.
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# @param head, a RandomListNode
# @return a RandomListNode
def copyRandomList(self, head):
if not head: return None
keephead=head
while head:
crt=RandomListNode(head.label)
crt.next=head.next
head.next=crt
head=crt.next
head=keephead
while head:
crt=head.next
if head.random:
crt.random=head.random.next
head=crt.next
newhead=keephead.next
head=keephead
while head:
crt=head.next
head.next=crt.next
if crt.next:
crt.next=crt.next.next
head=head.next
return newhead
Leetcode: Recover Binary Search Tree @Python
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a tree node
def recoverTree(self, root):
if not root: return None
pre=parent=f1=f2=None# dummy node
foundfirst=False
crt=root
while crt:
if crt.left:
pre=crt.left
while pre.right and pre.right!=crt:
pre=pre.right
if not pre.right:
pre.right=crt
crt=crt.left
else:
pre.right=None
if parent.val>crt.val:
if not foundfirst:
f1=parent
foundfirst=True
f2=crt
parent=crt
crt=crt.right
else:
if parent and parent.val>crt.val:
if not foundfirst:
f1=parent
foundfirst=True
f2=crt
parent=crt
crt=crt.right
if f1 and f2:
f1.val,f2.val=f2.val,f1.val
return root
Leetcode: Anagrams @Python
class Solution:
# @param strs, a list of strings
# @return a list of strings
def anagrams(self, strs):
dic={}
res=[]
for word in strs:
S_word=''.join(sorted(word))
dic[S_word]=[word] if S_word not in dic else dic[S_word]+[word]
for i in dic:
if len(dic[i])>1:
res+=dic[i]
return res
Leetcode: ZigZag Conversion @Python
class Solution:
# @return a string
def convert(self, s, nRows):
if nRows==1: return s
tmp=['' for i in range(nRows)]
index=-1; step=1
for i in range(len(s)):
index+=step
if index==nRows:
index-=2; step=-1
elif index==-1:
index=1; step=1
tmp[index]+=s[i]
return ''.join(tmp)
Leetcode: Combination Sum II @Python
class Solution:
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers
def combinationSum2(self, candidates, target):
A=sorted(candidates)
n=len(A)
stack=[([A[i]],i,A[i]) for i in range(n) if A[i]<target]
rst=[]
for i in A:
if i==target:
rst=[[i]]
break
while stack:
new_stack=[]
for i in stack:
for j in range(i[1]+1,n):
crt_sum=i[2]+A[j]
if crt_sum<target:
new_stack.append((i[0]+[A[j]],j,crt_sum))
elif crt_sum==target and (i[0]+[A[j]] not in rst):
rst.append(i[0]+[A[j]])
stack=new_stack[:]
return rst
Leetcode: Jump Game II @Python
class Solution:
# @param A, a list of integers
# @return an integer
def jump(self, A):
n=len(A)
reach=0
if n<=1: return 0
jumpNum=0
while True:
jumpNum+=1
for i in range(reach+1):
reach=max(reach, i+A[i])
if reach>=n-1:
return jumpNum
Leetcode: Distinct Subsequences @Python
class Solution:
# @return an integer
def numDistinct(self, S, T):
s=len(S)
t=len(T)
dp=[[0 for j in range(s+1)] for i in range(t+1)]
for j in range(s+1):
dp[0][j]=1
for j in range(1,s+1):
for i in range(1,min(j+1,t+1)):
if T[i-1]!=S[j-1]:
dp[i][j]=dp[i][j-1]
else:
dp[i][j]=dp[i-1][j-1]+dp[i][j-1]
return dp[t][s]
Leetcode: Reverse Nodes in k-Group @Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @param k, an integer
# @return a ListNode
def reverse(self, start, end):
newhead=ListNode(0); newhead.next=start
while newhead.next!=end:
tmp=start.next
start.next=tmp.next
tmp.next=newhead.next
newhead.next=tmp
return [end, start]
def reverseKGroup(self, head, k):
if head==None: return None
nhead=ListNode(0); nhead.next=head; start=nhead
while start.next:
end=start
for i in range(k-1):
end=end.next
if end.next==None: return nhead.next
res=self.reverse(start.next, end.next)
start.next=res[0]
start=res[1]
return nhead.next
Leetcode: Remove Duplicates from Sorted List II @Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @return a ListNode
def deleteDuplicates(self, head):
nhead=pre=ListNode(0)
pre.next=head
crt=head
flag=0
while crt and crt.next:
if crt.next.val==crt.val:
crt.next=crt.next.next
flag=1
else:
if flag==0:
crt=crt.next
pre=pre.next
else:
pre.next=crt.next
crt=crt.next
flag=0
if flag==1:
pre.next=crt.next
return nhead.next
Leetcode: Permutations II @Python
class Solution:
# @param num, a list of integer
# @return a list of lists of integers
def permuteUnique(self, num):
n=len(num)
if n<=1:
return [num]
rst=[]
num.sort()
cur=0
pre=None
for cur in range(n):
if num[cur]==pre:
continue
pre=num[cur]
for i in self.permuteUnique(num[:cur]+num[cur+1:]):
rst.append(i+[num[cur]])
return rst
Leetcode: Insertion Sort List @Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @return a ListNode
def insertionSortList(self, head):
if not head: return None
nextH=ListNode(0)
nextH.next=head
crt=head
while crt.next:
if crt.next.val>=crt.val:
crt=crt.next
continue
cmpr=nextH.next
last=nextH
while crt.next.val>cmpr.val:
last=cmpr
cmpr=cmpr.next
temp=crt.next.next
last.next=crt.next
crt.next.next=cmpr
crt.next=temp
return nextH.next
Leetcode: Edit Distance @Python
class Solution:
# @return an integer
def minDistance(self, word1, word2):
n=len(word1)
m=len(word2)
M=max(n,m)
dp=[[M for i in range(m+1)] for j in range(n+1)]
for i in range(n+1):
dp[i][m]=n-i
for i in range(m+1):
dp[n][i]=m-i
for i in reversed(range(n)):
for j in reversed(range(m)):
if word1[i]==word2[j]:
dp[i][j]=dp[i+1][j+1]
else:
dp[i][j]=1+min(dp[i+1][j],dp[i][j+1],dp[i+1][j+1])
return dp[0][0]
Leetcode: Next Permutation @Python
class Solution:
# @param num, a list of integer
# @return a list of integer
def nextPermutation(self, num):
k=len(num)
if k==1:
return num
left=-1
for i in range(k-2,-1,-1):
if num[i]<num[i+1]:
left=i
break
for i in range(k-1,-1,-1):
if num[i]>num[left]:
right=i
break
if left>=0:
num[left],num[right]=num[right],num[left]
l=left+1
else:
l=0
while l<k-1:
num[l],num[k-1]=num[k-1],num[l]
l+=1
k-=1
return num
Leetcode: Gas Station @Python
class Solution:
# @param gas, a list of integers
# @param cost, a list of integers
# @return an integer
def canCompleteCircuit(self, gas, cost):
n=len(gas)
Sum=total=0
k=0
for i in range(n):
Sum+=gas[i]-cost[i]
total+=gas[i]-cost[i]
if Sum<0:
k=i+1
Sum=0
return k if total>=0 else -1
Leetcode: Validate Binary Search Tree @Python
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a boolean
def iterVBST(self,root,m,M):
if root==None: return True
if root.val>=M or root.val<=m: return False
return self.iterVBST(root.left,m,root.val) and self.iterVBST(root.right,root.val,M)
def isValidBST(self, root):
return self.iterVBST(root,-2147483648,2147483647)
Leetcode: Palindrome Partitioning @Python
class Solution:
# @param s, a string
# @return a list of lists of string
def isPalindrome(self, s):
pattern = re.compile('[\W_]+')
A=pattern.sub('', s.lower())
return A==A[::-1]
def partition(self, s):
n=len(s)
rst=[]
stack=[([],0)]
ptable=[[False for i in range(n)] for j in range(n)]
for i in range(n):
for j in range(i+1,n+1):
ptable[i][j-1]=self.isPalindrome(s[i:j])
i=0
while stack:
crt=[]
for i in stack:
if i[1]==n:
rst.append(i[0])
continue
j=i[1]+1
while j<=n:
if ptable[i[1]][j-1]==True:
temp=i[0]+[s[i[1]:j]]
crt.append((temp,j))
j+=1
stack=crt
return rst
Leetcode: Pow(x, n) @Python
class Solution:
# @param x, a float
# @param n, a integer
# @return a float
def pow(self, x, n):
if n==0:
return 1
elif n==1:
return x
elif n%2==0:
return pow(x*x,n/2)
else:
return pow(x*x,n/2)*x
Leetcode: Add Binary @Python
class Solution:
# @param a, a string
# @param b, a string
# @return a string
def addBinary(self, a, b):
n=len(a)
m=len(b)
if n>=m:
c=a[:n-m]
else:
c=b[:m-n]
flag=0
rst=''
i=-1
while -i<=min(n,m):
if a[i]=='1' and b[i]=='1':
if flag==0:
rst='0'+rst
else:
rst='1'+rst
flag=1
elif a[i]=='0' and b[i]=='0':
if flag==0:
rst='0'+rst
else:
rst='1'+rst
flag=0
elif flag==0:
rst='1'+rst
flag=0
else:
rst='0'+rst
flag=1
i-=1
for i in reversed(range(abs(n-m))):
if c[i]=='1' and flag==1:
rst='0'+rst
flag=1
elif c[i]=='0' and flag==1:
rst='1'+rst
flag=0
else:
rst=c[i]+rst
flag=0
if flag==1:
rst='1'+rst
return rst
Leetcode: N-Queens @Python
class Solution:
# @return a list of lists of string
def under_attack(self,col, queens):
return col in queens or any(abs(col - x) == len(queens)-i for i,x in enumerate(queens))
def solve(self,n):
solutions = [[]]
for row in range(n):
solutions = (solution+[i]
for solution in solutions # first for clause is evaluated immediately,
# so "solutions" is correctly captured
for i in range(n)
if not self.under_attack(i, solution))
return solutions
def solveNQueens(self, n):
slt=[]
for j in self.solve(n):
if len(j)==n:
slt.append(list('.'*i+'Q'+'.'*(n-1-i) for i in j))
return slt
Leetcode: Reverse Linked List II @Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @param m, an integer
# @param n, an integer
# @return a ListNode
def reverseBetween(self, head, m, n):
if not head: return None
before=ListNode(0)
before.next=head
fast=slow=head
for i in range(m-1):
before=slow
slow=slow.next
for i in range(n-1):
fast=fast.next
for i in range(n-m):
before.next=slow.next
slow.next=fast.next
fast.next=slow
slow=before.next
return before.next if m==1 else head
Leetcode: Letter Combinations of a Phone Number @Python
class Solution:
# @return a list of strings, [s1, s2]
def letterCombinations(self, digits):
dic={'1':'','2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz','0':''}
rst=['']
for i in digits:
rst=[j+k for j in rst for k in dic[i]]
return rst
Leetcode: Construct Binary Tree from Inorder and Postorder Traversal @Python
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param inorder, a list of integers
# @param postorder, a list of integers
# @return a tree node
def buildTree(self, inorder, postorder):
if not inorder: return None
root=TreeNode(postorder[-1])
rootidx=inorder.index(postorder[-1])
root.left=self.buildTree(inorder[:rootidx],postorder[:rootidx])
root.right=self.buildTree(inorder[1+rootidx:],postorder[rootidx:-1])
return root
Leetcode: Construct Binary Tree from Preorder and Inorder Traversal @Python
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param preorder, a list of integers
# @param inorder, a list of integers
# @return a tree node
def buildTree(self, preorder, inorder):
if not inorder: return None
root=TreeNode(preorder[0])
rootidx=inorder.index(preorder[0])
root.left=self.buildTree(preorder[1:1+rootidx],inorder[:rootidx])
root.right=self.buildTree(preorder[1+rootidx:],inorder[1+rootidx:])
return root
Leetcode: Combination Sum @Python
class Solution:
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers
def combinationSum(self, candidates, target):
A=sorted(candidates)
stack=[[i] for i in A if i<target]
rst=[]
for i in A:
if i==target:
rst=[[i]]
break
while stack:
new_stack=[]
for i in stack:
for j in A:
if i[-1]>j:
continue
else:
crt_sum=sum(i+[j])
if crt_sum<target:
new_stack.append(i+[j])
elif crt_sum==target:
rst.append(i+[j])
stack=new_stack[:]
return rst
Leetcode: Binary Tree Zigzag Level Order Traversal @Python
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a list of lists of integers
def zigzagLevelOrder(self, root):
crt=[root]
rst=[]
if not crt:
return []
flag=1
while crt!=[None]*len(crt):
if flag==1:
rst.append([i.val for i in crt])
else:
temp=[i.val for i in crt]
temp.reverse()
rst.append(temp)
nextlvl=[]
for i in crt:
if i.left:
nextlvl.append(i.left)
if i.right:
nextlvl.append(i.right)
crt=nextlvl
flag*=-1
return rst
Leetcode: Triangle @Python
class Solution:
# @param triangle, a list of lists of integers
# @return an integer
def minimumTotal(self, triangle):
n=len(triangle)
if n==0:return 0
sv=[triangle[0][0]]
for i in range(1,n):# given sv for row i, calculate sv for row i+1
new_sum=[0 for x in range(i+1)]
for j in range(i+1):
if j==0:
new_sum[0]=triangle[i][0]+sv[0]
elif j==i:
new_sum[i]=triangle[i][i]+sv[i-1]
else:
new_sum[j]=min(triangle[i][j]+sv[j-1],triangle[i][j]+sv[j])
sv=new_sum[:]
return min(sv)
Leetcode: Partition List @Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @param x, an integer
# @return a ListNode
def partition(self, head, x):
if not head: return head
nless=less=ListNode(0)
ngeq=geq=ListNode(0)
pre,crt=None,head
while crt:
pre=crt
crt=crt.next
if pre.val<x:
less.next=pre
less=pre
less.next=None
else:
geq.next=pre
geq=pre
geq.next=None
less.next=ngeq.next
return nless.next
Leetcode: Path Sum II @Python
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @param sum, an integer
# @return a list of lists of integers
def pathSum(self, root, sum):
stack=[]
if root:
stack=[([root],root.val)]
else:
return []
rst=[]
while stack:
crt=[]
for i in stack:
if i[0][-1].left==None and i[0][-1].right==None and i[1]==sum:
rst.append([j.val for j in i[0]])
if i[0][-1].left:
temp=i[0]+[i[0][-1].left]
crt.append((temp,i[1]+i[0][-1].left.val))
if i[0][-1].right:
temp=i[0]+[i[0][-1].right]
crt.append((temp,i[1]+i[0][-1].right.val))
stack=crt[:]
return rst
Leetcode: Subsets II @Python
class Solution:
# @param num, a list of integer
# @return a list of lists of integer
def subsetsWithDup(self, S):
res = [[]]
for e in sorted(S):
res = res+[l+[e] for l in res if l+[e] not in res]
return res
Leetcode: 3Sum Closest @Python
class Solution:
# @return an integer
def threeSumClosest(self, num, target):
A=sorted(num)
n=len(A)
rst=[A[0],A[1],A[2]]
crt=abs(A[0]+A[1]+A[2]-target)
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:
gap=A[i]+A[j]+A[k]-target
if abs(gap)<crt:
rst=[A[k],A[i],A[j]]
crt=abs(gap)
while j>i:
if A[i]+A[j]+A[k]-target>0:
j-=1
if A[j]!=A[j+1]:
break
else:
i+=1
if A[i]!=A[i-1]:
break
return sum(rst)
Leetcode: Jump Game @Python
class Solution:
# @param A, a list of integers
# @return a boolean
def canJump(self, A):
crt=-1
for i in range(len(A)-1):
crt=max(crt-1,A[i])
if crt==0:
return False
return True
Leetcode: Longest Common Prefix @Python
class Solution:
# @return a string
def longestCommonPrefix(self, strs):
if len(strs) == 0:
return ""
for i in range(len(strs[0])):
for j in range(len(strs)):
if len(strs[j]) <= i or strs[j][i] != strs[0][i]:
return (strs[0])[0 : i]
return strs[0]
Leetcode: Convert Sorted List to Binary Search Tree @Python
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a list node
# @return a tree node
def AtoBST(self,A):
n=len(A)
if n==0:
return None
else:
ml=n//2
A[ml].right=self.AtoBST(A[ml+1:])
A[ml].left=self.AtoBST(A[:ml])
return A[ml]
def sortedListToBST(self, head):
A=[]
while head:
A.append(TreeNode(head.val))
head=head.next
return self.AtoBST(A)
Leetcode: Unique Binary Search Trees II @Python
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
#@return a list of tree node with value range from start to end
def TreeGen(self, start,end):
if start>end:
return [None]
rst=[]
for rVal in range(start, end+1):
leftlist=self.TreeGen(start,rVal-1)
rightlist=self.TreeGen(rVal+1,end)
for i in leftlist:
for j in rightlist:
root=TreeNode(rVal)
root.left=i
root.right=j
rst.append(root)
return rst
# @return a list of tree node
def generateTrees(self, n):
return self.TreeGen(1,n)
Leetcode: Count and Say @Python
class Solution:
# @return a string
def itergen(self,a):
k,last,result = 1,a[0],''
for i in range(1,len(a)):
if last==a[i]:k+=1
else:
result = result+str(k)+last
k=1
last = a[i]
result = result+str(k)+last
return result
def countAndSay(self, n):
if n==0: return ''
rst='1'
for i in range(n-1):
rst=self.itergen(rst)
return rst
Leetcode: Search for a Range @Python
class Solution:
# @param A, a list of integers
# @param target, an integer to be searched
# @return a list of length 2, [index1, index2]
def searchRange(self, A, target):
left,right,idx=0,len(A)-1,-1
while left<=right:
mid=(left+right)//2
if A[mid]==target:
idx=mid
break
elif A[mid]<target:
left=mid+1
elif A[mid]>target:
right=mid-1
if idx==-1:
return [-1,-1]
rl,rr=left,right
ml=mr=mid
while rl<ml:
mml=(rl+ml)//2
if A[mml]==target:
ml=mml
else:
rl=mml+1
while rr>mr:
mmr=-((-rr-mr)//2)
if A[mmr]==target:
mr=mmr
else:
rr=mmr-1
return [rl, rr]
Leetcode: Unique Paths II @Python
class Solution:
# @param obstacleGrid, a list of lists of integers
# @return an integer
def uniquePathsWithObstacles(self, obstacleGrid):
row=len(obstacleGrid)
col=len(obstacleGrid[0])
if row*col==0:
return 1
dp=[[0 for i in range(col)] for j in range(row)]
for i in range(row):
if obstacleGrid[i][0]==0:
dp[i][0]=1
else:
break
for j in range(col):
if obstacleGrid[0][j]==0:
dp[0][j]=1
else:
break
for i in range(1,row):
for j in range(1,col):
if obstacleGrid[i][j]==1:
dp[i][j]=0
else:
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[row-1][col-1]
Subscribe to:
Posts
(
Atom
)