71. Simplify Path （Medium）
Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.
class Solution:
def simplifyPath(self, path: str) -> str:
path = [e.replace('/','') for e in path.split('/') ]
print(path)
path = [e for e in path if e!='.' and len(e)>0]
print(path)
res = []
for p in path:
if p=='..':
if res:
res.pop()
else:
res.append(p)
return '/'+'/'.join(res)
72. Edit Distance (Hard)
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
# insert 2 del 3 replace
#dp 0 r o s
# 0 0 1 2 3
# h 1 1 2 3
# o 2 2 1 2
# r 3 3 2 2
# s 4 4 3 2
# e 5 5 4 3
rows=len(word1)+1
cols=len(word2)+1
dp=[[0]*cols for _ in range(rows)]
#fill row0 :
for j in range(len(word2)+1):
dp[0][j]=j
#fill col0
for i in range(len(word1)+1):
dp[i][0]=i
for i in range(1,rows):
for j in range(1,cols):
min_=min(dp[i][j-1],dp[i-1][j-1],dp[i-1][j])
if word1[i-1]==word2[j-1]:
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=min_+1
return dp[rows-1][cols-1]
似乎是用dynamic programmming， 但没想出来递归怎么写。
看了答案发现很简单。。。dp[i][j] = min(dp[i][j-1],dp[i-1][j-1],dp[i-1][j]) + 1 如果末尾不同，如果末尾相同 dp[i][j] = dp[i-1]dp[j-1]
73. Set Matrix Zeroes (Medium)
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's, and return the matrix.
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# project 0 to row[0] & col[0] but matrix[0][0] will overlapping should be taken care
row00 = 1
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if matrix[row][col]==0:
if col==0:
row00=0
else:
matrix[0][col]=0
matrix[row][0]=0
# for row in matrix:
# print(row)
for row in range(len(matrix)-1,-1,-1):
for col in range(len(matrix[0])-1,-1,-1):
if col==0:
if row00==0:
matrix[row][col]=0
else:
if (matrix[0][col]==0 or matrix[row][0]==0):
matrix[row][col]=0
挺有意思一题目，正的扫0位置，把0位置存在top和left边上，但是【0，0】的位置会存2此产生数据覆盖，所以如果第一列有元素是0，则需要把row00这个赋为0. 第二部，反的扫元素位置，防止填0的时候覆盖数据。然后注意第一列是不是为0依靠判断row00元素是否为0即可。
74. Search a 2D Matrix （Medium）
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# 1 2 3
# 4 5 6 seach 2 mid=5 target<mid left top or left right
# 7 8 9 9 mid=5 target>mid right bot or left bot
m = len(matrix)
n = len(matrix[0])
def helper(matrix, target, rowleft,rowright,colleft,colright):
print(rowleft,rowright,colleft,colright)
if rowleft==rowright:
return target in [matrix[rowleft][col] for col in range(colleft,colright+1)]
if colleft==colright:
return target in [matrix[row][colleft] for row in range(rowleft,rowright+1)]
if rowright-rowleft==1 and colright-colleft==1:
if matrix[rowleft][colleft]==target:
return True
if matrix[rowleft][colright]==target:
return True
if matrix[rowright][colleft]==target:
return True
if matrix[rowright][colright]==target:
return True
return False
rowmid = (rowleft+rowright)//2
colmid = (colleft+colright)//2
if matrix[rowmid][colmid]==target:
return True
elif matrix[rowmid][colmid]<target:
#seach right bot or left bot
return helper(matrix,target,rowmid,rowright,colmid,colright) or helper(matrix,target,rowmid,rowright, colleft,colmid)
else:
#seaerch left top or left right
return helper(matrix,target,rowleft,rowmid,colleft,colmid) or helper(matrix,target,rowleft,rowmid, colmid,colright)
return helper(matrix,target,0,m-1,0,n-1)
# answer way of writting
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]: return False
#binary find row first
rows=len(matrix)
cols=len(matrix[0])
if rows==cols and rows==1:
return matrix[0][0]==target
l=0
r=rows-1
while l<=r:
m=(l+r)//2
if target==matrix[m][cols-1]:
return True
elif target>matrix[m][cols-1]:
l=m+1
else:
r=m-1
findrow=l
if findrow<0: findrow=0
if findrow>=rows: findrow=rows-1
#binary search find col
l=0
r=cols-1
while l<=r:
m=(l+r)//2
if target==matrix[findrow][m]:
return True
elif target>matrix[findrow][m]:
l=m+1
else:
r=m-1
return False
##############
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m=len(matrix)
n=len(matrix[0])
#seach last column
li = [matrix[i][-1] for i in range(m)]
def bs(li,t):
l=0
r=len(li)-1
while l<=r:
m=(l+r)//2
if li[m]==target:
return m
elif li[m]>target:
r=m-1
else:
l=m+1
return l
row = bs(li,target)
if row>=m:
return False
#print(row)
col=bs(matrix[row],target)
if col>=n:
return False
return matrix[row][col]==target
#BEST ANSWER
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m,n = len(matrix),len(matrix[0])
row = m-1
col = 0
while m>row>=0 and n>col>=0:
if matrix[row][col]==target: return True
elif matrix[row][col]>target:
row-=1
else:
col+=1
return False
binary search for matrix... 虽然写出来了，但感觉写的不完美而且用时过长，思路：如果最后是4个正方形矩阵，依次寻找target，如果最后是一行，依次寻找。 把目标分解到4个象限中的2个来寻找。
感觉递归base case这步可以优化。另一种写法是先找行再找列。。。
75. Sort Colors （Medium）
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# left maintail all 0s rigth maintain all 2s
l=0
r=len(nums)-1
for i,n in enumerate(nums):
if n==0:
nums[l],nums[i] = nums[i],nums[l]
l+=1
l=0
r=len(nums)-1
#print(nums)
for i in range(len(nums)-1,-1,-1):
if nums[i]==2:
nums[r],nums[i] = nums[i],nums[r]
r-=1
#answer way of writting
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
p0=cur=0
p2=len(nums)-1
while cur<=p2:
if nums[cur]==0:
nums[p0],nums[cur]=nums[cur],nums[p0]
p0+=1
cur+=1
elif nums[cur]==2:
nums[p2],nums[cur],=nums[cur],nums[p2]
p2-=1
else:
cur+=1
我的答案是遍历2次， 第一次找0位置做交换， 第二次从末向前遍历找2位置做交换。
答案更简单只遍历一次。。。有点tricky地方在于必须用while cur<=p2, 不能for i，n in enumerate（nums）
76. Minimum Window Substring (Hard）
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
class Solution:
def minWindow(self, s: str, t: str) -> str:
# sliding window
# how?
#
# l r
# move r util contains all t's chars
# shrink l,until count[char]==0 del count char, then move r
#
def equal(dic_s,dic_t):
for k,v in dic_t.items():
if k not in dic_s:
return False
if dic_s[k]<v:
return False
return True
dic_t = dict()
for char in t:
dic_t[char]=dic_t.get(char,0)+1
l=0
r=0
dic_s = dict()
while not equal(dic_s,dic_t) and r<len(s):
if s[r] in dic_t:
dic_s[s[r]]=dic_s.get(s[r],0)+1
r+=1
r=r-1 if r-1>=0 else 0
#print(l,r)
#now l to r contains all chars in t
res = ''
minw = float('inf')
#shrink l , move r
while l<=r and r<len(s):
#calculate
if r-l+1 < minw and equal(dic_s,dic_t):
minw=r-l+1
res=s[l:r+1]
#remove char
char = s[l]
if char in dic_t:
dic_s[char] = dic_s.get(char,0)-1
if dic_s[char]<=0:
del dic_s[char]
while not equal(dic_s,dic_t):
r+=1
if r>=len(s):
break
if s[r] in dic_t:
dic_s[s[r]]=dic_s.get(s[r],0)+1
#
l=l+1
return res
####
class Solution:
def minWindow(self, s: str, t: str) -> str:
dic_t = collections.Counter(t)
res = None
# expand include all
# shrink until less than dic_t expand again
def dic_equal(d,t):
for k,v in t.items():
if k not in d:
return False
if d[k]<v:
return False
return True
p = 0
dic = dict()
length = float('inf')
res = ''
for i,ch in enumerate(s):
dic[ch] = dic.get(ch,0)+1
while dic_equal(dic,dic_t):
candidate=s[p:i+1]
l=i+1-p
if l<length:
length = l
res = candidate
if s[p] in dic:
dic[s[p]]-=1
if dic[s[p]]==0:
del dic[s[p]]
p+=1
return res
通过sliding window做出来了， equal 这个helper function很关键。 要equal dic_s里面得有所有 dic_target 的key 而且val必须大于等于target val。 思路： move r util contains all t's chars。shrink l,until count[char]==0 del count char, then move r。
77. Combinations （Medium）
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].
You may return the answer in any order.
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
nums = [i for i in range(1,n+1)]
def bt(tmp,start):
if len(tmp)==k:
res.append(tmp[:])
else:
for i in range(start,n):
tmp.append(nums[i])
bt(tmp,i+1)
tmp.pop()
bt([],0)
return res
典型backtracking， 新start=i+1 假如是start+1 则可能这个start+1 是小于等于i的，相当于重复选择 。
78. Subsets （Medium）
Given an integer array nums of unique elements, return all possible subsets (the power set).
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def bt(tmp,start):
res.append(tmp[:])
for i in range(start,len(nums)):
n=nums[i]
if n not in tmp:
tmp.append(n)
bt(tmp,i+1)
tmp.pop()
bt([],0)
return res
79. Word Search (Medium)
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
# bfs??? 几乎忘记了 dfs bfs 怎么写?
# 不能重复用元素，所以访问后设为-1，
def bfs(board,word,i,j):
if not word:
return True
if word[0]!= board[i][j]:
return False
boardij=board[i][j]
board[i][j]=-1
word=word[1:]
res = False
neig = [(i,j+1),(i,j-1),(i-1,j),(i+1,j)]
valid_neig = []
for nei in neig:
row,col=nei
if row>=0 and row<len(board) and col>=0 and col<len(board[0]):
valid_neig.append((row,col))
if not valid_neig and not word:
return True
for nei in valid_neig:
row,col=nei
res = res or bfs(board,word,row,col)
board[i][j]=boardij
return res
res = False
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j]==word[0]:
res = res or bfs(board,word,i,j)
return res
# answer way of writting
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not word: return True
if not board: return False
def dfs(board,i,j,w):
if not w:
return True
if i<0 or j<0 or i>=len(board) or j>=len(board[0]) or board[i][j]!=w[0]:
return False
#found first fit
temp=board[i][j]
board[i][j]="#" #avoid visit again
res=dfs(board,i+1,j,w[1:]) or dfs(board,i,j+1,w[1:]) or dfs(board,i-1,j,w[1:]) or dfs(board,i,j-1,w[1:])
board[i][j]=temp
return res
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(board, i, j, word):
return True
return False
代码巨大丑无比， 但是pass了 。 答案的dfs写的很优雅。。。Time Complexity: O(N⋅3**L) where N is the number of cells in the board and L is the length of the word to be matched.
80. Remove Duplicates from Sorted Array II (Medium)
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
#
pos = 0
pre=nums[0]
c =0
for i,n in enumerate(nums):
if pre==n:
c+=1
else:
c=1
if c<=2:
nums[pos] = nums[i]
pos+=1
pre=n
return pos
two pointer 。 pos是下一个正确位置。当pre！=cur时候 重新更新计数器为1，pre=cur
如果 计数器c 小于等于2. 把nums[i]放入nums[pos]。