leetcode write up for 61-90 problems
61. Rotate List
要考虑的特殊case比较多，listnode是share的，修改也会互相改变，但是head不同，所以我们要知道先改哪些。
class Solution(object):
def rotateRight(self, head, k):
if not head:
return None
if not head.next:
return head
pointer = head
count = 1
while pointer.next:# calculate the lenth of the total listNode
pointer = pointer.next
count+=1
rotateTimes = k % count #calculate the steps it have to ratate
if not k or not rotateTimes: #if k and steps is 0, return head
return head
slow = fast =tmp = head # slow, fast, head share the listNode,but they have different start head
for i in range(count - rotateTimes -1): #find the target's last element
slow = slow.next
for i in range(count-rotateTimes): #find the header for the target's element
tmp = tmp.next
while fast.next:
fast = fast.next # to make the last element connect with the firs element.
slow.next = None
fast.next = head
return tmp
62. Unique Paths
Router 要放在外面，是全局变量。
router = {}
class Solution(object):
def uniquePaths(self, m, n):
if m < 1 or n < 1:
return 0
elif m is 1 and n is 1:
return 1
elif (m, n) not in router:
router[(m,n)] = self.uniquePaths(m-1,n) + self.uniquePaths(m,n-1)
return router[(m,n)]
63. Unique Paths II
router是局部变量，不能放在外面，否则测试的时候会因为多个case，router不更新。但是放在里面会有问题，所以要用self。
class Solution(object):
def __init__(self):
self.router = {}
def dp(self,m,n,obstacleGrid):
if n < 1 or m < 1 or obstacleGrid[m-1][n-1] ==1 or obstacleGrid[0][0] == 1:
return 0
elif n == 1 and m ==1:
return 1
elif (m,n) not in self.router:
self.router[(m,n)] = self.dp(m-1,n,obstacleGrid)+self.dp(m,n-1,obstacleGrid)
return self.router[(m,n)]
def uniquePathsWithObstacles(self, obstacleGrid):
m = len(obstacleGrid)
n = len(obstacleGrid[0])
return self.dp(m,n,obstacleGrid)
64. Minimum Path Sum
class Solution(object):
def minPathSum(self, grid):
if not grid:
return 0
dp = [[float("inf")] * len(grid[0])]*len(grid)
for i in range(len(grid)):
for j in range(len(grid[0])):
if j == 0 and i ==0:
dp[i][j] = grid[i][j]
elif i == 0 :
dp[i][j] = grid[i][j] + dp[i][j-1]
elif j == 0:
dp[i][j] = grid[i][j] + dp[i-1][j]
else:
dp[i][j] = grid[i][j] + min(dp[i-1][j],dp[i][j-1])
return dp[len(grid)-1][len(grid[0])-1]
65. Valid Number
class Solution(object):
def isNumber(self, s):
try:
float(s)
return True
except:
return False
67. Add Binary
二进制转换，注意去掉’0b’。
class Solution(object):
def addBinary(self, a, b):
a1 = int(a,2)
b1 = int(b,2)
sum = a1 + b1
sum1 = bin(sum)
x = sum1.replace('0b','')
return x
69. Sqrt(x)
求平方很简单。注意余数舍去并且不能带浮点数，如ceil会精确一位。所以用int
import math
class Solution(object):
def mySqrt(self, x):
return int(math.sqrt(x))
70，Climbing Stairs
斐波拉切数列，很简单。
class Solution(object):
def climbStairs(self, n):
if n==1:
return 1
if n==2:
return 2
i = 3
x = 0
nums= [0] * (n+1)
nums[1] = 1
nums[2] = 2
while i <= n and i >2:
nums[i] = nums[i-1] + nums[i-2]
i +=1
return nums[n]
class Solution(object):
def simplifyPath(self, path):
res = []
pathList = path.split('/')
for item in pathList:
if item:
if item == '..' and res:
res.pop()
elif item != '.' and item != '':
res.append(item)
return '/'+'/'.join(res)
72. Edit Distance
class Solution:
def minDistance(self, word1, word2):
"""Dynamic programming solution"""
m = len(word1)
n = len(word2)
table = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
table[i][0] = i
for j in range(n + 1):
table[0][j] = j
print table
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
table[i][j] = table[i - 1][j - 1]
else:
table[i][j] = 1 + min(table[i - 1][j], table[i][j - 1], table[i - 1][j - 1])
return table[-1][-1]
73. Set Matrix Zeroes
class Solution(object):
def setZeroes(self, matrix):
tmp = []
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if matrix[row][col] == 0:
tmp.append([row,col])
for item in tmp:
matrix[item[0]] =[0] * len(matrix[0])
for j in range(len(matrix)):
matrix[j][item[1]] = 0
74. Search a 2D Matrix
class Solution(object):
def searchMatrix(self, matrix, target):
if len(matrix) == 1:
if target in matrix[0]:
return True
for row in range(1,len(matrix)):
if row == len(matrix) -1:
if target in matrix[row] or target in matrix[row-1]:
return True
if target < matrix[row][0] and target in matrix[row-1]:
return True
75. Sort Colors
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
i = 0 #for index 0
j = 0 # for index 1
n = len(nums)-1 # for index 2
while j<= n:
if nums[j] == 0:
nums[i], nums[j] = nums[j],nums[i]
i+=1
j+=1
elif nums[j] == 2:
nums[j],nums[n] = nums[n],nums[j]
n-=1
else: j +=1
76. Minimum Window Substring
首先要确定，T里面每种字符不一定都只有一个，有可能是AABC等。
第二滑动窗口是有两个pointer的，第一个是i，第二个是j。
TC是目标的内容，SC是滑动窗口内的内容，只要SC和TC相同的地方等于TC，我们就可以一直移动ipointer，让滑动窗口最小化。
collection的counter是字典形式统计数量的。
class Solution(object):
def minWindow(self, s, t):
need, missing = Counter(t), len(t)
i = I = J = 0
for j, c in enumerate(s,1):
missing -= need[c] > 0
need[c] -= 1
if not missing:
while i < j and need[s[i]] < 0:
need[s[i]] += 1
i += 1
if not J or j - i <= J - I:
I, J = i, j
return s[I:J]
77. Combinations
class Solution(object):
def combine(self, n, k):
tmp = [i for i in xrange(1,n+1)]
return combinations(tmp,k)
78. Subsets
class Solution(object):
def subsets(self, nums):
res = []
for i in xrange(len(nums)+1):
res += combinations(nums,i)
return res
80. Remove Duplicates from Sorted Array II
class Solution(object):
def removeDuplicates(self, nums):
for i in set(nums):
while nums.count(i) > 2:
nums.remove(i)
90. Subsets II
Dictionary 初始化的set：result = {()}
copy是shadow copy，与原来的共享。
（i，）是为了将int转化成tuple后与另外的tuple相加
class Solution(object):
def subsetsWithDup(self, nums):
result = {()}
nums.sort()
for i in nums:
[result.add(num+(i,)) for num in result.copy()]
return result
82. Remove Duplicates from Sorted List II
由于第一个也可能重复，所以不能直接取head，需要把第一个也放在比较范围，
所以前面加一个node设为0。
class Solution(object):
def deleteDuplicates(self, head):
ans = pre = ListNode(0)
pre.next = move = head
while move and move.next:
repeat = False
while move.next and move.val == move.next.val:
move.next = move.next.next
repeat = True
if repeat:
pre.next = move.next
else:
pre = pre.next
move = move.next
return ans.next
83，Remove Duplicates from Sorted List
list nodes
base case。 然后每个node去比较是否和前一个一样，不一样就放进去。注意temp有变化，但是只能返回最后一个值。而最后要return s。
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def deleteDuplicates(self, head):
if head == None:
return None
temp = s = ListNode (head.val)
while head.next is not None:
if head.next.val != head.val:
temp.next = ListNode(head.next.val)
temp = temp.next
head = head.next
return s
84. Largest Rectangle in Histogram
如果是升序，就不停压入stack中，每次都先计算一次自己本身的大小，在去计算前面的大小。
j = stack.pop()后stack[-1]就会是原来的倒数第二个。
由于第一个和最后一个也要计算进去，所以height前后都加了一个0，不会影响结果。
class Solution(object):
def largestRectangleArea(self, heights):
ans = 0
stack = []
heights = [0] + heights + [0]
for i in range(len(heights)):
while(stack and heights[stack[-1]] > heights[i]):
j = stack.pop()
ans = max(ans, (i-stack[-1]-1)*heights[j])
stack.append(i)
return ans
86. Partition List
大的小的分两个list最后连接起来就行了。
class Solution(object):
def partition(self, head, x):
h1 = l1 = ListNode(0)
h2 = l2 = ListNode(0)
while head:
if head.val< x:
l1.next = head
l1 = l1.next
else:
l2.next = head
l2 = l2.next
head = head.next
l2.next = None
l1.next = h2.next
return h1.next
88，Merge two sorted arrays
先放进去再排序。很简单。
class Solution(object):
def merge(self, nums1, m, nums2, n):
if not nums1:
return nums2
if not nums2:
return nums1
for i in range(len(nums2)):
print(m+i)
nums1[m+i] = nums2[i]
nums1.sort()
return nums1
89. Gray Code
00,01,然后一直都是前面加1的状态，换成二进制就是不停的加2的次方。所以bit+=bit。
class Solution(object):
def grayCode(self, n):
res = [0]
bit = 1
while n > 0:
layer = res[::-1]
for i in layer:
res.append(i+bit)
bit += bit
n -= 1
return res
