這里是 HOT 100刷題筆記，篇幅較長(zhǎng)，因此分成兩部分，按照題目序號(hào)排列。有幾題沒(méi)做后序會(huì)補(bǔ)上。
- 兩數(shù)之和
比較好的辦法就是利用map來(lái)存儲(chǔ)每一個(gè)元素以及其對(duì)應(yīng)的索引，但是這里要考慮到map是無(wú)法存儲(chǔ)重復(fù)的key，因此我們?cè)谂袛嗍欠翊嬖跐M足符合條件的，一個(gè)為原數(shù)組中的索引，另一個(gè)為Map中的索引這個(gè)一定要注意。
解法1：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
Map = {}
for i in range(len(nums)):
Map[nums[i]] = i
for i in range(len(nums)):
j = Map.get(target - nums[i])
if j and j != i:
return[i, j]
return []
解法2：（將兩個(gè)for循環(huán)合并一下，可以讓程序提前終止，讓Map存儲(chǔ)當(dāng)前元素之前的信息）
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
Map = {}
for i in range(len(nums)):
j = Map.get(target - nums[i])
if j != None :
return[j, i]
Map[nums[i]] = i #這一步的順序不能調(diào)換
return []
- 兩數(shù)相加
這一題其實(shí)就是兩個(gè)鏈表相加，這一需要考慮到兩個(gè)鏈表的長(zhǎng)度不一致和進(jìn)位的情況，這一題還有一個(gè)小技巧，就是使用一個(gè)頭節(jié)點(diǎn)，這樣代碼寫起來(lái)更方便。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
s = 0
head = p = ListNode(0)
while(l1 or l2 or s):
s += (l1.val if l1 else 0) + (l2.val if l2 else 0)
p.next = ListNode(s%10)
p = p.next
s = s // 10
if l1:
l1 = l1.next
else:
l1 = None
if l2:
l2 = l2.next
else:
l2 = None
return head.next
- 最長(zhǎng)無(wú)重復(fù)子串
經(jīng)典的滑動(dòng)窗口題目，模板題，詳情參考：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
window = {}
left = 0
right = 0
length = len(s)
res = 0
while(right < length):
c = s[right]
if c not in window:
window[c] = 1
else:
window[c] += 1
right += 1
while(window[c] > 1):
d = s[left]
left += 1
window[d] -= 1
res = max(res, right-left)
return res
- 最長(zhǎng)回文子串
這一題與647回文字串這一題一樣，具體的我就不多說(shuō)了。
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ''
length = len(s)
dp = [[0]*length for i in range(length)]
for i in range(length):
for j in range(length):
if i == j:
dp[i][j] = 1
maxlength = 1
res = s[0]
for i in range(length-1, -1, -1):
for j in range(i+1, length):
if s[j] == s[i]:
if j == i+1:
dp[i][j] = 1
else:
dp[i][j] = dp[i+1][j-1]
else:
dp[i][j] = 0
if dp[i][j] == 1:
if j - i + 1 > maxlength:
maxlength = j - i + 1
res = s[i:j+1]
return res
- 盛最多水的容器
簡(jiǎn)單的DP:
采用雙指針進(jìn)行搜索，將a[i]和a[j]中較小的坐標(biāo)進(jìn)行移動(dòng)，因?yàn)閷⑤^大的往里進(jìn)行移動(dòng)，最終的結(jié)果一定會(huì)變小。
class Solution:
def maxArea(self, height: List[int]) -> int:
i = 0
j = len(height) - 1
res = -99999999
while(i <= j):
res = max(res, min(height[i], height[j])*(j - i))
if height[i] < height[j]:
i += 1
else:
j -= 1
return res
- 三數(shù)之和
參考：https://blog.csdn.net/sd4567855/article/details/86777399 先排序再利用雙指針來(lái)去重。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
length = len(nums)
if length < 3 or nums[0] > 0 or nums[-1] < 0 :
return res
for i in range(length-2):
if nums[i] > 0:
break
if i > 0 and nums[i-1] == nums[i]:
continue
j = i + 1
k = length - 1
while(j < k):
if nums[i] + nums[j] + nums[k] == 0:
res.append([nums[i], nums[j], nums[k]])
while(j < k and nums[j] == nums[j+1]):
j += 1
while(j < k and nums[k-1] == nums[k]):
k -= 1
j += 1
k -= 1
elif nums[i] + nums[j] + nums[k] > 0:
k -= 1
else:
j += 1
return res
- 電話號(hào)碼的字母組合
簡(jiǎn)單的DFS即可。
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
Dict = {'2':{'a', 'b', 'c'},
'3':{'d', 'e', 'f'}, '4':{'g', 'h', 'i'}, '5':{'j', 'k', 'l'},
'6':{'m', 'n', 'o'}, '7':{'p', 'q', 'r', 's'}, '8':{'t', 'u', 'v'},
'9':{'w', 'x', 'y', 'z'}}
length = len(digits)
res = []
def dfs(route, count):
if count == length:
res.append(route)
return
for c in Dict[digits[count]]:
dfs(route + c, count + 1)
dfs('', 0)
return res
- 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
快慢指針，基本操作，需要注意的是有一種情況是直接刪除頭節(jié)點(diǎn)。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if not head:
return None
temp = head
count = 0
while(temp):
count += 1
if count == n:
break
temp = temp.next
slow = head
fast = temp
pre = None
while(fast.next):
fast = fast.next
pre = slow
slow = slow.next
if not pre:
return head.next
pre.next = slow.next
return head
- 有效的括號(hào)
- 比較直接的方法就是利用python的正則表達(dá)式直接對(duì)這三種括號(hào)進(jìn)行替換。
- 借助棧結(jié)構(gòu)來(lái)完成括號(hào)的匹配操作。
解法1：
class Solution:
def isValid(self, s: str) -> bool:
while('()' in s or '{}' in s or '[]' in s):
s = s.replace('()', '')
s = s.replace('[]', '')
s = s.replace('{}', '')
return s == ''
解法2：
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for c in s:
if c == '(' or c == '[' or c == '{':
stack.append(c)
else:
if not stack:
return False
if c == ')':
temp = stack.pop()
if temp != '(':
return False
elif c == ']':
temp = stack.pop()
if temp != '[':
return False
elif c == '}':
temp = stack.pop()
if temp != '{':
return False
return stack == []
- 合并兩個(gè)有序鏈表
正常的鏈表遍歷操作，注意在合并鏈表的時(shí)候，除了要保存頭節(jié)點(diǎn)以外，還需要用一個(gè)指針來(lái)記錄鏈表當(dāng)前節(jié)點(diǎn)的位置。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
head1 = l1
head2 = l2
head3 = None
temp = None
if head1.val <= head2.val:
head3 = head1
temp = head3
head1 = head1.next
else:
head3 = head2
temp = head3
head2 = head2.next
while(head1 and head2):
if head1.val <= head2.val:
temp.next = head1
temp = head1
head1 = head1.next
else:
temp.next = head2
temp = head2
head2 = head2.next
while(head1):
temp.next = head1
temp = head1
head1 = head1.next
while(head2):
temp.next = head2
temp = head2
head2 = head2.next
return head3
- 括號(hào)生成
https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/
這一題使用遞歸比較符合正常的想法，同樣需要設(shè)計(jì)好遞歸函數(shù)的參數(shù)，這里使用route，left，right這三個(gè)參數(shù)，分別表示存儲(chǔ)的路徑，左括號(hào)還剩余的數(shù)量，右括號(hào)還剩余的數(shù)量，該遞歸函數(shù)沒(méi)有返回值，使用全局變量來(lái)存儲(chǔ)不同的路徑。
當(dāng)左右剩余的括號(hào)數(shù)量為0的時(shí)候，表明找到了滿足題意的路徑。
當(dāng)剩余的左括號(hào)數(shù)量大于剩余的右括號(hào)數(shù)量的時(shí)候，程序終止，因?yàn)檫@樣生成的路徑一點(diǎn)不滿足題意。
左右剩余的括號(hào)數(shù)量大于0的時(shí)候，才進(jìn)行下一次擴(kuò)展。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def dfs(route, left, right):
if left == 0 and right == 0:
res.append(route)
return
if left > right:
return
if left > 0:
dfs(route + '(', left - 1, right)
if right > 0:
dfs(route + ')', left, right - 1)
dfs('', n, n)
return res
- 合并K個(gè)排序鏈表
比較直觀的做法，直接利用分治的方法，接下來(lái)的重點(diǎn)就是如何設(shè)計(jì)好遞歸函數(shù)的參數(shù)了。
遞歸函數(shù)的參數(shù)還是借用二分的寫法，采用左右邊界來(lái)確定鏈表的個(gè)數(shù)。
也可以通過(guò)建立一個(gè)堆來(lái)合并這k個(gè)鏈表。
解法1：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
def merge(l1, l2):
p = ListNode()
temp = p
while(l1 and l2):
if l1.val < l2.val:
temp.next = l1
l1 = l1.next
else:
temp.next = l2
l2 = l2.next
temp = temp.next
if l1 :
temp.next = l1
else:
temp.next = l2
return p.next
def recursion(l, r):
if l == r:
return lists[l]
if l > r:
return
mid = (l + r) // 2
left = recursion(l, mid)
right = recursion(mid + 1, r)
return merge(left, right)
return recursion(0, len(lists) - 1)
解法2：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
from heapq import heappush, heappop
class MyNode:
def __init__(self, node):
self.node = node
def __lt__(self, other):
if self.node.val <= other.node.val:
return True
else: return False
def get(self):
return self.node
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
heap = []
for l in lists:
if l:
heappush(heap, MyNode(l))
p = head = ListNode(0)
while heap:
node = heappop(heap)
p.next = node.get()
p = p.next
if node.get().next:
heappush(heap, MyNode(node.get().next))
return head.next
- 下一個(gè)排列
求下一個(gè)排列有著比較標(biāo)準(zhǔn)的算法，這個(gè)在組合數(shù)學(xué)上都有專門講過(guò)，C++中STL也專門封裝了這個(gè)方法。算法分為三步：
- 從后往前搜，找到第一個(gè)跳變：要求后一個(gè)大于前一個(gè)，如果沒(méi)有說(shuō)明當(dāng)前排列已經(jīng)是最大的了。
- 通過(guò)前面的跳變查找將數(shù)組分成了前后兩個(gè)部分，在后面部分的數(shù)組中找到第一個(gè)大于跳變的那個(gè)數(shù)，進(jìn)行交換。
- 將后面部分的數(shù)組按照從小到達(dá)的順序進(jìn)行交換。
語(yǔ)言表述可能不是很清楚，參考：https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
length = len(nums) - 1
i = length
while(i >= 1 and nums[i-1] >= nums[i]):
i -= 1
if i == 0:
nums.reverse()
return nums
j = length
while(j >= 0 and nums[j] <= nums[i-1]):
j -= 1
temp = nums[j]
nums[j] = nums[i-1]
nums[i-1] = temp
res = nums[i:]
for i in range(len(res)):
nums[length-i] = res[i]
return nums
- 最長(zhǎng)有效括號(hào)
直觀上來(lái)看需要用到棧這樣的結(jié)構(gòu)。需要記錄啥時(shí)候入棧，啥時(shí)候會(huì)出棧。當(dāng)棧為空的時(shí)候，當(dāng)前元素為'('或者當(dāng)前棧頂元素為')'入棧，否則出棧，入棧的是字符的索引，這樣方便計(jì)算出括號(hào)的長(zhǎng)度。
class Solution:
def longestValidParentheses(self, s: str) -> int:
if s == "":
return 0
stack = []
res = 0
for index, c in enumerate(s):
if not stack or c == '(' or s[stack[-1]] == ')': #注意細(xì)節(jié)
stack.append(index)
else:
stack.pop()
temp = stack[-1] if stack else -1 #注意細(xì)節(jié)
res = max(res, index - temp )
return res
- 搜索旋轉(zhuǎn)排序數(shù)組
那這一題顯然是要用二分查找，但是這一題卻是局部有序，因此我們需要在原始的二分查找上面進(jìn)行一些改動(dòng)，一半來(lái)說(shuō)二分查找的難點(diǎn)在于邊界條件。首先需要判斷元素是在左邊部分還是右邊部分，然后對(duì)于左邊部分和右邊部分需要各自判斷其的左右部分。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while(left <= right):
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[left]:
if nums[mid] > target and target >= nums[left]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
- 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
二分法查找左邊界和右邊界，二分法的細(xì)節(jié)太難寫了，開區(qū)間還是閉區(qū)間，等于還是不等于都需要注意。這里還有一種寫法來(lái)求左右邊界，如果有那么就一直向左移動(dòng)或者是向右移動(dòng)，沒(méi)有的話就返回-1。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def serachLeft(nums):
if not nums:
return -1
left = 0
right = len(nums) - 1
while(left <= right):
mid = (left + right) // 2
if nums[mid] == target: #要求找最左邊，因此更新右邊界
right = mid - 1
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
if left <= len(nums) - 1 and nums[left] == target: #注意
return left
else:
return -1
def searchRight(nums):
if not nums:
return -1
left = 0
right = len(nums) - 1
while(left <= right):
mid = (left + right) // 2
if nums[mid] == target: #要求找最右邊，因此更新左邊界
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
if right >= 0 and nums[right] == target: #注意
return right
else:
return -1
return [serachLeft(nums), searchRight(nums)]
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def search_left(nums):
l = 0
r = len(nums)-1
while(l <= r):
mid = (l+r) // 2
if nums[mid] == target:
left = mid
right = mid
while(left>=1):
if nums[left] == nums[left-1]:
left = left - 1
else:
break
while(right <= len(nums)-2):
if nums[right] == nums[right+1]:
right = right + 1
else:
break
return [left, right]
elif nums[mid] > target:
r = mid - 1
else:
l = mid + 1
return [-1, -1]
return search_left(nums)
最后一種寫法:
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def left_search(nums):
l = 0
r = len(nums) - 1
while(l <= r):
mid = (l + r) // 2
if nums[mid] == target:
r = mid - 1
elif nums[mid] > target:
r = mid - 1
else:
l = mid + 1
if l == len(nums) or nums[l] != target:
return -1
return l
def right_searh(nums):
l = 0
r = len(nums) - 1
while(l <= r):
mid = (l + r) // 2
if nums[mid] == target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
else:
l = mid + 1
if r < 0 or nums[r] != target:
return -1
return r
l = left_search(nums)
r = right_searh(nums)
return [l, r]
- 組合總和
標(biāo)準(zhǔn)的DFS，需要設(shè)計(jì)好遞歸函數(shù)的參數(shù)。基本的遍歷和剪枝都很簡(jiǎn)單，關(guān)鍵是如何去重，這個(gè)跟以前的DFS有區(qū)別，不能用標(biāo)記來(lái)記錄走過(guò)的路徑，因?yàn)檫@里的數(shù)字可以重復(fù)選取。解法里給了一個(gè)索引來(lái)記錄當(dāng)前節(jié)點(diǎn)的順序，在下一次的遍歷中從這個(gè)節(jié)點(diǎn)開始，這樣就保證了數(shù)字可以重復(fù)選取，也避免了路徑的重復(fù)。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def dfs(i, sumNum, route):
if sumNum == 0:
res.append(route)
return
for index in range(i, len(candidates)):
if sumNum >= candidates[index]:
dfs(index, sumNum - candidates[index], route + [candidates[index]])
dfs(0, target, [])
return res
- 接雨水
這一題本質(zhì)上是要求一個(gè)定值，第一眼看到這題我也沒(méi)啥好的思路，看了題解才知道要用單調(diào)遞減棧。需要使用棧是因?yàn)樾碌陌疾圩筮吔缫欢ㄊ亲钚掠龅降?，而要使用遞減棧是因?yàn)楫?dāng)?shù)偷挠龅礁叩牟艜?huì)相應(yīng)的凹槽。在具體實(shí)現(xiàn)上這一題有很多細(xì)節(jié)，首先我們?nèi)霔Ｊ窃氐南聵?biāo)，因?yàn)楹竺嫖覀冃枰褂孟聵?biāo)來(lái)求寬度。當(dāng)前棧不為空且當(dāng)前元素大于棧頂則出棧。在計(jì)算凹槽能存儲(chǔ)的雨水時(shí)，需要當(dāng)前元素，前一個(gè)元素，后面一個(gè)元素來(lái)共同計(jì)算，當(dāng)沒(méi)有前一個(gè)元素的時(shí)候，直接跳出，計(jì)算凹槽的寬度沒(méi)啥難度，但是計(jì)算凹槽的高度的時(shí)候需要注意：前后兩個(gè)高度取較低的再減去中間這個(gè)最低的才能得到相對(duì)高度差。
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
stack = []
for i in range(len(height)):
while(stack and height[stack[-1]] < height[i]):
temp = stack.pop()#出棧
if not stack:#沒(méi)有前一個(gè)元素直接跳出
break
left = stack[-1]
right = i
width = right - left -1
length = min(height[left], height[right]) - height[temp]
ans += width*length
stack.append(i)#下標(biāo)入棧
return ans
- 全排列
標(biāo)準(zhǔn)的排列做法。這里需要注意一下python中傳遞列表這一類數(shù)據(jù)的時(shí)候
解法1：（錯(cuò)誤）
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
length = len(nums)
res = []
route = [0]*length
flags = [0]*length
def dfs(count):
if count == length:
print(route)
res.append(route)
return
for i in range(length):
if flags[i] == 0:
flags[i] = 1
route[count] = nums[i]
dfs(count + 1)
flags[i] = 0
dfs(0)
return res
解法2：(對(duì)傳遞的列表進(jìn)行復(fù)制)
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
length = len(nums)
res = []
route = [0]*length
flags = [0]*length
def dfs(count):
if count == length:
print(route)
res.append(route[:])
return
for i in range(length):
if flags[i] == 0:
flags[i] = 1
route[count] = nums[i]
dfs(count + 1)
flags[i] = 0
dfs(0)
return res
解法3：（將存儲(chǔ)路徑的變量采用參數(shù)的形式來(lái)傳遞）
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
length = len(nums)
res = []
flags = [0]*length
def dfs(count, route):
if count == length:
res.append(route)
return
for i in range(length):
if flags[i] == 0:
flags[i] = 1
dfs(count + 1, route + [nums[i]])
flags[i] = 0
dfs(0, [])
return res
- 旋轉(zhuǎn)圖像
先將矩陣進(jìn)行轉(zhuǎn)置，再將每一行反轉(zhuǎn)即可。
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
for i in range(len(matrix)):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(len(matrix)):
matrix[i].reverse()
- 字母異位詞分組
比較好的辦法就是利用字典，但是我們需要區(qū)分好鍵值，這里使用排序函數(shù)來(lái)進(jìn)行區(qū)分。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
Dict = {}
for s in strs:
key = ''.join(sorted(s))
if key not in Dict:
Dict[key] = []
Dict[key].append(s)
return list(Dict.values())
- 最大子序和
簡(jiǎn)答的DP。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0]*len(nums)
dp[0] = nums[0]
res = nums[0]
for i in range(1, len(nums)):
if dp[i-1] < 0:
dp[i] = nums[i]
else:
dp[i] = dp[i-1] + nums[i]
res = max(res, dp[i])
return res
- 跳躍游戲
這一題需要用動(dòng)態(tài)規(guī)劃，k表示到達(dá)第i步時(shí)，能夠走的最遠(yuǎn)距離。如果k<i那么就返回False，每次對(duì)k進(jìn)行更新 k = max(k, i+nums[i])
解法1：超時(shí)
class Solution:
def canJump(self, nums: List[int]) -> bool:
length = len(nums)
flags = [0]*length
flags[0] = 1
for i in range(length-1):
if flags[i] == 1:
for j in range(i, min(i+nums[i]+1, length)):
flags[j] = 1
if flags[-1] == 1:
return True
if flags[-1] == 1:
return True
else:
return False
解法2：
k表示在在當(dāng)前位置能夠走到的最遠(yuǎn)距離。
class Solution:
def canJump(self, nums: List[int]) -> bool:
length = len(nums)
k = 0
for i in range(length):
if i > k:
return False
k = max(k, i + nums[i])
return True
- 合并區(qū)間
這個(gè)題目從暴力上是沒(méi)法解決的，暴力的復(fù)雜度是n!，只能通過(guò)排序的手段來(lái)降低時(shí)間復(fù)雜度。注意cmp_to_key這個(gè)關(guān)鍵字需要引入functools包。
按照貪心的策略來(lái)進(jìn)行排序，優(yōu)先按照左端從小到大進(jìn)行排序，如果左端相同則將右端較大的放在前面，如果前一個(gè)區(qū)間的右端點(diǎn)小于后一個(gè)區(qū)間的左端點(diǎn)，那么這兩個(gè)區(qū)間不會(huì)重合，否則兩個(gè)重復(fù)，新區(qū)間的右端點(diǎn)為這兩個(gè)區(qū)間有邊界的較大值。
改正，這個(gè)題目只需要對(duì)左邊界排序即可，其他的不用管。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
def compare(a, b):
if a[0] > b[0] or (a[0] == b[0] and a[1] < b[1]):
return 1
elif a[0] == b[0] and a[1] == b[1]:
return 0
else:
return -1
intervals.sort(key = cmp_to_key(compare))
res = [intervals[0]]
for left, right in intervals[1:]:
temp = res[-1]
if left > temp[1]: #注意是嚴(yán)格大于
res.append([left, right])
else:
res[-1][1] = max(right, temp[1])
return res
- 不同路徑
第一眼看上去像是簡(jiǎn)單的迷宮搜索問(wèn)題，可以直接嘗試暴力搜索，結(jié)果超時(shí)，這里我給了兩種寫法，第一種使用了標(biāo)記數(shù)組，后面發(fā)現(xiàn)是沒(méi)有必要的，因?yàn)楦鶕?jù)題意是絕對(duì)不會(huì)往回走的?；剡^(guò)頭來(lái)仔細(xì)看一下，這個(gè)題其實(shí)就是組合數(shù)的定義，或者我們也可以使用標(biāo)準(zhǔn)的DP來(lái)解決：
需要注意初始化的問(wèn)題，不然結(jié)果全為0。
解法1：超時(shí)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
self.count = 0
flags = [[0]*m for i in range(n)]
def dfs(x, y):
if x == n-1 and y == m-1:
self.count += 1
if x <0 or x >n-1 or y < 0 or y > m-1:
return
for (delta_x, delta_y) in [(0, 1), (1, 0)]:
if x+delta_x < 0 or x+delta_x > n-1 or y+delta_y <0 or y+delta_y > m-1:
continue
if flags[x+delta_x][y+delta_y] == 0:
flags[x+delta_x][y+delta_y] = 1
dfs(x+delta_x, y+delta_y)
flags[x+delta_x][y+delta_y] = 0
flags[0][0] = 1
dfs(0, 0)
return self.count
解法2：超時(shí)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
self.count = 0
def dfs(x, y):
if x == n-1 and y == m-1:
self.count += 1
if x <0 or x >n-1 or y < 0 or y > m-1:
return
dfs(x+1, y)
dfs(x, y+1)
dfs(0, 0)
return self.count
解法3：DP
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0]*(m + 2) for i in range(n+2)]
for i in range(1, n+1):
for j in range(1, m+1):
if i == 1 and j == 1:
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[n][m]
- 最小路徑和
同樣這一題是非常基礎(chǔ)的DP，按照我之前的寫法將數(shù)組外圍擴(kuò)充一下，但是這種寫法不能填充0，應(yīng)該填充一個(gè)很大的值。這個(gè)一定要注意。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
width = len(grid)
length = len(grid[0])
dp = [[0]*length for i in range(width)]
for i in range(0, width):
for j in range(0, length):
if i == 0 and j == 0:
dp[i][j] = grid[i][j]
elif i == 0 and j != 0:
dp[i][j] = dp[i][j-1] + grid[i][j]
elif i !=0 and j == 0:
dp[i][j] = dp[i-1][j] + grid[i][j]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]
- 爬樓梯
斐波拉契數(shù)列，注意初始值。
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
dp = [0]*n
dp[0] = 1
dp[1] = 2
for i in range(2, n):
dp[i] = dp[i-1] + dp[i-2]
return dp[n-1]
- 編輯距離
這一題也是經(jīng)典的DP，這一題與求兩個(gè)序列的最長(zhǎng)公共子序列這一題類似，同樣是二階DP。
假設(shè)現(xiàn)在有兩個(gè)字符串a(chǎn)，b，dp[i][j]表示a[:i]和b[:j]這兩個(gè)字串的最短編輯距離，那么我們可以得到相應(yīng)的狀態(tài)轉(zhuǎn)移方程：
a[i]=b[j]的時(shí)候很好理解，當(dāng)a[i]!=b[j]的時(shí)候，我們以a為例，我們可以將a[i]修改成和b[j]一樣的，這個(gè)時(shí)候就轉(zhuǎn)換成求dp[i-1][j-1]了，我們也可以直接將a[i]刪除，但是刪除a[i]之后，我們也無(wú)法去頂a[i-1]和b[j]是否相等，這個(gè)時(shí)候問(wèn)題轉(zhuǎn)換成求dp[i-1][j]，我們也可以在a[i]后面增加一個(gè)和b[j]一樣的元素，這個(gè)時(shí)候a[i+1]和b[j]是一樣的，然后問(wèn)題就轉(zhuǎn)換成dp[i][j-1]了。在具體實(shí)現(xiàn)的時(shí)候，我們需要添加一個(gè)空串，因?yàn)檫@樣容易初始化，因此代碼中會(huì)有相應(yīng)的調(diào)整。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
length1 = len(word1) + 1
length2 = len(word2) + 1
#print(length1, length2)
dp = [[0]*length1 for i in range(length2)]
for i in range(length2):
dp[i][0] = i
for j in range(length1):
dp[0][j] = j
for i in range(1, length2):
for j in range(1, length1):
if word2[i-1] == word1[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
#print(i, j)
dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))
return dp[-1][-1]
- 顏色分類
三色國(guó)旗問(wèn)題。官方題解寫的挺好的：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode/ ，關(guān)于這個(gè)算法其實(shí)也比較好理解。p0表示左邊界，p2表示右邊界，cur表示遍歷的當(dāng)前元素，因?yàn)樽罱K我們需要讓整個(gè)數(shù)組變成遞增的形式，當(dāng)nums[cur] = 2的時(shí)候，就需要和nums[p2]進(jìn)行交換，并且將p2左移，當(dāng)nums[cur] = 0的時(shí)候，就需要和nums[p1]進(jìn)行交換，并且cur和p1都要右移，當(dāng)nums[cur] = 1的時(shí)候，只需要cur右移即可。
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] == 2:
nums[cur], nums[p2] = nums[p2], nums[cur]
p2 -= 1
elif nums[cur] == 0:
nums[cur], nums[p0] = nums[p0], nums[cur]
cur += 1
p0 += 1
else:
cur += 1
- 最小覆蓋子串
同樣是經(jīng)典的滑動(dòng)窗口題目。需要維護(hù)兩個(gè)字典，和兩個(gè)指針。但是這一題需要子串覆蓋，因此窗口收縮的條件更為嚴(yán)格，不能簡(jiǎn)單的通過(guò)雙指針之間的距離大于等于目標(biāo)串的長(zhǎng)度就來(lái)進(jìn)行窗口收縮操作，這樣會(huì)增加時(shí)間復(fù)雜度。
class Solution:
def minWindow(self, s: str, t: str) -> str:
window = {}
need = {}
left = 0
right = 0
valid = 0
maxlength = inf
temp = 0
for c in t:
if c not in need:
need[c] = 1
else:
need[c] += 1
while(right < len(s)):
c = s[right]
right += 1
if c not in window:
window[c] = 1
else:
window[c] += 1
if c in need:
if window[c] == need[c]:
valid += 1
while(valid == len(need)): #這個(gè)收縮條件更為嚴(yán)格
if right - left < maxlength:
maxlength = right - left
temp = left
c = s[left]
left += 1
if c in need:
if need[c] == window[c]:
valid -= 1
window[c] -= 1
if maxlength == inf:
return ''
else:
return s[temp:temp+maxlength]
- 子集
類似于生成全排列，用一個(gè)深度優(yōu)先搜索最為直接。具體的實(shí)現(xiàn)的時(shí)候需要注意終止條件，這里不需要使用標(biāo)記數(shù)組來(lái)防止重復(fù)遍歷。
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
length = len(nums)
res = []
def dfs(count, route):
if count == length:
res.append(route)
return
for i in range(2):
if i == 1:
dfs(count + 1, route + [nums[count]])
else:
dfs(count + 1, route)
dfs(0, [])
return res
- 單詞搜索
同樣是DFS，但是這個(gè)DFS搜索稍微有點(diǎn)復(fù)雜。遞歸函數(shù)參數(shù)有3個(gè)，分別表示橫縱坐標(biāo)和走過(guò)的步數(shù)，由于這個(gè)題需要從所有可能的路徑中找出一條滿足題意的路徑，因此這一題需要采用for循環(huán)的寫法：用flags標(biāo)記數(shù)組來(lái)在防止同一條路徑上重復(fù)遍歷，并且還要保證不同的路徑之間互不影響。在進(jìn)行下一步遞歸的時(shí)候需要保證不越界、未走過(guò)、且保證當(dāng)前遍歷的元素與word中相同位置的元素相同這三個(gè)條件。最后需要注意的是，這一題需要剪枝，也就是當(dāng)找到一條滿足題意的路徑的時(shí)候，需要立刻將程序終止，否則會(huì)超時(shí)。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
length = len(board)
width = len(board[0])
flags = [[0]*width for i in range(length)]
self.res = 0
def dfs(x, y, count):
if count == len(word):
self.res = 1
return
for delta_x, delta_y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
if self.res == 1:
return
if x + delta_x >= 0 and x + delta_x <= length -1 and y + delta_y >= 0 and y + delta_y <= width - 1 and flags[x + delta_x][y + delta_y] == 0 and board[x+delta_x][y+delta_y] == word[count]:
flags[x + delta_x][y + delta_y] = 1
dfs(x + delta_x, y + delta_y, count + 1)
flags[x + delta_x][y + delta_y] = 0
for i in range(length):
for j in range(width):
if board[i][j] == word[0]:
flags[i][j] = 1
dfs(i, j, 1)
flags[i][j] = 0
if self.res == 1:
return True
return False
- 柱狀圖中最大的矩形
這一題與接雨水這一題神似，不同的是，接雨水那一題需要碰到更高的才會(huì)形成相應(yīng)的凹槽，而這一題是遇到更低的柱形之后，后面會(huì)有凹槽這樣無(wú)法形成對(duì)應(yīng)的矩形，只能計(jì)算前面的矩形了。因此這一題也需要使用到單調(diào)棧，單調(diào)不減的棧，這一同樣需要把元素索引入棧，因?yàn)樾枰?jì)算對(duì)應(yīng)的寬度，在計(jì)算寬度的時(shí)候還需要考慮前面是否有柱形，還有一個(gè)技巧就是在最后加上一個(gè)高度為0的柱形，計(jì)算寬度需要注意下，右邊界為當(dāng)前元素的位置，左邊界為出棧后的棧頂，沒(méi)有的話就為空。參考：https://blog.csdn.net/Zolewit/article/details/88863970
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights.append(0) #注意這一步
stack = []
res = 0
for i in range(len(heights)):
while(stack and heights[i] < heights[stack[-1]]):
mid = stack.pop()
right = i #注意這一步
if not stack:
width = right
else:
left = stack[-1] #注意這一步
width = right - left - 1
res = max(res, width*heights[mid])
stack.append(i)
return res
- 二叉樹的中序遍歷
題目要求使用非遞歸的方式來(lái)完成。這就需要定義一個(gè)棧來(lái)模擬系統(tǒng)棧的壓棧、彈棧過(guò)程。
在模擬中序遍歷的時(shí)候，同樣需要讓左子樹不斷入棧，直到最左邊即可。若當(dāng)前節(jié)點(diǎn)為空，則出棧并獲取棧頂元素的值，并將當(dāng)前元素更新到其右子樹的狀態(tài)。整個(gè)循環(huán)終止的條件為當(dāng)前節(jié)點(diǎn)為空且棧也為空。
詳細(xì)情況請(qǐng)參考：
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/die-dai-fa-by-jason-2/
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
cur = root
while(cur or stack):
while(cur):
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
- 不同的二叉搜索樹
簡(jiǎn)單的DP，dp[i]表示i個(gè)節(jié)點(diǎn)的樹能夠構(gòu)成二叉搜索的種類:
如果這一題是普通的二叉樹的話，就需要再乘以n!。
class Solution:
def numTrees(self, n: int) -> int:
dp = [0]*(n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
for j in range(0, i):
dp[i] += dp[j]*dp[i-1-j]
return dp[n]
- 驗(yàn)證二叉搜索樹
簡(jiǎn)單的遞歸函數(shù)即可，同樣需要設(shè)計(jì)好參數(shù)和返回值，遞歸函數(shù)其實(shí)比較簡(jiǎn)單，違反二叉樹的性質(zhì)就返回False，當(dāng)樹遍歷到空節(jié)點(diǎn)的時(shí)候返回True，因?yàn)檫@個(gè)時(shí)候表示在遍歷過(guò)程中沒(méi)有出現(xiàn)任何違反二叉搜索樹性質(zhì)的情況，最后當(dāng)所有的條件都滿足的時(shí)候，返回True即可。但是有一點(diǎn)需要注意，就是右子樹的每一個(gè)節(jié)點(diǎn)都要大于根節(jié)點(diǎn)，左子樹的每一個(gè)節(jié)點(diǎn)都要小于根節(jié)點(diǎn)，因此單獨(dú)地判斷每一個(gè)根節(jié)點(diǎn)和其左右子節(jié)點(diǎn)的大小關(guān)系是不夠的。這里第一種解法就是這種錯(cuò)誤的解法。
解法1：錯(cuò)誤的解法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if not root:
return True
if root.left:
if root.left.val >= root.val:
return False
if root.right:
if root.right.val <= root.val:
return False
left = self.isValidBST(root.left)
right = self.isValidBST(root.right)
if not left or not right:
return False
else:
return True
解法2：在遞歸函數(shù)的參數(shù)里設(shè)置上下界，lower和upper，注意是開區(qū)間：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
minNum = -9999999999
maxNum = 9999999999
def dfs(root, minNum, maxNum):
if not root:
return True
if root.val <= minNum or root.val >= maxNum:
return False
left = dfs(root.left, minNum, root.val)
right = dfs(root.right, root.val, maxNum)
if not left or not right:
return False
else:
return True
return dfs(root, minNum, maxNum)
- 對(duì)稱二叉樹
- 有一種最笨的辦法就是直接將這棵樹進(jìn)行交換然后再遍歷，如果遍歷的結(jié)果相同，那么說(shuō)明這是一顆對(duì)稱樹，這里強(qiáng)調(diào)一下，應(yīng)該使用先序遍歷，使用中序遍歷的話有些數(shù)據(jù)過(guò)不了。
- 建立一個(gè)合理的遞歸關(guān)系，直接對(duì)左右子樹進(jìn)行判斷，不滿足相應(yīng)的條件就返回False，滿足相應(yīng)的條件就返回True，但是要注意的一點(diǎn)是根節(jié)點(diǎn)為空需要單獨(dú)判讀，不能放在遞歸函數(shù)里，遞歸函數(shù)里的參數(shù)為兩個(gè)表示左右子樹。
解法1：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def swap(root):
if not root:
return None
newRoot = TreeNode()
temp1 = root.left
temp2 = root.right
root.left = swap(temp2)
root.right = swap(temp1)
'''
newRoot.val = root.val
newRoot.left = swap(root.right)
newRoot.right = swap(root.left)
return newRoot
'''
return root
def dfs(root):
if not root:
return ['null']
else:
left = dfs(root.left)
right = dfs(root.right)
return [root.val] + left + right
res1 = dfs(root)
newNode = swap(root)
res2 = dfs(newNode)
if res1 == res2:
return True
else:
return False
解法2：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def judge(left, right):
if not left and not right:
return True
if not left:
return False
if not right:
return False
if left.val != right.val:
return False
return judge(left.left, right.right) and judge(left.right, right.left)
if not root:
return True
if judge(root.left, root.right):
return True
else:
return False
