Python Hot100 学习笔记
这篇是我刷 Hot100 的总览页。
我会把每道题单独存到此篇笔记目录下的 .py 文件，并由页面自动读取展示。
目录
链表
二叉树
动态规划
代码
1. 两数之和
class Solution(object):
def twoSum(self, nums, target):
l = len(nums)
hashtable = dict()
for i in range(l):
if target - nums[i] in hashtable:
return [hashtable[target - nums[i]], i]
hashtable[nums[i]] = i
return []
49. 字母异位词分组
class Solution(object):
def groupAnagrams(self, strs):
mp = dict()
for s in strs:
key = "".join(sorted(s))
if key not in mp:
mp[key] = []
mp[key].append(s)
return list(mp.values())
128. 最长连续序列
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
hashset = set(nums)
maxlen = 0
for num in nums :
if num-1 not in hashset :
nowlen = 1
nex = num+1
while nex in hashset :
nex += 1
nowlen += 1
maxlen = max(nowlen,maxlen)
return maxlen
283. 移动零
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
length = len(nums)
putindex = 0
# 将非零元素依次放在前面
for i in range(length):
while putindex < length and nums[putindex] == 0:
putindex += 1
if putindex == length:
nums[i] = 0
else:
nums[i] = nums[putindex]
putindex += 1
11. 盛最多水的容器
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height)-1
maxArea = 0
while left < right :
area = (right-left) * min(height[right] , height[left])
maxArea = max( maxArea , area)
if height[right] < height[left] :
right -= 1
else :
left += 1
return maxArea
15. 三数之和
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
# 双重for + set找need 有重复
# 应该使用排序 + 双指针
l = len(nums)
nums.sort()
ans = []
for i in range(l) :
if i > 0 and nums[i] == nums[i-1] :
continue
need = -nums[i]
left = i+1
right = l-1
while left < right :
if nums[left]+nums[right] > need :
right -= 1
elif nums[left]+nums[right] < need :
left += 1
else :
ans.append([-need , nums[left] , nums[right]])
while left < right and nums[left] == nums[left + 1]: left += 1
while left < right and nums[right] == nums[right - 1]: right -= 1
left += 1
right -= 1
return ans42. 接雨水
class Solution:
def trap(self, height: List[int]) -> int:
l = len(height)
pre = 0
preheight = [0]*l
for i in range(l) :
pre = max(height[i],pre)
preheight[i] = pre
ans = 0
nex = 0
for j in range(l-1 , -1, -1) :
nex = max(height[j],nex)
ans += min(nex,preheight[j])-height[j]
return ans3. 无重复字符的最长子串
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s :
return 0
mp = {}
star , l = 0 , 1
# map中存在即重复 新的star = key+1
for i in range(len(s)) :
c = s[i]
if c not in mp or mp[c] < star :
l = max(l , i-star+1)
mp[c] = i
else :
star = mp[c]+1
mp[c] = i
return l438. 找到字符串中所有字母异位词
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
sl,pl = len(s),len(p)
if sl < pl :
return []
sMap,pMap = [0]*26 , [0]*26
ans = []
for i in range(pl) :
sMap[ ord(s[i]) - ord('a') ] += 1
pMap[ ord(p[i]) - ord('a') ] += 1
if sMap == pMap :
ans.append(0)
for i in range(0 , sl-pl) :
sMap[ ord(s[i])-ord('a') ] -= 1
sMap[ord(s[i+pl])-ord('a')] +=1
if sMap == pMap :
ans.append(i+1)
return ans560. 和为 K 的子数组
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
ans , nowsum = 0, 0
mp = {}
mp[0] = 1
for num in nums :
nowsum += num
need = nowsum - k
if need in mp :
ans += mp[need]
mp[nowsum] = mp.get(nowsum , 0) +1
return ans 239. 滑动窗口最大值
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
l = len(nums)
if k > l :
return []
left = 0
heap = []
ans = []
for i in range(l) :
# 存当前的元素
heapq.heappush(heap , (-nums[i] , i))
if i >= k-1 :
# 满了 存 拿 移动left
while heap[0][1] < left :
heapq.heappop(heap)
ans.append(-heap[0][0])
left += 1
return ans
#也可以存递减的下标 76. 最小覆盖子串
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(t) > len(s) :
return ""
tmap ={}
for tchar in t :
tmap[tchar] = tmap.get(tchar, 0) + 1
needchar = len(tmap)
left , star = 0 , -1
minLength = len(s) + 1
for right in range(len(s)) :
addchar = s[right]
if addchar in tmap:
tmap[addchar] -= 1
if tmap[addchar] == 0 : needchar -= 1
while needchar == 0 :
# 移除前面的无用字母
if s[left] not in tmap :
left += 1
# 以及多余字母
elif tmap[s[left]] < 0 :
tmap[s[left]] += 1
left += 1
# 当前最短有效
else :
if right-left+1 < minLength :
minLength = right-left+1
star = left
# 记录后 删除第一个有效字母
tmap[s[left]] += 1
needchar += 1
left += 1
if star == -1 : return ""
return s[star : star+minLength]53. 最大子数组和
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxsum,nowsum = nums[0],0
for right in range(len(nums)) :
nowsum += nums[right]
# 更新最大值
maxsum = max(maxsum,nowsum)
# 如果当前和小于0 就丢弃之前的和 从下一个开始
if nowsum < 0:
nowsum = 0
return maxsum56. 合并区间
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
pq = []
ans = []
for interval in intervals :
heapq.heappush(pq,interval)
while pq :
interval = heapq.heappop(pq)
while pq and pq[0][0] <= interval[1] :
add = heapq.heappop(pq)
interval[1] = max (interval[1],add[1])
ans.append(interval)
return ans189. 轮转数组
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.reverse()
l = len(nums)
k = k % l
left , right = 0 , k-1
while left < right :
temp = nums[left]
nums[left] = nums[right]
nums[right] = temp
left += 1
right -= 1
left ,right = k ,l-1
while left < right :
temp = nums[left]
nums[left] = nums[right]
nums[right] = temp
left += 1
right -= 1
238. 除了自身以外数组的乘积
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
l = len(nums)
pre, nex = [1]*l, [1]*l
for i in range(l-1) :
pre[i+1] = pre[i]*nums[i]
nex[l-2-i] = nex[l-1-i] * nums[l-1-i]
ans = [1]*l
for i in range(l) :
ans[i] = pre[i] * nex[i]
return ans41. 缺失的第一个正数
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
l = len(nums)
for index in range(l):
while 1 <= nums[index] <= l and nums[index] != index+1 and nums[nums[index]-1] != nums[index]:
temp = nums[index]
nums[index] = nums[temp-1]
nums[temp-1] = temp
for index in range(l):
if index+1 != nums[index] :
return index+1
return l+173. 矩阵置零
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
hst, lst=set(), set()
for i in range(len(matrix)) :
for j in range(len(matrix[i])) :
if matrix[i][j] == 0 :
hst.add(i)
lst.add(j)
for i in range(len(matrix)) :
for j in range(len(matrix[i])) :
if matrix[i][j] != 0 and ( i in hst or j in lst ) :
matrix[i][j] = 0
54. 螺旋矩阵
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
end, right= len(matrix)-1, len(matrix[0])-1
top, left = 0, 0
ans=[]
while top<=end and left<=right :
ans+=order(matrix,top,left,end,right)
top +=1
left +=1
end -=1
right -=1
return ans
def order(matrix,top,left,end,right)-> List[int]:
ans = []
for i in range(left,right+1):
ans.append(matrix[top][i])
for i in range(top+1,end+1):
ans.append(matrix[i][right])
if end-top>0 :
for i in range(right-1,left-1,-1):
ans.append(matrix[end][i])
if right-left>0 :
for i in range(end-1,top,-1):
ans.append(matrix[i][left])
return ans48. 旋转图像
class Solution:
def rotateSide(self,matrix,star,l) :
if l <= 1 :
return
left,right,top,end = star,star+l-1,star,star+l-1
for i in range(l-1):
# 1. 存下左上角
temp = matrix[top][left + i]
# 2. 左上角 = 左下角
matrix[top][left + i] = matrix[end - i][left]
# 3. 左下角 = 右下角
matrix[end - i][left] = matrix[end][right - i]
# 4. 右下角 = 右上角
matrix[end][right - i] = matrix[top + i][right]
# 5. 右上角 = 暂存的左上角 (temp)
matrix[top + i][right] = temp
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
l = len(matrix)
i = 0
while l > 0 :
# 类内定义的方法 类内调用必需使用self.
self.rotateSide(matrix,i,l)
l -= 2
i += 1
240. 搜索二维矩阵 II
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
# 右上搜 <t 说明在下面i++ >t 说明在左边 j--
i, j = 0,n-1
while i<m and j>=0 :
if matrix[i][j] == target :
return True
elif matrix[i][j] > target :
j -= 1
else :
i += 1
return False
160. 相交链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
linkset = set()
A = headA
while A :
linkset.add(A)
A = A.next
B = headB
while B :
if B in linkset :
return B
B = B.next
return None
206. 反转链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next :
return head
prehead = ListNode(0, head)
now = head.next
head.next = None
while now :
nex = now.next
now.next = prehead.next
prehead.next = now
now = nex
return prehead.next234. 回文链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if not head or not head.next :
return True
linkedStr = ""
while head :
linkedStr += str(head.val)
head = head.next
if linkedStr == linkedStr[::-1] :
return True
return Falsea141. 环形链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow,fast = head,head
while fast :
if fast.next and fast.next.next :
fast = fast.next.next
else :
return False
slow=slow.next
if fast == slow :
return True
return False
142. 环形链表 II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast , slow = head,head
while fast :
if fast.next and fast.next.next :
fast = fast.next.next
else : return None
slow = slow.next
if fast==slow :
fast = head
# a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
while fast != slow :
fast = fast.next
slow = slow.next
return fast
return None21. 合并两个有序链表
# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
prehead = ListNode()
nownode = prehead
p,q = list1,list2
while p and q :
if q.val < p.val :
nownode.next = q
q = q.next
nownode = nownode.next
else :
nownode.next = p
p = p.next
nownode = nownode.next
if p :
nownode.next = p
else :
nownode.next = q
return prehead.next2. 两数相加
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
add = 0
prehead = ListNode()
now = prehead
while l1 and l2 :
val = l1.val+l2.val+add
add = val // 10
val %= 10
node = ListNode(val)
now.next = node
now = now.next
l1 = l1.next
l2 = l2.next
if l1 :
while l1 and add != 0 :
val = l1.val+add
add = val // 10
val %= 10
node = ListNode(val)
now.next = node
now = now.next
l1 = l1.next
now.next=l1
else :
while l2 and add != 0 :
val = l2.val+add
add = val // 10
val %= 10
node = ListNode(val)
now.next = node
now = now.next
l2 = l2.next
now.next=l2
if add != 0 :
now.next = ListNode(add)
return prehead.next19. 删除链表的倒数第 N 个结点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
prehead = ListNode(0,head)
fast , slow = prehead, prehead
setp = 0
while fast.next :
if setp >= n :
slow = slow.next
fast = fast.next
setp += 1
slow.next = slow.next.next
return prehead.next24. 两两交换链表中的节点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapTwo(self,p1,p2):
p1.next = p2.next
p2.next = p2.next.next
p1.next.next= p2
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next :
return head
prehead = ListNode(0,head)
a,b = prehead,head
while a.next and b.next :
self.swapTwo(a,b)
a = b
b = b.next
return prehead.next
25. K 个一组翻转链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseOnce(self,pre,k):
end = pre.next
for i in range(k-1):
now = end.next
end.next = now.next
now.next = pre.next
pre.next = now
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if k == 1 or not head : return head
prehead = ListNode(0,head)
pre = prehead
now , num = head , 0
while pre and now :
num += 1
nex = now.next
if num == k :
nextpre = pre.next
self.reverseOnce(pre,k)
num = 0
pre = nextpre
now = nex
return prehead.next
138. 随机链表的复制
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
prehead = Node(0)
nownode = prehead
oldnode = head
mp = {}
while oldnode :
newnode = Node(oldnode.val)
mp[oldnode] = newnode
oldnode = oldnode.next
nownode.next = newnode
nownode = nownode.next
oldnode , nownode = head , prehead.next
while oldnode :
if oldnode.random :
nownode.random = mp[oldnode.random]
nownode = nownode.next
oldnode = oldnode.next
return prehead.next
148. 排序链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
# 快拍错误 因为链表每次自动选择第一个点固定位置特殊情况时间复杂度为n2
# 归并
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next :
return head
# 简化1：快慢指针找中点的标准模板
fast, slow = head.next, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
left = self.sortList(head)
right = self.sortList(mid)
return self.merge(left,right)
def merge(self,slow,fast):
prehead = ListNode()
prenow = prehead
while slow and fast :
if slow.val < fast.val :
prenow.next = slow
slow = slow.next
prenow = prenow.next
else :
prenow.next = fast
fast = fast.next
prenow = prenow.next
if slow :
prenow.next = slow
else :
prenow.next = fast
return prehead.next23. 合并 K 个升序链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
newlist = []
while len(lists) > 1 :
for i in range(0, len(lists), 2) :
if i+1 < len(lists):
newlist.append(self.mergeTwo(lists[i],lists[i+1]))
else :
newlist.append(lists[i])
lists = newlist
newlist = []
'''
可以换成双端队列
dq = deque(lists)
while len(dq) > 1 :
a,b = dq.pop() ,dq.pop()
dq.appendleft( self.mergeTwo(a,b) )
'''
if not lists : return None
else : return lists[0]
def mergeTwo(self,l1,l2) :
prehead = ListNode()
pre = prehead
while l1 and l2 :
if l1.val<l2.val :
pre.next = l1
l1 = l1.next
pre = pre.next
else :
pre.next = l2
l2 = l2.next
pre = pre.next
pre.next = l1 if l1 else l2
return prehead.next146. LRU 缓存
class LRUCache:
def __init__(self, capacity: int):
self.capacity= capacity
self.mp = {}
self.head , self.end= ListNode(), ListNode()
self.head.next = self.end
self.end.pre = self.head
def get(self, key: int) -> int:
if key in self.mp :
node = self.mp[key]
node.remove()
node.add(self.end)
return node.val
else :
return -1
def put(self, key: int, value: int) -> None:
if key in self.mp : # 存在删链表
self.mp[key].remove()
else : # 不存在 添加mp
self.mp[key] = ListNode(key)
# 更新
node = self.mp[key]
node.val = value
node.add(self.end)
# 容量校验
if len(self.mp) > self.capacity:
old_node = self.head.next
old_node.remove()
del self.mp[old_node.key]
class ListNode:
def __init__(self,key=-1,val=-1, pre=None, nex=None):
self.key,self.val ,self.pre ,self.next =key, val , pre , nex
def remove(self) :
self.pre.next=self.next
self.next.pre=self.pre
def add(self,end) :
self.pre=end.pre
self.next=end
self.pre.next=self
self.next.pre=self
94. 二叉树的中序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root : return []
ans = []
if root.left :
ans += self.inorderTraversal(root.left)
ans.append(root.val)
if root.right :
ans += self.inorderTraversal(root.right)
return ans104. 二叉树的最大深度
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root : return 0
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
return max(left,right)+1226. 翻转二叉树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root : return None
temp = root.left
root.left = root.right
root.right = temp
if root.left : self.invertTree(root.left)
if root.right : self.invertTree(root.right)
return root101. 对称二叉树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root : return True
left ,right = root.left , root.right
larr ,rarr =[],[]
larr.append(left)
rarr.append(right)
while larr and rarr :
left = larr.pop()
right = rarr.pop()
if not left and not right : continue
if not left or not right or left.val != right.val :
return False
larr.append(left.left)
larr.append(left.right)
rarr.append(right.right)
rarr.append(right.left)
return True543. 二叉树的直径
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
# 备注： 需要重新做
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
if not root : return 0
self.ans = 0
def deep(node) :# 点的深度 leftdeep + rightdeep == 边数
if not node : return 0
L = deep(node.left)
R = deep(node.right)
self.ans = max(self.ans , L+R)
return max(L,R)+1
deep(root)
return self.ans102. 二叉树的层序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root : return []
ans = []
nodes = deque()
nodes.append(root)
while nodes :
l,lay = len(nodes),[]
for _ in range(l) :
node = nodes.popleft()
lay.append(node.val)
if node.left : nodes.append(node.left)
if node.right : nodes.append(node.right)
ans.append(lay)
return ans108. 将有序数组转换为二叉搜索树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if not nums: return None
mid = len(nums)//2
left = self.sortedArrayToBST(nums[:mid])
right = self.sortedArrayToBST(nums[mid+1:])
root = TreeNode(nums[mid],left,right)
return root98. 验证二叉搜索树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if not root : return True
def midarr(root) :
if not root : return []
ans = []
ans += midarr(root.left)
ans.append(root.val)
ans += midarr(root.right)
return ans
arr = midarr(root)
for i in range(len(arr)):
if i <1 :continue
if arr[i-1] >= arr[i] : return False
return True 230. 二叉搜索树中第 K 小的元素
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
def midarr(root) :
if not root : return []
ans = []
ans += midarr(root.left)
ans.append(root.val)
ans += midarr(root.right)
return ans
arr = midarr(root)
return arr[k-1]199. 二叉树的右视图
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root : return []
dq = deque()
dq.append(root)
ans = []
while dq:
size = len(dq)
for _ in range(size):
node = dq.popleft()
if node.left : dq.append(node.left)
if node.right : dq.append(node.right)
if _ == size-1 : ans.append(node.val)
return ans
114. 二叉树展开为链表
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if not root : return
prehead = TreeNode(0,None,root)
pre = prehead
stack = []
stack.append(root)
while stack :
node = stack.pop()
if node.right : stack.append(node.right)
if node.left :
stack.append(node.left)
node.left = None
pre.right = node
pre = pre.right105. 从前序与中序遍历序列构造二叉树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder : return None
node = TreeNode()
node.val = preorder[0]
index = inorder.index(preorder[0])
left = self.buildTree(preorder[1:1+index],inorder[:index])
right = self.buildTree(preorder[1+index:],inorder[index+1:])
node.left = left
node.right = right
return node437. 路径总和 III
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
if not root : return 0
ans = 0
mp = {} # dict()
mp[root] = [root.val]
if root.val == targetSum : ans += 1
nodes = []
nodes.append(root)
while nodes:
node = nodes.pop()
if node.left :
left = node.left
nodes.append(left)
mp[left] = [left.val]
if left.val == targetSum : ans += 1
for preval in mp[node]:
if preval + left.val == targetSum : ans += 1
mp[left].append( preval + left.val)
if node.right :
right = node.right
nodes.append(right)
mp[right] = [right.val]
if right.val == targetSum : ans += 1
for preval in mp[node]:
if preval + right.val == targetSum : ans += 1
mp[right].append( preval + right.val)
return ans236. 二叉树的最近公共祖先
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 需要重做
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root : return None
if root == p or root == q : return root
left = self.lowestCommonAncestor(root.left,p,q)
right = self.lowestCommonAncestor(root.right,p,q)
if left and right : return root
elif left : return left
else : return right124. 二叉树中的最大路径和
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
if not root : return 0
self.maxsum = root.val
def onePath(node):
if not node : return 0
left = onePath(node.left)
right = onePath(node.right)
mx= max(left,right,0)+ node.val
self.maxsum = max(self.maxsum,left+right+node.val,mx)
return mx
onePath(root)
return self.maxsum200. 岛屿数量
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def land(grid,i,j,m,n):
if not 0<=i<m or not 0<=j<n : return
if grid[i][j] == "0" : return
else :
grid[i][j] = "0"
land(grid,i+1,j,m,n)
land(grid,i-1,j,m,n)
land(grid,i,j+1,m,n)
land(grid,i,j-1,m,n)
num,m,n = 0 ,len(grid),len(grid[0])
for i in range(m) :
for j in range(n):
if grid[i][j] == "1":
num += 1
land(grid,i,j,m,n)
return num
994. 腐烂的橘子
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
if not grid : return 0
m,n = len(grid) , len(grid[0])
unfresh ,freshnum= set() , 0
for i in range(m) :
for j in range(n) :
if grid[i][j]==2 :
unfresh.add((i,j))
if grid[i][j]==1 :
freshnum += 1
time = 0
while unfresh :
newunfresh = set()
for uf in unfresh :
dirct = [(1,0),(-1,0),(0,1), (0,-1)]
for d in dirct:
ni,nj = uf[0]+d[0], uf[1]+d[1]
if 0<=ni<m and 0<=nj<n and grid[ni][nj]==1 :
freshnum -= 1
grid[ni][nj] = 2
newunfresh.add((ni,nj))
if not newunfresh : break
unfresh = newunfresh
time += 1
if freshnum == 0:
return time
return -1
207. 课程表
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
needCourses ,canLearn,havelearn= [0]*numCourses ,{},0
for i in range(numCourses) :
canLearn[i] = set()
for request in prerequisites :
needCourses[request[0]] += 1
canLearn[request[1]].add(request[0])
learn = []
for i in range(numCourses) :
if needCourses[i] == 0 :
learn.append(i)
while learn :
lc = learn.pop()
havelearn += 1
for prelearn in canLearn[lc]:
needCourses[prelearn] -= 1
if needCourses[prelearn] == 0:
learn.append(prelearn)
if havelearn != numCourses : return False
return True208. 实现 Trie (前缀树)
class TreeNode:
def __init__(self,end=False):
self.isEnd = end
self.sun = [None]*26
class Trie:
def __init__(self):
self.head = TreeNode()
def insert(self, word: str) -> None:
if not str : return
node = self.head
for char in word :
index = ord(char) - ord('a')
if not node.sun[index] :
node.sun[index] = TreeNode()
node = node.sun[index]
node.isEnd = True
def search(self, word: str) -> bool:
node = self.head
for char in word :
index = ord(char) - ord('a')
if node.sun[index] :
node = node.sun[index]
else :
return False
return node.isEnd
def startsWith(self, prefix: str) -> bool:
node = self.head
for char in prefix :
index = ord(char) - ord('a')
if node.sun[index] :
node = node.sun[index]
else :
return False
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)46. 全排列
class Solution:
# 使用deque 不断pop左 append右
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums : return []
nums = deque(nums)
self.ans = []
self.addans(nums,[])
return self.ans
def addans(self,nums,nowans):
if not nums :
self.ans.append(nowans[:]) # 必需拷贝
for i in range(len(nums)):
num = nums.popleft()
nowans.append(num)
self.addans(nums,nowans)
nowans.pop()
nums.append(num)
class Solution: # 直接交换不同位置
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums : return []
def traceback(first = 0):
if first == n : ans.append(nums[:])
for i in range(first,n):
nums[i],nums[first] = nums[first],nums[i]
traceback(first+1)
nums[i],nums[first] = nums[first],nums[i]
n = len(nums)
ans = []
traceback()
return ans
78. 子集
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
# 递归回溯
if not nums : return []
ans ,n= [] ,len(nums)
def choose(index=0 , addnums=[]):
if index == n :
ans.append(addnums[:])
return
addnums.append(nums[index])
choose(index+1,addnums)
addnums.pop()
choose(index+1,addnums)
choose()
return ans
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
# 位运算 0~2^n-1 每个数的二进制表示一个子集
ans ,n= [] ,len(nums)
for i in range(2**n):
thistime ,index= [],0
while i != 0:
if i % 2 == 1 :
thistime.append(nums[index])
index += 1
i = i>>1
ans.append(thistime)
return ans17. 电话号码的字母组合
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits : return []
mp = [
[], # 0 键
[], # 1 键
['a', 'b', 'c'], # 2 键
['d', 'e', 'f'], # 3 键
['g', 'h', 'i'], # 4 键
['j', 'k', 'l'], # 5 键
['m', 'n', 'o'], # 6 键
['p', 'q', 'r', 's'],# 7 键
['t', 'u', 'v'], # 8 键
['w', 'x', 'y', 'z'] # 9 键
]
que = deque()
que.append("")
for dig in digits :
index = ord(dig) - ord('0')
size = len(que)
for _ in range(size):
pre = que.popleft()
for add in mp[index]:
que.append(pre+add)
return list(que)39. 组合总和
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
mp = [None]*(target+1)
mp[0],mp[target] = [[]],[]
for num in candidates:
for i in range(num,target+1):
if mp[i-num] :
if not mp[i] : mp[i] = []
for arr in mp[i-num] :
narr = arr + [num]
mp[i].append(narr)
return mp[target]22. 括号生成
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def addchar(left=n,right=0,nowstr=''):
if left == 0 and right == 0 :
ans.append(nowstr)
elif left == 0 :
nowstr += ')'*right
ans.append(nowstr)
else :
addchar(left-1,right+1,nowstr+'(')
if right > 0 :
addchar(left,right-1,nowstr+')')
ans = []
addchar()
return ans79. 单词搜索
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not board : return False
m , n =len(board),len(board[0])
used = [None]*m
for i in range(m) : used[i]=[False]*n
star=[]
for i in range(m) :
for j in range(n):
if board[i][j]==word[0] :
star.append([i,j])
def findnext(i,j,index):
if index == len(word) :
return True
dirc = [[1,0],[-1,0],[0,1],[0,-1]]
ans = False
for d in dirc:
ni,nj = i+d[0],j+d[1]
if 0<=ni<m and 0<=nj<n and not used[ni][nj] and board[ni][nj] == word[index]:
used[ni][nj]=True
ans = findnext(ni,nj,index+1)
if ans : return ans
used[ni][nj]=False
return False
ans = False
for s in star:
i , j = s
used[i][j]=True
ans = findnext(i,j,1)
if ans :
return True
used[i][j]=False
return False131. 分割回文串
class Solution:
def partition(self, s: str) -> List[List[str]]:
# 自己写的 多次递归 每次找切不切的点 复杂度较高
def split(star=0,index=0,nowans=[]):
if star == len(s):
ans.append(nowans[:])
elif index == len(s):
return
else :
if s[star:index+1] == s[star:index+1][::-1] :# 分
nowans.append(s[star:index+1])
split(index+1,index+1,nowans)
nowans.pop()
split(star,index+1,nowans) # 不分
ans = []
split()
return ans
class Solution:
def partition(self, s: str) -> List[List[str]]:
ans = []
#从开始位置 找所有可以切的点进行下面的遍历 切光为止
# 这个递归函数的目标无比纯粹：从 start 开始，把剩下所有的回文切片找出来
def backtrack(start: int, nowans: List[str]):
# 逻辑终点：整根“黄瓜”都被切完了，说明前面每一步的切法都合法！
if start == len(s):
ans.append(nowans[:]) # 存入最终结果
return
# 核心循环：枚举当前这一刀切在哪个位置（i 从 start 一路切到末尾）
for i in range(start, len(s)):
sub_str = s[start:i+1] # 这一刀切下来的片段
# 核心校验：只有切下来的片段是回文，这一刀才算切成功了
if sub_str == sub_str[::-1]:
nowans.append(sub_str) # 1. 把切下来的这段装进盘子里
backtrack(i + 1, nowans) # 2. 递归：让下一个人从 i+1 的位置继续往后切
nowans.pop() # 3. 回溯：把这段拿出来，腾出地方尝试“切得更长一点”
backtrack(0, [])
return ans51. N 皇后
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
if n == 0 : return []
# left = i+j right = j-i
left ,right,col= [False]*(2*n-1),[False]*(2*n-1),[False]*n
def putQueen(index=0,nowans=[]):
if index == n :
ans.append(nowans[:])
return
i , put = index,['.']*n
for j in range(n):
if not left[i+j] and not right[j-i] and not col[j] :
left[i+j] , right[j-i] , col[j] = True,True,True
put[j]='Q'
putstr = ""
for c in put : putstr += c
nowans.append(putstr)
putQueen(index+1,nowans)
nowans.pop()
put[j]='.'
left[i+j] , right[j-i] , col[j] = False,False,False
ans=[]
putQueen()
return ans
35. 搜索插入位置
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
def half(left=0 ,right=n-1):
if target > nums[right] : return right+1
elif target < nums[left] : return left
else :
mid = (right + left)//2
if nums[mid] == target :
return mid
elif nums[mid] < target :
return half(mid+1,right)
else :
return half(left,mid-1)
return half()74. 搜索二维矩阵
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix : return False
m ,n = len(matrix) , len(matrix[0])
i , j = 0 , 0
while i < m:
if target == matrix[i][0] : return True
if target < matrix[i][0] :
break
else : i += 1
i -= 1
if i<0 : return False
while j < n:
if target == matrix[i][j] : return True
if target > matrix[i][j] :
j += 1
else : return False
return False34. 在排序数组中查找元素的第一个和最后一个位置
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def half(left,right):
if left>right : return [-1,-1]
if nums[left]==target and nums[right]==target:
return (left,right)
mid = (left+right) // 2
if nums[mid]==target:
a = half(left,mid-1)
b = half(mid+1,right)
c = [mid,mid]
if a[0] != -1 : c[0]=a[0]
if b[1]!= -1 : c[1]=b[1]
return c
elif nums[mid] < target:
return half(mid+1,right)
else : return half(left,mid-1)
n = len(nums)
return half(0,n-1)33. 搜索旋转排序数组
class Solution:
def search(self, nums: List[int], target: int) -> int:
def half(left,right):
if left>right: return -1
mid = (left+right)//2
if nums[mid]==target:
return mid
else :
if nums[left]<=nums[mid]: # 左有序
if nums[left]<=target<=nums[mid] :
return half(left,mid-1)
else: return half(mid+1,right)
else: # 右 有序
if nums[mid]<=target<=nums[right]:
return half(mid+1,right)
else: return half(left,mid-1)
return half(0,len(nums)-1)153. 寻找旋转排序数组中的最小值
class Solution:
def findMin(self, nums: List[int]) -> int:
def half(left,right):
if nums[left]<=nums[right] :
return nums[left]
mid = (left+right)//2
if nums[left]<= nums[mid] : # 左 有序
return half(mid+1,right)
else :
if mid>0 and nums[mid]>nums[mid-1] :# 右增 left > right mid > mid-1
return half(left+1,mid-1)
else : return nums[mid]
n = len(nums)
return half(0,n-1)4. 寻找两个正序数组的中位数
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 从 0 开始 index 0，1//2 ==0
# 从 1 开始 index 1 直接min 2 //2 ==1
# 需要重做
def half(l1,l2,index):
if l1==n1 :
return nums2[l2+index-1]
if l2==n2 :
return nums1[l1+index-1]
if index == 1 :
return min(nums1[l1],nums2[l2])
hf = index//2
mid1 , mid2= min(l1+hf-1 , n1-1),min(l2+hf-1 , n2-1)
if nums1[mid1] > nums2[mid2] :
return half(l1,mid2+1,index-(mid2+1-l2))
else :
return half(mid1+1,l2,index-(mid1+1-l1))
n1,n2 =len(nums1),len(nums2)
if (n1+n2)%2 == 1:
return half(0,0,(n1+n2+1)//2)
else :
return ( half(0,0,(n1+n2)//2) + half(0,0,(n1+n2)//2+1) ) /2
20. 有效的括号
class Solution:
def isValid(self, s: str) -> bool:
stack =[]
for char in s :
if not stack :
if char in "}])" : return False
stack.append(char)
else:
if char in "{([" :
stack.append(char)
elif char==')' and stack[-1]=='(' :
stack.pop()
elif char==']' and stack[-1]=='[' :
stack.pop()
elif char=='}' and stack[-1]=='{' :
stack.pop()
else : stack.append(char)
if stack : return False
return True
155. 最小栈
class MinStack:
def __init__(self):
self.nums = []
self.nummap ,self.minstack = {} ,[]
def push(self, val: int) -> None:
self.nums.append(val)
self.nummap[val] = self.nummap.get(val,0) + 1
# 有最小值 可能已经被删除了
# erro {}中查找没有的值 会报错 KeyError！ 直接用get
# while self.minstack and not self.nummap[self.minstack[-1]] : self.minstack.pop()
while self.minstack and self.nummap.get(self.minstack[-1],0)==0 : self.minstack.pop()
if not self.minstack :
self.minstack.append(val)
else : # 单向的push pop 维护一个以进队顺序的递减最小值
# 还有最小值
if val < self.minstack[-1] :
self.minstack.append(val)
def pop(self) -> None:
num = self.nums.pop()
self.nummap[num] -= 1
# 归0 即可 删除多一步操作 浪费时间
# if self.nummap[num] == 0 : del self.nummap[num]
def top(self) -> int:
return self.nums[-1]
def getMin(self) -> int:
# 有最小值 可能已经被删除了
while self.minstack and self.nummap.get(self.minstack[-1],0)==0 : self.minstack.pop()
if not self.minstack : return None
return self.minstack[-1]
# leetcode 标答 确实没必要存之前比来比去的 维护最小值stack
# val > stack[-1] : stack.append(stack[-1])
# val <= stack[-1] : stack.append(val)
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [math.inf]
def push(self, x: int) -> None:
self.stack.append(x)
self.min_stack.append(min(x, self.min_stack[-1]))
def pop(self) -> None:
self.stack.pop()
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
394. 字符串解码
class Solution:
def decodeString(self, s: str) -> str:
ans = ""
numstack,charstack = [] ,[]
i = 0
while i < len(s) :
char = s[i]
if "0"<= char <= "9" :
num = char
while i+1 < len(s) and "0"<= s[i+1] <= "9" :
i += 1
num += s[i]
numstack.append(int(num))
elif char == "]":
nowstr = ""
while charstack[-1] != "[" : nowstr = charstack.pop() + nowstr
charstack.pop()
num = numstack.pop()
endstr = nowstr*num
charstack.append(endstr)
else :
charstack.append(char)
i += 1
while charstack : ans = charstack.pop() + ans
return ans739. 每日温度
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
premax , i= len(temperatures)-1, len(temperatures)-1
ans = [0]*len(temperatures)
# 单调栈 每次入栈时pop出小于当前的所有元素并更新answer[i] = new - old
while i >= 0 :
if temperatures[i] < temperatures[premax] :
j = i + 1
while j < premax and temperatures[i] >= temperatures[j] :
j += ans[j]
ans[i] = j-i
else :
ans[i] = 0
premax = i
i -= 1
return ans84. 柱状图中最大的矩形
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
# 计算前后小于它的位置 及可算出以该点为高的最大面积
n = len(heights)
premin , nextmin = [-1]*n , [n]*n
stack = []
for i in range(n):
height = heights[i]
if not stack :
stack.append(i)
else :
if height >= heights[stack[-1]]:
stack.append(i)
else :
while stack and height < heights[stack[-1]] :
index = stack.pop()
nextmin[index] = i
stack.append(i)
stack.clear()
for i in range(n-1, -1, -1):
height = heights[i]
if not stack :
stack.append(i)
else :
if height >= heights[stack[-1]] :
stack.append(i)
else :
while stack and height < heights[stack[-1]] :
index = stack.pop()
premin[index] = i
stack.append(i)
stack.clear()
maxarr = 0
for i in range(n):
nowarr = heights[i]*(nextmin[i]-premin[i]-1)
maxarr = max(maxarr,nowarr)
return maxarr
# 暴力超时
# ans , n = 0 , len(heights)
# for star in range(n) :
# nowarr , end , minh =heights[star] , star+1 , heights[star]
# while end < n :
# minh = min(minh,heights[end])
# nowarr = max(nowarr, minh*(end-star+1))
# ans = max(ans,nowarr)
# end += 1
# ans = max(ans,nowarr)
# return ans215. 数组中的第K个最大元素
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
n = len(nums)
def halffind(star,end,index):
if star == end :
return nums[star]
sig = nums[random.randint(star,end)]
p , q = star-1, end+1
while True:
p += 1
while nums[p] < sig :
p += 1
q -= 1
while nums[q] > sig :
q -= 1
if p >= q: break
nums[p],nums[q] = nums[q],nums[p]
if q < index:
return halffind(q+1,end,index)
else :
return halffind(star,q,index)
return halffind(0,n-1,n-k)
347. 前 K 个高频元素
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
if k == 0 : return []
nummap = {}
for num in nums:
nummap[num] = nummap.get(num,0) + 1
heap = []
for nownum in nummap :
if not heap or len(heap)<k :
heapq.heappush(heap,(nummap[nownum],nownum))
else :
if heap[0][0] < nummap[nownum] :
heapq.heappop(heap)
heapq.heappush(heap,(nummap[nownum],nownum))
ans = []
while heap:
ans.append(heapq.heappop(heap)[1])
return ans
295. 数据流的中位数
class MedianFinder:
# 双队列 左右分别存储较小和较大的数，保持平衡
def __init__(self):
self.minpq , self.maxpq = [] , []
def addNum(self, num: int) -> None:
qmin , qmax = self.minpq , self.maxpq
if not qmin or num <= -qmin[0] :
heapq.heappush(qmin,-num)
if len(qmax)+1 < len(qmin):
heapq.heappush(qmax,-heapq.heappop(qmin))
else :
heapq.heappush(qmax,num)
if len(qmin) < len(qmax):
heapq.heappush(qmin,-heapq.heappop(qmax))
def findMedian(self) -> float:
if len(self.maxpq) == len(self.minpq) :
return (self.maxpq[0] - self.minpq[0])/2
else :
return -self.minpq[0]
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()121. 买卖股票的最佳时机
class Solution:
def maxProfit(self, prices: List[int]) -> int:
nex = 0
n = len(prices)
ans = 0
for i in range(n-1,-1,-1):
ans = max(ans, nex-prices[i])
nex = max(prices[i],nex)
return ans
55. 跳跃游戏
class Solution:
def canJump(self, nums: List[int]) -> bool:
maxstep ,nowstep= 0,0
n = len(nums)
while nowstep<=maxstep:
maxstep = max(maxstep , nowstep+nums[nowstep])
nowstep += 1
if maxstep >= n-1 :
break
if maxstep >= n-1 :
return True
return False45. 跳跃游戏 II
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
canjump ,steps= deque() , [-1]*n
canjump.append(0)
steps[0] = 0
while canjump :
now = canjump.popleft() # 0
jump = nums[now] # 2
for i in range(1,jump+1): # 1-2
nex = now+i # 1
if nex >= n : break
if steps[nex]==-1 :
steps[nex] = steps[now]+1
canjump.append(nex)
elif steps[nex] > steps[now]+1 :
steps[nex] = steps[now]+1
return steps[n-1]
# 贪心算法 ： 每次更新最远距离 超过当前步的最远距离就 增加步数
class Solution:
def jump(self, nums: List[int]) -> int:
step ,maxjump ,nowend= 0 , 0 ,0
n = len(nums)
for i in range(n-1):
if maxjump >= i :
maxjump = max(maxjump, i+nums[i])
if i == nowend:
nowend = maxjump
step += 1
return step 763. 划分字母区间
class Solution:
def partitionLabels(self, s: str) -> List[int]:
charmap = {}
for i in range(len(s)) :
char = s[i]
charmap[char] = i
ans = []
nowstar ,nowend = 0 , charmap[s[0]]
for i in range(len(s)) :
nowend = max(nowend, charmap[s[i]])
if i == nowend :
ans.append(i-nowstar+1)
nowstar = i+1
return ans70. 爬楼梯
class Solution:
def climbStairs(self, n: int) -> int:
dp = [1]*(n+1)
for i in range(2,n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]118. 杨辉三角
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows < 1 : return []
ans = [None]*numRows
for i in range(1,numRows+1):
row = [1]*i
for j in range(i):
if j == 0 or j == i-1:
continue
row[j] = ans[i-2][j-1]+ans[i-2][j]
ans[i-1] = row
return ans198. 打家劫舍
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0]*(n+1)
dp[1] = nums[0]
for i in range(2,n+1):
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
return dp[n]279. 完全平方数
class Solution:
def numSquares(self, n: int) -> int:
dp = [n]*(n+1)
dp[0] = 0
for i in range(1,int(sqrt(n))+1):
add = i**2
for j in range(add,n+1):
dp[j] = min(dp[j],dp[j-add]+1)
return dp[n]
322. 零钱兑换
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [-1]*(amount+1)
dp[0] = 0
coins.sort()
for coin in coins:
for i in range(coin,amount+1):
if dp[i-coin] != -1 : # 可以通过 + i获得
if dp[i] == -1 :
dp[i] = dp[i-coin]+1
else :
dp[i] = min(dp[i] , dp[i-coin]+1)
return dp[amount]
139. 单词拆分
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
lens= len(s)
dp = [False]*(lens+1)
dp[0] = True
for end in range(1,len(s)+1):
for star in range(0,end):
if dp[star] and s[star:end] in wordDict :
dp[end] = True
break
return dp[lens]300. 最长递增子序列
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
stack = []
for num in nums:
if not stack :
stack.append(num)
else :
if num > stack[-1]:
stack.append(num)
else : # 小于当前最大
# 替换 里面第一个大于它的
index = len(stack)-1
while index >= 0 and stack[index] >= num :
index -= 1
stack[index+1] = num
return len(stack)152. 乘积最大子数组
class Solution:
def maxProduct(self, nums: List[int]) -> int:
maxsun , minsun ,ans= nums[0] , nums[0] , nums[0]
for num in nums[1:] :
newnim = min(maxsun*num , minsun*num , num)
newmax = max(maxsun*num , minsun*num , num)
ans = max(ans , newmax)
maxsun , minsun = newmax ,newnim
return ans416. 分割等和子集
class Solution:
def canPartition(self, nums: List[int]) -> bool:
numsum = sum(nums)
if numsum % 2 != 0 : return False
target = numsum//2
canto = set()
canto.add(0)
nums.sort()
for num in nums:
newcanto = set()
for i in range(num,target+1):
if i not in canto and i-num in canto :
newcanto.add(i)
canto.update(newcanto)
if target in canto :
return True
return False
32. 最长有效括号
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s : return 0
stack = []
for i in range(len(s)):
if not stack :
stack.append(i)
else :
if s[i] == ')' and s[stack[-1]] == '(' :
stack.pop()
else :
stack.append(i)
end , ans = len(s)-1 ,0
while stack :
sun = end - stack[-1]
end = stack.pop() - 1
ans = max(ans , sun)
ans = max(ans , end + 1)
return ans62. 不同路径
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [None]*(m+1)
for i in range(m+1) : dp[i] = [0]*(n+1)
for i in range(1,m+1) :
for j in range(1,n+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[m][n]64. 最小路径和
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m , n = len(grid),len(grid[0])
dp = [None]*m
for i in range(m) : dp[i] = [-1]*n
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
dp[i][j] = grid[i][j]
else :
if i>0 and j>0 :
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
elif i>0 :
dp[i][j] =dp[i-1][j] + grid[i][j]
else :
dp[i][j] =dp[i][j-1] + grid[i][j]
return dp[m-1][n-1]5. 最长回文子串
class Solution:
def longestPalindrome(self, s: str) -> str:
# dp[i][j] = str[i:j+1] is hui ?
n = len(s)
dp= [None]*n
for i in range(n):
dp[i] = [None]*(n)
for j in range(n):
if j<=i : dp[i][j] = True
else : dp[i][j] = False
maxlength , maxstar = 1 , 0
for length in range(2,n+1) :
for star in range(n-length+1) :
end = star+length-1
if s[star] == s[end] and dp[star+1][end-1] :
dp[star][end] = True
if length > maxlength :
maxlength = length
maxstar = star
return s[maxstar:maxstar+maxlength]1143. 最长公共子序列
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
l1 ,l2 = len(text1), len(text2)
dp = [None]*(l1+1)
for i in range(l1+1): dp[i] = [0]*(l2+1)
for i in range(1,l1+1):
for j in range(1,l2+1):
c1 ,c2 = text1[i-1],text2[j-1]
if c1 == c2 :
dp[i][j] = dp[i-1][j-1]+1
else :
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
return dp[l1][l2] 72. 编辑距离
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
l1 ,l2 = len(word1), len(word2)
dp = [None]*(l1+1)
for i in range(l1+1):
dp[i] = [0]*(l2+1)
dp[i][0] = i
for j in range(l2+1):
dp[0][j] = j
''' x r o s
null 0 1 2 3
h 1 1 2 3
o 2 2 1
r 3
s 4
e 5
'''
for i in range(1,l1+1):
for j in range(1,l2+1):
c1 ,c2 = word1[i-1],word2[j-1]
if c1 == c2 :
dp[i][j] = dp[i-1][j-1]
else :
dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1
return dp[l1][l2] 136. 只出现一次的数字
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for num in nums:
ans ^= num
return ans169. 多数元素
class Solution:
def majorityElement(self, nums: List[int]) -> int:
n = len(nums)
mp = {}
for num in nums :
mp[num] = mp.get(num,0) + 1
if mp[num] > n/2 :
return num
return -1
# 投票法 每次票数为0时 将当前的数作为候选人
# 票数为1 继续投票 如果遇到相同的数
# 票数加1 否则减1 最后剩下的数就是众数75. 颜色分类
31. 下一个排列
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
index = n-2
while index >= 0 and nums[index] >= nums[index+1] :
index -= 1
if index == -1 :
nums.reverse()
return
exchange_index = n - 1
while nums[exchange_index] <= nums[index]:
exchange_index -= 1
nums[index] ,nums[exchange_index] = nums[exchange_index] ,nums[index]
p , q = index+1 ,n-1
while p<q :
nums[p] , nums[q] = nums[q],nums[p]
p+=1
q-=1287. 寻找重复数
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
for index in range(len(nums)):
while index+1 != nums[index] :
target_index = nums[index]-1
if nums[target_index] != target_index+1 :
nums[index] ,nums[target_index]= nums[target_index] , nums[index]
else :
return nums[index]
return -1记录方式
- 将道题结果
.py文件存入hoot100笔记统计目录下，扫描全部py文件自动添加显示 - 代码都是 leetcode 过了提交测试的，但是思路并不一定是最佳思路，仅为自己过程记录
- 如果你发现了某个代码有问题，可以在背地里偷偷笑我，因为我的博客里没有添加评论功能