- LeetCode66. Plus One - Easy
- LeetCode67. Add Binary - Easy
LeetCode69. Sqrt(x) - Easy 二分找
- LeetCode70. Climbing Stairs - Easy dp
- LeetCode71. Simplify Path - Medium
- 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.
思路: 注意'/..hidden/'这一类例子.
用'/'split 之后, 用 stack 记录碰到的内容, 且判断是否是'.'或者是'..'.
- class Solution:
- def simplifyPath(self, path: str) -> str:
- if not path or len(path) == 0:
- return " "
- res = ''
- stack = []
- i = 0
- path = path.split('/')
- print(path)
- for i in range(len(path)):
- if not path[i] or path[i] == '.':
- continue
- elif path[i] == '..':
- if stack:
- stack.pop()
- else:
- continue
- else:
- stack.append(path[i])
- for i in range(len(stack)):
- res += '/'+stack[i]
- if not res: res = '/'
- return res
- LeetCode72. Edit Distance - Hard
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')
思路: 和 text regex 一样的思路, 用一个 len(s1)+1 * len(s2) +1 的 dp 来记录状态.
- class Solution:
- def minDistance(self, word1: str, word2: str) -> int:
- if not word1 or len(word1) == 0:
- return len(word2)
- if not word2 or len(word2) == 0:
- return len(word1)
- # the max will be len(word1)
- m = len(word1)
- n = len(word2)
- dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
- temp = 1
- for i in range(1,m+1):
- dp[i][0] = temp
- temp += 1
- dp[0] = [i for i in range(n+1)]
- for i in range(1, m+1):
- for j in range(1, n+1):
- if word1[i-1] == word2[j-1]:
- dp[i][j] = dp[i-1][j-1]
- else:
- dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- # print(dp)
- return dp[-1][-1]
- LeetCode73. Set Matrix Zeroes
- Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place https://en.wikipedia.org/wiki/In-place_algorithm .
- Example 1:
- Input:
- [
- [1,1,1],
- [1,0,1],
- [1,1,1]
- ]
- Output:
- [
- [1,0,1],
- [0,0,0],
- [1,0,1]
- ]
思路: 用'#'标记本来是 1 但是后来改为 0 的元素.
- class Solution:
- def setZeroes(self, matrix: List[List[int]]) -> None:
- """
- Do not return anything, modify matrix in-place instead.
- """
- if not matrix or len(matrix) == 0:
- return []
- rows = len(matrix)
- cols = len(matrix[0])
- for i in range(rows):
- for j in range(cols):
- if matrix[i][j] == 0:
- row = i
- col = j
- for ii in range(rows):
- if matrix[ii][col] != 0:
- matrix[ii][col] = '#'
- for jj in range(cols):
- if matrix[row][jj] != 0:
- matrix[row][jj] = '#'
- for i in range(rows):
- for j in range(cols):
- if matrix[i][j] == '#':
- matrix[i][j] = 0
- LeetCode74.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.
- Example 1:
- Input:
- matrix = [
- [1, 3, 5, 7],
- [10, 11, 16, 20],
- [23, 30, 34, 50]
- ]
- target = 3
- Output: true
- Example 2:
- Input:
- matrix = [
- [1, 3, 5, 7],
- [10, 11, 16, 20],
- [23, 30, 34, 50]
- ]
- target = 13
- Output: false
- class Solution:
- def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
- if not matrix or len(matrix)==0 or len(matrix[0])== 0:
- return False
- for i in range(len(matrix)):
- l = 0
- r = len(matrix[0])-1
- if matrix[i][l]> target or matrix[i][r] <target:
- print('!!')
- continue
- while l <r:
- mid = l + (r-l) // 2
- if matrix[i][mid] == target:
- return True
- elif matrix[i][mid]> target:
- r = mid
- else:
- l = mid + 1
- if matrix[i][l] == target:
- return True
- if matrix[i][r] == target:
- return True
- return False
- LeetCode75. Sort Colors - Medium
- Given an array with n objects colored red, white or blue, sort them in-place https://en.wikipedia.org/wiki/In-place_algorithm so that objects of the same color are adjacent, with the colors in the order red, white and blue.
- Note: You are not supposed to use the library's sort function for this problem.
- Example:
- Input: [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.
- """
- if not nums or len(nums) == 0:
- return []
- l = 0
- r = len(nums)-1
- i = 0
- while i <= r:
- if nums[i] == 0:
- nums[l], nums[i] = nums[i], nums[l]
- l += 1
- i += 1
- elif nums[i] == 2:
- nums[r], nums[i] = nums[i], nums[r]
- r -= 1
- else:
- i += 1
- LeetCode76. Minimum Windows Substring - Hard
- Given a string S and a string T, find the minimum Windows in S which will contain all the characters in T in complexity O(n).
- Example:
- Input: S = "ADOBECODEBANC", T = "ABC"
- Output: "BANC"
- Note:
- If there is no such Windows in S that covers all characters in T, return the empty string "".
- If there is such a Windows, you are guaranteed that there will always be only one unique minimum Windows in S.
- construct a counter for t and a missing for # of the characters for t
- initialize a start, end and one of the pointers i to be zero
- 1) for every element if the value in the counter for that element is greater than zero, which means t has this element, we will do missing -= 1
- 2) minus 1 of the value for every element in the counter
- 3) if the missing value is zero, it means we have already got all the characters in the t. We use i to do sliding Windows.
- class Solution:
- def minWindow(self, s: str, t: str) -> str:
- if not s or len(s) == 0:
- return ""
- need = collections.Counter(t)
- missing = len(t)
- start = end = 0
- i = 0
- for j, char in enumerate(s, 1):
- if need[char]> 0:
- missing -= 1
- need[char] -= 1
- if missing == 0:
- while i < j and need[s[i]] < 0:
- need[s[i]] += 1
- i += 1
- need[s[i]] += 1
- missing += 1
- if end == 0 or j-i < end - start:
- start, end = i, j
- i += 1
- return s[start:end]
来源: http://www.bubuko.com/infodetail-3364734.html