My Leetcode Solutions
[TOC]
Week 1
"""
2Sum
Author: smtech
Method: Hash Table
History: 2015-09-07
"""
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hashtb = dict() # hash table
for i in xrange(len(nums)):
diff = target - nums[i]
# if you can find diff at hash table, return
if diff in hashtb:
return [hashtb.get(diff)+1, i+1]
else: # if you can't find diff, add to hash table
hashtb[nums[i]] = i
return []
"""
3Sum
"""
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# ATTENTIONS!
# Pass duplicte item in order to speed up algorithm!
n = len(nums)
if n < 3:
return []
# sort list. n*log n
nums.sort()
triplets = list() # output list
triplet = list() # triple
s = 0
low = 0 # two pointers
high = 0
for i in xrange(n-2):
if i>0 and nums[i] == nums[i-1]: # pass duplicate
continue
low = i+1
high = n-1
while low < high:
s = nums[i] + nums[low] + nums[high]
if s == 0:
triplet = [nums[i],nums[low],nums[high]]
triplets.append(triplet)
while low < high and nums[low] == nums[low+1]: # pass duplicate
low += 1
while low < high and nums[high] == nums[high-1]: # pass duplicate
high -= 1
if s < 0:
low += 1
else:
high -= 1
return triplets
"""
3Sum Closest
"""
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
n = len(nums)
nums = sorted(nums)
diff = 1000000
output = 0
for i in xrange(n-2):
low = i + 1
high = n - 1
while low < high:
s = nums[low] + nums[high] + nums[i]
if abs(target - s) < diff:
diff = abs(target-s)
output = s
if (target < s):
high -= 1
else:
low += 1
return output
"""
Longest substring without repeated char
"""
class Solution:
# @return an integer
def lengthOfLongestSubstring(self, s):
#without repeat char
max_len = 0 # record max length
curr_len = 0 # record current length
charmap = dict() # hash map
for i in xrange(len(s)):
ch = s[i]
curr_len += 1
# if repeat, refresh current char
if charmap.get(ch) !=None:
curr_len = min(curr_len, i-charmap.get(ch))
charmap[ch] = i # hash map add none-repeat char
max_len = max(curr_len, max_len)
return max_len
"""
Longest palindrome substring
Time: O(n^2), time exceeded, not accept yet.
"""
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
s1 = self.longestPalindromeOdd(s)
s2 = self.longestPalindromeEven(s)
if len(s1) > len(s2):
return s1
return s2
def longestPalindromeOdd(self,s): # Odd length palindrom
mx, ex, c = 0, 0, 0
for i in xrange(len(s)):
ex = 0
while (i-ex >= 0) and (i+ex <= len(s)-1) and (s[i-ex]==s[i+ex]):
if ex > mx:
c = i
mx = ex
ex += 1
return s[c-mx: c+mx+1]
def longestPalindromeEven(self,s): # Even lenght palindrom
mx, ex, c = 0, 0, 0
for i in xrange(1,len(s)):
ex = 0
while (i-1-ex >= 0) and (i+ex <= len(s)-1) and (s[i-1-ex]==s[i+ex]):
if ex > mx:
c = i
mx = ex
ex += 1
return s[c-mx-1: c+mx+1]
if __name__=='__main__':
test = Solution()
s = "aabbbaa"
print test.longestPalindrome(s)
Week 2
"""
Swap Nodes in Pairs
"""
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None or head.next == None:
return head
p1 = head
p2 = head.next
pre = ListNode(0) # previous node
pre.next = head
head = pre # fake header
while True:
# swap 2 node
pre.next = p2
p1.next = p2.next
p2.next = p1
pre = p1
# if only 1 node or non node left, break and finish
if p1.next == None:
break
elif p1.next.next==None:
break
# shift to next
p1 = p1.next
p2 = p1.next
return head.next # first node is a fake header
"""
Add Binary
"""
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
if len(a) > len(b):
max_len = len(a)
min_len = len(b)
longstr = a
shortstr = b
else:
max_len = len(b)
min_len = len(a)
longstr = b
shortstr = a
res = ''
carry = 0
ia, ib = 0, 0
i, i2 = min_len -1 , max_len -1
while i >= 0:
ia, ib = int(shortstr[i]), int(longstr[i2])
res += str( ia ^ ib ^ carry) # xor
carry = (ia&ib)|(ia&carry)|(ib&carry) # calculate carry
i-=1
i2-=1
while i2 >= 0:
ia = int(longstr[i2])
res += str( ia ^ carry)
carry = carry & ia
i2-=1
if carry > 0:
res += str(carry)
return res[::-1]
'''
Plus One
'''
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
carry = 1
for i in xrange(len(digits)-1, -1, -1):
if carry + digits[i] == 10:
digits[i] = 0
carry = 1
else:
digits[i] += carry
carry = 0
if carry > 0:
return [1] + digits
return digits
"""
Valid Anagram
"""
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if sorted(s) == sorted(t):
return True
return False
"""
Group Anagram
"""
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
res = list()
strdict = dict()
for stri in strs:
astr = ''.join(sorted(stri))
if astr in strdict:
idx = strdict.get(astr)
res[idx].append(stri)
else:
strdict[astr] = len(res)
res.append([stri])
for i in xrange(len(res)-1):
res[i] = sorted(res[i])
return res
"""
Spiral Matrix
Using recursive method:
1. First outter round
2. Then inner sub-matrix
"""
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
m = len(matrix)
if m == 0: # in case empty: [ ]
return []
n = len(matrix[0])
if n == 0: # in case empty: [ [],[],[],[],..., [] ]
return []
if m==1: # single row
return matrix[0]
if n==1: # single col
return [x[0] for x in matrix]
res = list()
for j in xrange(n-1):
res.append(matrix[0][j])
print res
for i in xrange(m-1):
res.append(matrix[i][n-1])
print res
for j in xrange(n-1, 0, -1):
res.append(matrix[m-1][j])
print res
for i in xrange(m-1, 0, -1):
res.append(matrix[i][0])
print res
inner = list()
for row in matrix[1:m-1]:
inner.append(row[1:n-1])
print 'inner',inner
return res + self.spiralOrder(inner[:]) # recursive
Week 3
"""
Next Permutation
"""
class Solution(object):
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
if len(nums) <= 1:
return
i = len(nums) -1
j = i - 1
while nums[i] <= nums[j] and j >=0:
j -= 1
i -= 1
if j >= 0:
i = len(nums) -1
while nums[j] >= nums[i]: # find a smallest num on right but bigger than nums[j] (merely bigger than nums[j])
i -= 1
nums[i], nums[j] = nums[j], nums[i]
k = j +1
else:
k = 0 # if j ==-1, reverse all
i = len(nums) -1
while k < i:
nums[k], nums[i] = nums[i], nums[k]
k += 1
i -= 1
"""
Permutation
"""
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) <= 1:
return [nums]
nums.sort()
res = list()
res.append(nums[:])
while True:
i = len(nums) - 1
j = i - 1
while nums[i] < nums[j] and j>= 0: # Find nums[i] > nums[j]
i, j = i-1, j-1
if j < 0:
break
i = len(nums) -1
while nums[i] < nums[j]: # Find nums[i] > nums[j]
i -= 1
# nums[i] merely bigger than nums[j]
nums[i], nums[j] = nums[j], nums[i]
i = len(nums) - 1
k = j+1
while k < i:
nums[k], nums[i] = nums[i], nums[k]
k, i = k+1, i-1
res.append(nums[:])
return res
if __name__ == '__main__':
s = Solution()
print s.permute([1,2,3])
"""
Permutaion II
"""
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) <= 1:
return [nums]
nums.sort()
res = list()
res.append(nums[:])
while True:
i = len(nums) - 1
j = i - 1
while nums[i] <= nums[j] and j>= 0: # Find nums[i] > nums[j]
i, j = i-1, j-1
if j < 0:
break
i = len(nums) -1
while nums[i] <= nums[j]: # Find nums[i] > nums[j]
i -= 1
# nums[i] merely bigger than nums[j]
nums[i], nums[j] = nums[j], nums[i]
i = len(nums) - 1
k = j+1
while k < i:
nums[k], nums[i] = nums[i], nums[k]
k, i = k+1, i-1
print nums
res.append(nums[:])
return res
"""
Sort Colors
"""
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
"""
"method 1
"Count colors
"""
# redcnt, whitecnt, bluecnt = 0, 0, 0
# for obj in nums:
# if obj == 0:
# redcnt += 1
# elif obj == 1:
# whitecnt += 1
# else:
# bluecnt += 1
# for i in xrange(redcnt):
# nums[i] = 0
# for i in xrange(redcnt, redcnt+whitecnt):
# nums[i] = 1
# for i in xrange(redcnt+whitecnt, len(nums)):
# nums[i] = 2
"""
"method 2
"One pass
"
"n0: end of 0(red)
"n1: start of unsorted colors
"n2: start of 2(blue)
"""
n0, n1, n2 = 0, 0, len(nums)
while n1 < n2:
if nums[n1] == 0:
nums[n0], nums[n1] = nums[n1], nums[n0]
n0 += 1
n1 += 1
elif nums[n1] == 1:
n1 += 1
else :
n2 -= 1
nums[n2], nums[n1] = nums[n1], nums[n2]
"""
Unique Binary Search Tree Numbers
"""
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
u_list = [1,1]
# Increase from
# 1
# 1 2
# 1 2 3
# 1 2 3 4
# 1 2 3 4 5
# ...
for i in xrange(2, n+1):
# For example, n = 5, calculate T(5)
# T(5) = 2*T(0)*T(4) + 2*T(1)*T(3) + T(2)*T(2)
# T(2n) = 2*T(0)*T(2n-1) + 2*T(1)*T(2n-2) + ... + 2*T(n)*T(n)
# T(2n+1) = 2*T(0)*T(2n) + 2*T(1)*T(2n-1) + ... + 2*T(n)*T(n) + T(n+1)*T(n+1)
u_sum = 0
for j in xrange(1, i/2+1):
left = j-1
right = i-j
u_sum += 2 * u_list[left] * u_list[right]
if i%2 == 1:
u_sum += u_list[i/2] * u_list[i/2]
u_list.append(u_sum)
return u_list[-1]
"""
Unique Binary Search Tree II (Generate)
"""
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
"""
None Recursive Solution
"""
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0:
return [None]
if n == 1:
root = TreeNode(1)
return [root]
btree = list()
# zero tree
btree.append([[None] for x in range(n+1)])
# One node tree
btree.append(list())
for i in xrange(1,n+1):
root = TreeNode(i)
btree[1].append([root])
for intval in xrange(1,n):
btree.append(list())
for i in xrange(0, n-intval):
print i, i + intval
j = i + intval
btree[intval+1].append(list())
btree[intval+1][i] = list()
for k in xrange(i,j+1):
for ltree in btree[k-i][i]:
# print j-k, k+1
for rtree in btree[j-k][k+1]:
root = TreeNode(k+1)
root.left = ltree
root.right = rtree
btree[intval+1][i].append(root)
return btree[-1][0]
if __name__ == '__main__':
s = Solution()
print len(s.generateTrees(5))
Week 4
"""
House Robber I
"""
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
if len(nums) <3:
return max(nums)
s = list()
s.append(nums[0])
s.append(max(nums[:2]))
max_rob = 0
for i in xrange(2,len(nums)):
max_rob = max(s[i-2]+nums[i], s[i-1])
s.append(max_rob)
return max_rob
"""
House Robber II
"""
class Solution(object):
"""
Reduce a circuit to a simple straight line
"""
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
if len(nums) <4:
return max(nums)
# Skip the first house or skip the last house
max_rob = max( self.rob_straight(nums[1:]),
self.rob_straight(nums[:-1]) )
return max_rob
def rob_straight(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
s = list()
s.append(nums[0])
s.append(max(nums[:2]))
max_rob = 0
for i in xrange(2,len(nums)):
max_rob = max(s[i-2]+nums[i], s[i-1])
s.append(max_rob)
return max_rob
"""
Decode Ways
"""
import re
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0:
return 0
# First few codes should not be '0', if, it is invalid!
if s[0] == '0':
return 0
# Should not contain '00...', invalid!!
ss = [x for x in s.split('00')]
if '' in ss:
return 0
# '10', '20' can be recognized as a single code
ss = re.split('10|20',s)
print ss
# Should not contain '30', '40', ..., '90', invalid!!
if '0' in ''.join(ss):
return 0
# The remaining code is pure non-zero
n = 1
for si in ss:
n = n * self.numDecodingsEach(si)
return n
def numDecodingsEach(self, s):
if len(s) < 3:
if s == '':
return 1
if int(s) > 26:
return 1
return max(1, len(s))
d = [1, 2]
if int(s[0:2]) > 26:
d[1] = 1
for i in xrange(2, len(s)):
d.append(0)
if int( s[i-1:i+1] ) > 26:
d[i] = d[i-1]
else:
d[i] = d[i-1] + d[i-2]
return d[-1]
if __name__ == '__main__':
s = Solution()
print s.numDecodings('100212485')
"""
Scramble String
"""
class Solution(object):
"""docstring for Solution"""
def isScramble(setf, s1, s2):
if len(s1) != len(s2):
return False
n = len(s1)
if n == 0:
return False
if n == 1:
return s1 == s2
# Memozie matrix
m = list()
m.append([])
for k in xrange(1, n+1):
m.append([])
for i in xrange(n-k+1):
m[k].append([])
for j in xrange(n-k+1):
m[k][i].append([])
m[k][i][j] = False
for i in xrange(n):
for j in xrange(n):
if s1[i] == s2[j]:
m[1][i][j] = True
for k in xrange(2, n+1):
for i in xrange(n-k+1):
for j in xrange(n-k+1):
for l in xrange(1, k):
m[k][i][j] = m[k][i][j] or \
(m[l][i][j] and m[k-l][i+l][j+l]) or \
(m[l][i][j+k-l] and m[k-l][i+l][j])
return m[n][0][0]
"""
Set Matrix Zeros
"""
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
m, n = 0, 0
m = len(matrix)
if m != 0:
n = len(matrix[0])
col = [1 for x in xrange(n)]
# row = [1 for x in xrange(m)]
row = 1
for i in xrange(m):
for j in xrange(n):
if matrix[i][j] == 0:
# row[i], col[j] = 0, 0
row, col[j] = 0, 0
if row == 0:
for c in xrange(n):
matrix[i][c] = 0
row = 1
for c in xrange(n):
if col[c] == 0:
for i in xrange(m):
matrix[i][c] = 0
Week 5
"""
Edit Distance
"""
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m = [ [0 for col in xrange(len(word2)+1)] for row in xrange(len(word1)+1)]
for j in xrange(len(word2)+1):
m[0][j] = j
for i in xrange(len(word1)+1):
m[i][0] = i
for i in xrange(1, 1+len(word1)):
for j in xrange(1, 1+len(word2)):
if word1[:i][-1] != word2[:j][-1]:
# 1.Replace 2.Word1 delete 3.Word2 delete
m[i][j] = min(m[i-1][j-1] + 1, m[i-1][j]+1, m[i][j-1]+1)
else:
m[i][j] = m[i-1][j-1]
for line in m:
print line
return m[-1][-1]
if __name__=='__main__':
s = Solution()
print s.minDistance("a","ab")
"""
Missing Number
Tag: bit manipulation
"""
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
bit = [0 for x in xrange(n+1)]
for v in nums:
bit[v] = 1
miss = 0
for i in xrange(len(bit)):
if bit[i] == 0:
miss = i
break
return miss
"""
First Missing Positive
"""
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
N = len(nums)
new_nums = [0 for x in xrange(N+1)]
for i in xrange(N):
# nums[i] should be from 1 to N
if nums[i] <= N and nums[i] > 0:
new_nums[nums[i]] = nums[i]
for i in xrange(1, N+1):
if new_nums[i] != i:
return i
return N+1
"""
Longest Valid Parentheses
"""
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
stack = list() # use to push string char's index
max_len = 0
for i in xrange(len(s)):
if stack and s[i] == ')':
if s[stack[-1]] == '(': # stack[-1] is index
stack.pop()
else:
stack.append(i)
# init, if stack is empty, low is -1
low = -1
# if stack is not empty, low is stack top
if stack:
low = stack[-1]
# caculate max length by using index
max_len = max(max_len, i - low)
else:
stack.append(i)
return max_len
"""
Largest Rectangle in Histogram
"""
class Solution(object):
def largestRectangleArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
stack = list() # push index
max_rec = 0
height.append(0) # in order to pop the rest stack
for i in xrange(len(height)):
while stack and (height[i] < height[stack[-1]]):
t = stack.pop()
if not stack: # stack is empty
low = 0
else:
low = stack[-1] + 1
max_rec = max(max_rec, height[t] * (i - low) )
stack.append(i)
# print stack
return max_rec
