71、Simplify Path
Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.
In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix
Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.
Example 1:
Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.
绝对路径转化到规范路径
"""
绝对路径转化为规范路径
栈
"""
class Solution:
def simplifyPath(self, path: str) -> str:
stack=list()
dirs=path.split('/')
for dir in dirs:
if not dir or dir=='.':
continue
if dir=='..':
if stack:
stack.pop()
else:
stack.append(dir)
return '/'+'/'.join(stack)
72、Edit Distance
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
编辑距离
'''
编辑距离
插、删、替换
找出两个词之间的最小距离
动态规划
'''
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
matrix=[[i+j for j in range(len(word2)+1)] for i in range(len(word1)+1)]
for i in range(1,len(word1)+1):
for j in range(1,len(word2)+1):
if (word1[i-1]==word2[j-1]):
d=0
else:
d=1
matrix[i][j]=min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+d)
return matrix[len(word1)][len(word2)]
73、Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:
<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgb(247, 249, 250); padding: 10px 15px; color: rgb(38, 50, 56); line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]</pre>
'''
给定m×n矩阵，如果元素为0，则将其整个行和列设置为0.就地执行。
'''
class Solution:
# @param matrix, a list of lists of integers
# RETURN NOTHING, MODIFY matrix IN PLACE.
def setZeroes(self, matrix):
rownum = len(matrix)
colnum = len(matrix[0])
row = [False for i in range(rownum)]
col = [False for i in range(colnum)]
for i in range(rownum):
for j in range(colnum):
if matrix[i][j] == 0:
row[i] = True
col[j] = True
for i in range(rownum):
for j in range(colnum):
if row[i] or col[j]:
matrix[i][j] = 0
74、Search a 2D Matrix
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.
Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
'''
查询二维矩阵（判断是有目标值）
编写一个有效的算法，搜索m×n矩阵中的值。 该矩阵具有以下属性：
每行中的整数从左到右排序。
每行的第一个整数大于前一行的最后一个整数。
从左到右依次递增
从上到下依次增
二分查找
'''
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
if n == 0:
return False
mfirst,mlast = 0,m - 1
while mfirst < mlast:
mid = (mfirst + mlast + 1) // 2
if matrix[mid][0] == target:
return True
if matrix[mid][0] < target:
mfirst = mid
else:
mlast = mid - 1
print(mfirst)
nfirst,nlast = 0,n - 1
while nfirst <= nlast:
mid = (nfirst + nlast) // 2
if matrix[mfirst][mid] == target:
return True
if matrix[mfirst][mid] < target:
nfirst = mid + 1
else:
nlast = mid - 1
return False
75、Sort Colors
Given an array 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.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library's sort function for this problem.
Example:
<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgb(247, 249, 250); padding: 10px 15px; color: rgb(38, 50, 56); line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]</pre>
"""
给定一个具有红色，白色或蓝色的n个对象的数组，对它们进行就地排序，使相同颜色的对象相邻，颜色顺序为红色，白色和蓝色。
这里，我们将使用整数0,1和2分别表示红色，白色和蓝色。
//不使用库的排序功能来解决此问题
example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
"""
class Solution:
# @param A a list of integers
# @return nothing, sort in place
# @should learn another algorithm
def sortColors(self, A):
if A == []: return
p0 = 0; p2 = len(A) - 1; i = 0
while i <= p2:
if A[i] == 2:
A[i], A[p2] = A[p2], A[i]
p2 -= 1
elif A[i] == 0:
A[i], A[p0] = A[p0], A[i]
p0 += 1
i += 1
else:
i += 1
76、Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
"""
给定字符串S和字符串T，找到S中的最小窗口，它将包含的T中的所有字符。复杂度为O（n）。
"""
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
res = ""
left, right, cnt, minLen = 0, 0, 0, float('inf')
tcount = collections.Counter(t)
scount = collections.defaultdict(int)
while right < len(s):
scount[s[right]] += 1
if s[right] in tcount and scount[s[right]] <= tcount[s[right]]:
cnt += 1
while left <= right and cnt == len(t):
if minLen > right - left + 1:
minLen = right - left + 1
res = s[left : right + 1]
scount[s[left]] -= 1
if s[left] in tcount and scount[s[left]] < tcount[s[left]]:
cnt -= 1
left += 1
right += 1
return res
77、Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Example:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
"""
给定两个整数n和k，返回可能的包含k个元素的组合，元素范围1～n
深度优先搜索DFS
"""
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def dfs (start, valuelist):
if self.count==k:
res.append(valuelist)
return
for i in range(start,n+1):
self.count+=1
dfs(i+1,valuelist+[i])
self.count-=1
res=[]
self.count=0
dfs(1,[])
return res
78、subsets
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
"""
子集
给定一组不重复的整数，返回所有可能的子集
"""
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res=[[]]
for i in range(len(nums)):
for j in range(len(res)):
res.append(res[j]+[nums[i]])
return res
79、Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
"""
二维字母矩阵
查询单词
该单词可以由顺序相邻的单元的字母构成，其中“相邻”单元是水平或垂直相邻的单元。 相同的字母单元格不得多次使用。
深度优先搜索DFS
"""
class Solution:
# @param board, a list of lists of 1 length string
# @param word, a string
# @return a boolean
def exist(self, board, word):
def dfs(x, y, word):
if len(word)==0: return True
#up
if x>0 and board[x-1][y]==word[0]:
tmp=board[x][y]; board[x][y]='#'
if dfs(x-1,y,word[1:]):
return True
board[x][y]=tmp
#down
if x<len(board)-1 and board[x+1][y]==word[0]:
tmp=board[x][y]; board[x][y]='#'
if dfs(x+1,y,word[1:]):
return True
board[x][y]=tmp
#left
if y>0 and board[x][y-1]==word[0]:
tmp=board[x][y]; board[x][y]='#'
if dfs(x,y-1,word[1:]):
return True
board[x][y]=tmp
#right
if y<len(board[0])-1 and board[x][y+1]==word[0]:
tmp=board[x][y]; board[x][y]='#'
if dfs(x,y+1,word[1:]):
return True
board[x][y]=tmp
return False
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j]==word[0]:
if(dfs(i,j,word[1:])):
return True
return False
80、Remove Duplicates from Sorted Array II
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgb(247, 249, 250); padding: 10px 15px; color: rgb(38, 50, 56); line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Given nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It doesn't matter what you leave beyond the returned length.</pre>
Example 2:
<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgb(247, 249, 250); padding: 10px 15px; color: rgb(38, 50, 56); line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Given nums = [0,0,1,1,1,1,2,3,3],
Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.
It doesn't matter what values are set beyond the returned length.</pre>
"""
从排序数组里去除重复数据
给定一组排序的数据，就地删掉重复的数据，不要产生额外的空间去生成新的数组
返回新数组的长度
一个数字允许出现两次
思路：判断一个数和它后面第三个数是否一样
"""
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
a=len(nums)
end=2
for index in range(2,a):
if nums[end-2]!=nums[index]:
nums[end]=nums[index]
end+=1
return end
网友评论