您现在的位置是：首页 >学无止境 >Leetcode Hot 200 上网站首页学无止境
Leetcode Hot 200 上
简介Leetcode Hot 200 上
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
res = 0
visited = list()
# 先左移后右移窗口
for i in range(len(s)):
# 左移窗口
while s[i] in visited: visited.pop(0)
# 右移窗口
visited.append(s[i])
res = max(res, len(visited))
return res# 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: ListNode) -> ListNode:
pre, cur = None, head
while cur:
# 存储当前链表的下一个节点为临时变量
tmp = cur.next
# 当前链表的下一个指向前一个链表
cur.next = pre
# pre, cur整体往后移动一个位置
pre, cur = cur, tmp
return prefrom collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
# OrderedDict的key会按照插入的顺序排列，不是key本身排序
self.capacity = capacity
self.dict = OrderedDict()
def get(self, key: int) -> int:
# 说明在字典中,重新移动字典的尾部
if key in self.dict:
self.dict.move_to_end(key)
return self.dict.get(key, -1)
def put(self, key: int, value: int) -> None:
# 如果存在,删掉,重新赋值
if key in self.dict:
del self.dict[key]
# 在字典尾部添加
self.dict[key] = value
if len(self.dict) > self.capacity:
# 弹出字典的头部(因为存储空间不够了)
# OrderedDict.popitem()有一个可选参数last（默认为True），当last为True时它从OrderedDict中删除最后一个键值对并返回该键值对，当last为False时它从OrderedDict中删除第一个键值对并返回该键值对
self.dict.popitem(last=False)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def quick_sort(a, l, r, k):
if l >= r: return a[l]
i = l - 1; j = r + 1
x = a[l + r >> 1]
while i < j:
i += 1
while a[i] < x: i += 1
j -= 1
while a[j] > x: j -= 1
if i < j: a[i], a[j] = a[j], a[i]
s1 = j - l + 1
if k <= s1: return quick_sort(a, l, j, k)
else: return quick_sort(a, j + 1, r, k - s1)
return quick_sort(nums, 0, len(nums) - 1, len(nums) - k + 1)
# 第k个数是正序，本题是逆序# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
# 判断是否有k个节点
def cal_len(head):
p = head
cnt = 0
while p:
cnt += 1
p = p.next
if cnt >= k: return True
return False
# 翻转k个节点
def reverseK(head, k):
pre, cur = None, head
while k:
tmp = cur.next
cur.next = pre
pre, cur = cur, tmp
k -= 1
return pre, cur
# 递归
def dfs(head, k):
if not cal_len(head): return head
pre, cur = reverseK(head, k)
head.next = dfs(cur, k)
return pre
return dfs(head, k)class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
nums.sort()
for i in range(n):
l = i + 1; r = n - 1
# 减枝，可省略
if nums[i] > 0: break
# nums[i] 去重，一定使用 i - 1
if i > 0 and nums[i] == nums[i-1]: continue
while l < r:
sums = nums[i] + nums[l] + nums[r]
if sums < 0: l += 1
elif sums > 0: r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
# nums[l] nums[r] 去重
while l < r and nums[l] == nums[l+1]: l += 1
while l < r and nums[r] == nums[r-1]: r -= 1
# 最后再多走一步
l += 1; r -= 1
return resclass Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
# dp 以下标 i 结尾的最大和的连续子数组
for i in range(1, n):
if dp[i-1] > 0:
dp[i] = dp[i-1] + nums[i]
else:
dp[i] = nums[i]
return max(dp)# python
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def quick_sort(a, l, r):
if l >= r: return a
i = l - 1; j = r + 1; x = a[l + r >> 1]
while i < j:
i += 1
while a[i] < x: i += 1
j -= 1
while a[j] > x: j -= 1
if i < j: a[i], a[j] = a[j], a[i]
quick_sort(a, l, j); quick_sort(a, j+1, r)
return a
return quick_sort(nums, 0, len(nums)-1)
# python 模拟 c++ do while 循环
# while True: do() if fail_condition: break
# do(); while condtion: do()# 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]:
head = cur = ListNode(0)
while list1 and list2:
if list1.val <= list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
# 合并后 list1 和 list2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
cur.next = list1 if list1 else list2
return head.nextclass Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 遍历列表同时查字典
map = dict()
for i, n in enumerate(nums):
m = target - n
if m in map:
return [map[m], i]
else:
map[n] = i # 这句不能放在if语句之前，解决list中有重复值或target-num=num的情况
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res = []
q = [root]
while q:
tmp = []
for i in range(len(q)):
node = q.pop(0)
tmp.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
res.append(tmp)
return resclass Solution:
def palindrome(self, s: str, left: int, right: int) -> str:
while(left>=0 and right<len(s) and s[left]==s[right]):
left-=1
right+=1
return s[left+1:right]
def longestPalindrome(self, s: str) -> str:
res=""
for i in range(len(s)):
#奇数回文子串
s1 = self.palindrome(s,i,i)
#偶数回文子串
s2 = self.palindrome(s,i,i+1)
res = res if len(res)>len(s1) else s1
res = res if len(res)>len(s2) else s2
return resclass Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums: return -1
l = 0; r = len(nums) - 1
# 无重复数，在有序区间查找
while l <= r:
m = l + r >> 1
if nums[m] == target: return m # 因为存在找不到的情况，故在此return
# 可以用nums[l]和nums[m]判断有序，也可以用nums[m]和nums[r]判断有序
elif nums[l] <= nums[m]: # 左半部分是有序
# target落在左半部分有序区域内，去掉m
if nums[l] <= target < nums[m]:
r = m - 1
else:
l = m + 1
else: # 右半部分是有序
# target落在右半部分有序区域内，去掉m
if nums[m] < target <= nums[r]:
l = m + 1
else:
r = m - 1
return -1
# 2.1
# 时间复杂度：O(logn)
# 空间复杂度：O(1)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
minprice = float('inf')
maxprofit = 0
# 一次遍历
for price in prices:
minprice = min(minprice, price)
maxprofit = max(maxprofit, price-minprice)
return maxprofitclass Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1: return False
dict = {'(':')','[':']','{':'}'}
stack = list()
# stack中存左括号。 如果是左括号， 加入栈中； 如果是右括号， 判断栈顶元素的键的值是否等于当前元素; 栈 stack 为空： 此时 stack.pop() 操作会报错
for c in s:
if c in dict: stack.append(c)
elif not stack or dict[stack.pop()] != c: return False
return not stack# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: return True
return Falseclass Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
res = []
p1 = p2 = 0
while p1 < m or p2 < n:
if p1 == m:
res.append(nums2[p2])
p2 += 1
elif p2 == n:
res.append(nums1[p1])
p1 += 1
elif nums1[p1] <= nums2[p2]:
res.append(nums1[p1])
p1 += 1
else:
res.append(nums2[p2])
p2 += 1
nums1[:] = res
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res = []
q = [root]
cnt = 0
while q:
tmp = []
for i in range(len(q)):
node = q.pop(0)
tmp.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
if cnt%2 == 0: res.append(tmp)
else: res.append(tmp[::-1])
cnt += 1
return resclass Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(grid, i, j):
if not (0 <= i < len(grid) and 0 <= j < len(grid[0])): return
if grid[i][j] != '1': return
grid[i][j] = '2'; # 将格子标记为「已遍历过」
dfs(grid, i - 1, j)
dfs(grid, i + 1, j)
dfs(grid, i, j - 1)
dfs(grid, i, j + 1)
res = 0
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(grid, i, j)
res += 1
return res# 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 or root.val == p.val or root.val == q.val: return root
l = self.lowestCommonAncestor(root.left, p, q)
r = self.lowestCommonAncestor(root.right, p, q)
if not l: return r
if not r: return l
return rootclass Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
# 数字不重复
res = []
def backtrack(nums, path):
if len(path) == len(nums):
res.append(path[:])
return
for num in nums:
if num in path: continue
path.append(num)
backtrack(nums, path)
path.pop()
backtrack(nums, [])
return resclass Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix: return []
m = len(matrix); n = len(matrix[0])
l, r, t, b = 0, n - 1, 0, m - 1
res = []
num, tar = 1, m * n
while num <= tar:
for i in range(l, r + 1): # left to right
if num <= tar:
res.append(matrix[t][i])
num += 1
t += 1
for i in range(t, b + 1): # top to bottom
if num <= tar:
res.append(matrix[i][r])
num += 1
r -= 1
for i in range(r, l - 1, -1): # right to left
if num <= tar:
res.append(matrix[b][i])
num += 1
b -= 1
for i in range(b, t - 1, -1): # bottom to top
if num <= tar:
res.append(matrix[i][l])
num += 1
l += 1
return res# 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) -> ListNode:
p = headA; q = headB
while p != q:
p = p.next if p else headB
q = q.next if q else headA
return p# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
p = dummpy = ListNode(next=head)
for _ in range(left-1):
p = p.next
cur = p.next
pre = None
for _ in range(right-left+1):
tmp = cur.next
cur.next = pre
pre, cur = cur, tmp
p.next.next = cur
p.next = pre
return dummpy.next# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
h = cur = ListNode(-1)
for i, l in enumerate(lists):
if l: heapq.heappush(heap, (l.val, i))
while heap:
v, i = heapq.heappop(heap)
cur.next = lists[i]
cur = cur.next
lists[i] = lists[i].next
if lists[i]: heapq.heappush(heap, (lists[i].val, i))
return h.next
# 时间复杂度nlogkclass Solution:
def addStrings(self, num1: str, num2: str) -> str:
i, j = len(num1)-1, len(num2)-1
res = ''
carry = 0
while i >= 0 or j >= 0:
n1 = int(num1[i]) if i >= 0 else 0
n2 = int(num2[j]) if j >= 0 else 0
tmp = n1 + n2 + carry
carry = tmp // 10
res = str(tmp % 10) + res
i -= 1; j -= 1
return '1' + res if carry else res
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
d = [nums[0]]
for i in range(1, len(nums)):
if nums[i] > d[-1]:
d.append(nums[i])
else:
l = 0; r = len(d) - 1
index = r
while l <= r:
m = l + r >> 1
if d[m] >= nums[i]:
index = m
r = m - 1
else:
l = m + 1
d[index] = nums[i]
return len(d)
# 贪心 + 二分查找
# 贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小
# 基于上面的贪心思路，我们维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值
# 1) 如果 nums[i]>d[len] ，则直接加入到 d 数组末尾，并更新 len=len+1；
# 2) 否则，在 d 数组中二分查找，找到第一个比 nums[i] 小的数 d[k] ，并更新 d[k+1]=nums[i]。
# 时间复杂度：O(nlogn)。数组 nums 的长度为 n，
# 空间复杂度：O(n)，需要额外使用长度为 n 的 d 数组。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow, fast = head, head
while True:
if not fast or not fast.next: return None
# # 先走一步再判断，要不然刚开始就退出了
slow = slow.next
fast = fast.next.next
if slow == fast: break
slow = head
while slow != fast:
fast = fast.next
slow = slow.next
return slowclass Solution:
def trap(self, height: List[int]) -> int:
# max min
res = 0
left = 0; right = len(height) - 1
# leftMax[i] 表示下标 i 及其左边的位置中 height 的最大高度，rightMax[i] 表示下标 i 及其右边的位置中 height 的最大高度。积水量由两边 height 的最大高度的的较小值和当前高度值决定。当使用双指针时，左指针移动时，假设右边有一个无穷大的柱子，右指针移动时，假设左边有一个无穷大的柱子。
leftmax = rightmax = 0
while left < right:
leftmax = max(leftmax, height[left])
rightmax = max(rightmax, height[right])
# 若 height[left] < height[right]， 则 leftmax < rightmax
# 接的雨水由小边决定
if height[left] < height[right]:
res += leftmax - height[left]
left += 1
else:
res += rightmax - height[right]
right -= 1
return res
# 时间复杂度：O(n)
# 空间复杂度：O(1)# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: ListNode) -> ListNode:
slow = head; fast = head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
#截断
mid, slow.next = slow.next, None
return mid
def reverseList(self, head: ListNode) -> ListNode:
pre, cur = None, head
while cur:
# 存储当前链表的下一个节点为临时变量
tmp = cur.next
# 当前链表的下一个指向前一个链表
cur.next = pre
# pre, cur整体往后移动一个位置
pre, cur = cur, tmp
return pre
def merge(self, l1: ListNode, l2: ListNode):
h = cur = ListNode()
while l1 and l2:
cur.next = l1
l1 = l1.next
cur = cur.next
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return h.next
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head: return
l = head
r = self.partition(head)
r = self.reverseList(r)
self.merge(l, r)# 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
# 首先，考虑实现一个简化的函数 dfs(root)，该函数计算二叉树中的一个节点的最大贡献值，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和大。这里必须经过该节点root。
class Solution:
def __init__(self):
self.res = float("-inf")
def maxPathSum(self, root: TreeNode) -> int:
def dfs(root):
if not root: return 0
# 递归计算左右子节点的最大贡献值
# 只有在最大贡献值大于 0 时，才会选取对应子节点
left = max(dfs(root.left), 0)
right = max(dfs(root.right), 0)
# 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
self.res = max(self.res, root.val + left + right)
# 返回节点的最大贡献值
return root.val + max(left, right)
dfs(root)
return self.res
# 时间复杂度：O(n)
# 空间复杂度：O(n)# 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]:
def dfs(root: TreeNode):
if root is None: return
dfs(root.left)
res.append(root.val)
dfs(root.right)
res = []
dfs(root)
return resclass MyQueue:
def __init__(self):
self.s1 = []
self.s2 = []
def push(self, x: int) -> None:
self.s1.append(x)
def pop(self) -> int:
if not self.s2:
while self.s1: self.s2.append(self.s1.pop())
return self.s2.pop()
def peek(self) -> int:
if not self.s2:
while self.s1: self.s2.append(self.s1.pop())
return self.s2[-1]
def empty(self) -> bool:
return not self.s1 and not self.s2
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()# 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: ListNode, n: int) -> ListNode:
h = ListNode(0, head)
slow = h; fast = head
for i in range(n):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return h.nextclass Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1); n = len(word2)
dp = [ [0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
# pass
dp[i][j] = dp[i-1][j-1]
else: #增删改的最小值
dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 1)
return dp[m][n]class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0; r = len(nums) - 1
while l <= r:
m = (l + r) // 2
if nums[m] == target: return m
elif nums[m] < target: l = m + 1
else: r = m - 1
return -1class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def getK(k):
i = 0; j = 0
while True:
if i == m: return nums2[j + k - 1]
if j == n: return nums1[i + k - 1]
if k == 1: return min(nums1[i], nums2[j])
n_i = min(i + k // 2 - 1, m - 1)
n_j = min(j + k // 2 - 1, n - 1)
if nums1[n_i] <= nums2[n_j]:
k -= n_i - i + 1
i = n_i + 1
else:
k -= n_j - j + 1
j = n_j + 1
m = len(nums1); n = len(nums2)
size = m + n
if size % 2 == 1:
return getK((size + 1) // 2)
else:
return (getK(size // 2) + getK(size // 2 + 1)) / 2
# 转换为求第k大的元素
# 通过比较A[k/2]与B[k/2]，每次舍弃较小数组的一半。
# 二分+递归
# 时间复杂度：O(log(m+n))
# 空间复杂度：O(1)# 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 []
res = []; q = [root]
while q:
t = []
for i in range(len(q)):
n = q.pop(0)
t.append(n.val)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
res.append(t[-1])
return resclass Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# 按照 intervals 中每一项的第0个元素排序
# intervals.sort(key=lambda x: x[0])
intervals.sort()
res = []
for interval in intervals:
# 如果列表为空，或者当前区间与上一区间不重合，直接添加
if not res or res[-1][1] < interval[0]:
res.append(interval)
else:
# 否则的话，我们就可以与上一区间进行合并
res[-1][1] = max(res[-1][1], interval[1])
return res
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# dp[i][j] 表示 text1[0:i]， text2[0:j] 的最长公共子序列的长度
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
# 不连续# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummpy = ListNode(-1)
dummpy.next = head
p = dummpy
while p.next:
q = p.next.next
while q and q.val == p.next.val: q = q.next
if p.next.next == q: p = p.next
else: p.next = q
return dummpy.nextclass Solution:
def climbStairs(self, n: int) -> int:
p = 0; q = 1
for i in range(n):
p, q = q, p+q
return q# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
# 获取中间节点并截断
def mid(self, head: ListNode) -> ListNode:
slow = head; fast = head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
mid, slow.next = slow.next, None
return mid
def merge(self, l: Optional[ListNode], r: Optional[ListNode]) -> Optional[ListNode]:
cur = head = ListNode()
while l and r:
if l.val <= r.val:
cur.next = l
l = l.next
else:
cur.next = r
r = r.next
cur = cur.next
# 合并后 l 和 r 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
cur.next = l if l else r
return head.next
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next: return head
left = head; right = self.mid(head)
l = self.sortList(left)
r = self.sortList(right)
return self.merge(l, r)class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
i = n - 2
while i >= 0 and nums[i] >= nums[i+1]: i -= 1
j = n - 1
while i >= 0 and j >= 0 and nums[i] >= nums[j]: j -= 1
nums[i], nums[j] = nums[j], nums[i]
nums[i+1:] = nums[i+1:][::-1]
# l = i + 1; r = n - 1
# while l < r:
# nums[l], nums[r] = nums[r], nums[l]
# l += 1; r -= 1
"""
算法推导：
1. 我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。
2. 我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：
2.1 在尽可能靠右的低位进行交换，需要从后向前查找
2.2 将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换，因为数组降序，需要从后向前查找
2.3 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列
以上就是求“下一个排列”的分析过程。
算法过程：
1. 首先从后向前查找第一个顺序对 (i,i+1)(i,i+1)，满足 a[i] < a[i+1]a[i]<a[i+1]。这样「较小数」即为 a[i]a[i]。此时 [i+1,n)[i+1,n) 必然是下降序列。
2. 如果找到了顺序对，那么在区间 [i+1,n)[i+1,n) 中从后向前查找第一个元素 jj 满足 a[i] < a[j]a[i]<a[j]。这样「较大数」即为 a[j]a[j]。
3. 交换 a[i]a[i] 与 a[j]a[j]，此时可以证明区间 [i+1,n)[i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,n)[i+1,n) 使其变为升序，而无需对该区间进行排序。
"""class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
n = len(s)
if n < 4 or 12 < n:
return []
res = []
path = []
def backtrace(idx: int) -> None:
if len(path) == 4:
if idx == n:
res.append('.'.join(path))
return
if idx == n:
return
if s[idx] == '0':
path.append('0')
backtrace(idx + 1)
path.pop()
else:
for i in range(idx, n):
num = int(s[idx: i + 1])
if 0 <= num <= 255:
path.append(str(num))
backtrace(i + 1)
path.pop()
else:
break
backtrace(0)
return res# 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]:
dummpy = cur = ListNode()
carry = 0
while l1 or l2 or carry != 0:
n1 = l1.val if l1 else 0
n2 = l2.val if l2 else 0
n = n1 + n2 + carry
carry = n // 10
cur.next = ListNode(n % 10)
if l1: l1 = l1.next
if l2: l2 = l2.next
cur = cur.next
return dummpy.nextclass Solution:
def mySqrt(self, x: int) -> int:
# 由于 x 平方根的整数部分是满足 k^2≤x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。
l = 0; r = x
res = -1
while l <= r:
m = (l + r) // 2
if m * m <= x:
res = m
l = m + 1
else:
r = m - 1
return resimport re
class Solution:
def myAtoi(self, str: str) -> int:
INT_MAX = 2147483647
INT_MIN = -2147483648
str = str.lstrip() #清除左边多余的空格
num_re = re.compile(r'^[+-]?d+') #设置正则规则
num = num_re.findall(str) #查找匹配的内容
# list变量前加一个星号*，目的是将该list变量拆解开多个独立的参数
# dict变量前面加一个星号*，目的是将dict变量中的key值拆解开成多个独立的元素
num = int(*num) #由于返回的是个列表，解包并且转换成整数
return max(min(num,INT_MAX),INT_MIN) #返回值class Solution:
@lru_cache(None)
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return ['']
ans = []
for c in range(n):
for left in self.generateParenthesis(c):
for right in self.generateParenthesis(n-1-c):
ans.append('({}){}'.format(left, right))
return ansfrom collections import Counter
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
c = Counter(nums)
for num in range(1, len(nums)+2):
if c[num] == 0:
return numclass Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
q = [(-nums[i], i) for i in range(k)]
heapq.heapify(q)
res = [-q[0][0]]
for i in range(k, n):
heapq.heappush(q, (-nums[i], i))
while q[0][1] <= i - k: heapq.heappop(q)
res.append(-q[0][0])
return res# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
p = q = head
while k:
q = q.next
k -= 1
while q:
p = p.next
q = q.next
return pfrom collections import defaultdict
class Solution:
def minWindow(self, s: str, t: str) -> str:
res = ''
hw = defaultdict(int); ht = defaultdict(int)
for c in t: ht[c] += 1
j = 0; cnt = 0
for i in range(len(s)):
hw[s[i]] += 1
if hw[s[i]] <= ht[s[i]]: cnt += 1
while j <= i and hw[s[j]] > ht[s[j]]:
hw[s[j]] -= 1
j += 1
if cnt == len(t):
if not res or len(res) > i - j + 1:
res = s[j: i+1]
return resclass Solution:
def compareVersion(self, version1: str, version2: str) -> int:
for v1, v2 in zip_longest(version1.split('.'), version2.split('.'), fillvalue=0):
x, y = int(v1), int(v2)
if x != y:
return 1 if x > y else -1
return 0
# 时间复杂度：O(n+m)
# 空间复杂度：O(n+m)class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
ans = "0"
m, n = len(num1), len(num2)
for i in range(n - 1, -1, -1):
add = 0
y = int(num2[i])
curr = ["0"] * (n - i - 1)
for j in range(m - 1, -1, -1):
product = int(num1[j]) * y + add
curr.append(str(product % 10))
add = product // 10
if add > 0:
curr.append(str(add))
curr = "".join(curr[::-1])
ans = self.addStrings(ans, curr)
return ans
def addStrings(self, num1: str, num2: str) -> str:
i, j = len(num1) - 1, len(num2) - 1
add = 0
ans = list()
while i >= 0 or j >= 0 or add != 0:
x = int(num1[i]) if i >= 0 else 0
y = int(num2[j]) if j >= 0 else 0
result = x + y + add
ans.append(str(result % 10))
add = result // 10
i -= 1
j -= 1
return "".join(ans[::-1])
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s: return 0
res = 0
# stack一边匹配消消乐， 一边入栈
# 这一步可以防止stack中匹配完为空时pop()报错
stack = [-1]
for i in range(len(s)):
if s[i] == "(":
stack.append(i)
else:
# 如果是右括号则出栈
stack.pop()
# 如果栈是空的话, 把右括号放进来
if not stack: stack.append(i)
# 当前全部数减去剩余无法配对的数（单身）即res
else: res = max(res, i - stack[-1])
return res# 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]) -> TreeNode:
if not preorder: return None
root = TreeNode(preorder[0])
cur = inorder.index(root.val)
#跳过根节点
root.left = self.buildTree(preorder[1:cur+1], inorder[0:cur])
root.right = self.buildTree(preorder[cur+1:], inorder[cur+1:])
return rootclass Solution:
def reverseWords(self, s: str) -> str:
return " ".join(s.split()[::-1])class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1 # 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(root: TreeNode):
if root is None: return
res.append(root.val)
dfs(root.left)
dfs(root.right)
res = []
dfs(root)
return res# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(root: TreeNode):
if root is None: return
res.append(root.val)
dfs(root.left)
dfs(root.right)
res = []
dfs(root)
return resclass 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]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()# 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: TreeNode) -> int:
if not root: return 0
l = self.maxDepth(root.left)
r = self.maxDepth(root.right)
return (max(l,r)+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 maxDepth(self, root: TreeNode) -> bool:
if not root: return 0
l = self.maxDepth(root.left)
r = self.maxDepth(root.right)
return (max(l,r)+1)
def isBalanced(self, root: TreeNode) -> bool:
if not root: return True
return abs(self.maxDepth(root.left)-self.maxDepth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:
def dfs(root: Optional[TreeNode], preRes) -> int:
if not root: return 0
res = 10 * preRes + root.val
if not root.left and not root.right:
return res
else:
return dfs(root.left, res) + dfs(root.right, res)
return dfs(root, 0)# 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 isMirror(self, m: TreeNode, n: TreeNode) -> bool:
if not m and not n: return True
if m and n and m.val == n.val:
return self.isMirror(m.left,n.right) and self.isMirror(m.right,n.left)
return False
def isSymmetric(self, root: TreeNode) -> bool:
return self.isMirror(root,root)# 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: TreeNode) -> int:
self.res=0
def maxDepth(root: TreeNode) -> int:
if not root: return 0
l = maxDepth(root.left)
r = maxDepth(root.right)
# 将每个节点最大直径(左子树深度+右子树深度)当前最大值比较并取大者
self.res = max(self.res, l+r)
# 返回节点深度
return (max(l,r)+1)
maxDepth(root)
return self.res# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7
class Solution:
def rand10(self):
while True:
res = (rand7()-1)*7 + rand7()#构造1~49的均匀分布
if res <= 40:#剔除大于40的值，1-40等概率出现。
break
return res%10+1#构造1-10的均匀分布# 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: TreeNode, targetSum: int) -> List[List[int]]:
res = list(); path = list()
def dfs(root: TreeNode, targetSum: int):
if not root: return
path.append(root.val)
targetSum -= root.val
if not root.left and not root.right and targetSum == 0:
res.append(path[:])
dfs(root.left, targetSum)
dfs(root.right, targetSum)
path.pop()
dfs(root, targetSum)
return res# 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:
pre = -inf
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if not root: return True
if not self.isValidBST(root.left) or root.val <= self.pre:
return False
self.pre = root.val
return self.isValidBST(root.right)
# 中序遍历
# 时间复杂度：O(n)
# 空间复杂度：O(n)class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
row = len(grid); col = len(grid[0])
# 不要用 dp = [[0] * col] * row
# 要用 dp = [[0 for _ in range(col)] for _ in range(row)]
dp = [[0] * col for _ in range(row)]
dp[0][0] = grid[0][0]
for i in range(1, row):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, col):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, row):
for j in range(1, col):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# zip(*matrix) 旋转矩阵
matrix[:] = zip(*matrix[::-1])# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root: return False
if not root.left and not root.right: return root.val == targetSum
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)from typing import List
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates, begin, size, path, res, target):
if target < 0:
return
if target == 0:
res.append(path)
return
for index in range(begin, size):
dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])
size = len(candidates)
if size == 0:
return []
path = []
res = []
dfs(candidates, 0, size, path, res, target)
return res# 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: ListNode) -> bool:
vals = []
cur = head
while cur:
vals.append(cur.val)
cur = cur.next
return vals == vals[::-1]class Solution:
def majorityElement(self, nums: List[int]) -> int:
c = collections.Counter(nums)
return max(c.keys(), key=c.get)class Solution:
def decodeString(self, s: str) -> str:
stack, res, multi = [], "", 0
for c in s:
if c == '[':
stack.append([multi, res])
res, multi = "", 0
elif c == ']':
cur_multi, cur_res = stack.pop()
res = cur_res + cur_multi * res
elif '0' <= c <= '9':
multi = multi * 10 + int(c)
else:
res += c
return res
'''
if 数字， then 将数字转换为整数，用于后续倍数计算
if 字符， 延长当前字符串
if 左括号，当前状态压入栈
if 右括号，弹出状态，组合字符串
'''class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if len(matrix) == 0 or len(matrix[0]) == 0:
return 0
maxSide = 0
rows, columns = len(matrix), len(matrix[0])
# dp(i,j) 表示以(i,j) 为右下角，且只包含 1 的正方形的边长最大值
dp = [[0] * columns for _ in range(rows)]
for i in range(rows):
for j in range(columns):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
maxSide = max(maxSide, dp[i][j])
maxSquare = maxSide * maxSide
return maxSquareclass Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
# 计算从num1数组的start1位置开始，从num2数组的start2位置开始，长度最长的子数组的长度 。
def maxSize(start1, start2, size):
res = 0; cnt = 0
for k in range(size):
if nums1[start1+k] == nums2[start2+k]:
cnt += 1
res = max(res, cnt)
else:
cnt = 0
return res
res = 0
m = len(nums1); n = len(nums2)
# nums1不动，num2滑动
for i in range(m):
size = min(m-i, n)
res = max(res, maxSize(i, 0, size))
# nums1滑动，num2不动
for j in range(n):
size = min(m, n-j)
res = max(res, maxSize(0, j, size))
return res
# 滑动窗口
# 我们可以枚举 A 和 B 所有的对齐方式。对齐的方式有两类：第一类为 A 不变，B 的首元素与 A 中的某个元素对齐；第二类为 B 不变，A 的首元素与 B 中的某个元素对齐。对于每一种对齐方式，我们计算它们相对位置相同的重复子数组即可。
# 时间复杂度： O((N+M)×min(N,M))
# 空间复杂度： O(1)class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix); n = len(matrix[0])
i = 0; j = n - 1
while i <m and j >= 0:
if matrix[i][j] == target:
return True
elif matrix[i][j] < target:
i += 1
else:
j -= 1
return False# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
# 递归函数的终止条件，节点为空时返回
if not root: return None
# 将当前节点的左右子树交换
root.left, root.right = root.right, root.left
# 递归交换当前节点的 左子树和右子树
self.mirrorTree(root.left)
self.mirrorTree(root.right)
# 函数返回时就表示当前这个节点，以及它的左右子树
# 都已经交换完了
return rootclass Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def bl(nums, target):
l = 0; r = len(nums)
while l < r:
m = l + r >> 1
if nums[m] == target:
r = m
self.f = 1
elif nums[m] > target:
r = m
else:
l = m + 1
return l
def br(nums, target):
l = 0; r = len(nums)
while l < r:
m = l + r >> 1
if nums[m] == target:
l = m + 1
self.f = 1
elif nums[m] > target:
r = m
else:
l = m + 1
return l - 1
self.f = 0
l = bl(nums, target)
r = br(nums, target)
return [l, r] if self.f == 1 else [-1, -1]class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res = ""
for ss in zip(*strs):
s = set(ss)
if len(s) == 1: res += ss[0]
else: break
return resclass Solution:
def findPeakElement(self, nums: List[int]) -> int:
l = 0; r = len(nums) - 1
while l < r:
m = l + r >> 1
if nums[m] < nums[m+1]:
l = m + 1
else:
r = m
return lclass Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 第一行，第一列初始化为 1
dp = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
res = 0
num_set = set(nums)
for num in num_set:
if num-1 not in num_set:
cur = num
tmp = 1
while cur+1 in num_set:
cur += 1
tmp += 1
res = max(res, tmp)
return resclass Solution:
def calculate(self, s: str) -> int:
n = len(s)
stack = []
preSign = '+'
num = 0
for i in range(n):
if s[i] != ' ' and s[i].isdigit():
num = num * 10 + ord(s[i]) - ord('0')
if i == n - 1 or s[i] in '+-*/':
if preSign == '+':
stack.append(num)
elif preSign == '-':
stack.append(-num)
elif preSign == '*':
stack.append(stack.pop() * num)
else:
stack.append(int(stack.pop() / num))
preSign = s[i]
num = 0
return sum(stack)# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head: return head
p = head
while p.next:
if p.val == p.next.val: p.next = p.next.next
else: p = p.next
return head
# 时间复杂度分析：整个链表只扫描一遍，所以时间复杂度是 O(n)class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
def dfs(i ,j):
if not (0 <= i < m and 0 <= j < n): return 0
if grid[i][j] != 1: return 0
grid[i][j] = 0
return 1 + dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)
res = 0
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1: res = max(res, dfs(i, j))
return resclass Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
if n == 0: return 0
if n == 1: return nums[0]
if n == 2: return max(nums[0], nums[1])
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
return dp[n-1]class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
res = 1
# 注意这里是二维数组，[节点， 节点下标]
q = [[root, 1]]
while q:
tmp = []
for node, index in q:
if node.left:
tmp.append([node.left, index * 2])
if node.right:
tmp.append([node.right, index * 2 + 1])
res = max(res, q[-1][1] - q[0][1] + 1)
q = tmp
return res
# BFS
# 时间复杂度：O(n)
# 空间复杂度：O(n)class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
# 一次遍历
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profitclass Solution:
def heapify(self, nums, i, n):
while 2 * i + 1 < n:
l = 2 * i + 1; r = 2 * i + 2
if r >= n or nums[l] > nums[r]:
j = l
else:
j = r
if nums[i] < nums[j]:
nums[i], nums[j] = nums[j], nums[i]
i = j
else:
break
def buildHeap(self, nums):
for i in range(len(nums) - 1, -1, -1):
self.heapify(nums, i, len(nums))
def sortArray(self, nums: List[int]) -> List[int]:
self.buildHeap(nums)
for i in range(len(nums) - 1, -1, -1):
nums[i], nums[0] = nums[0], nums[i]
self.heapify(nums, 0, i)
return nums
"""
堆与排序：
对于一个待排序的包含 n 个元素的数组 nums，堆排序 通常包含以下几个基本步骤：
1. 建堆：将待排序的数组初始化为大根堆（小根堆）。此时，堆顶的元素（即根节点）即为整个数组中的最大值（最小值）。
2. 交换和调整：将堆顶元素与末尾元素进行交换，此时末尾即为最大值（最小值）。除去末尾元素后，将其他 n-1 个元素重新构造成一个大根堆（小根堆），如此便可得到原数组 n 个元素中的次大值（次小值）。
3. 重复步骤2，直至堆中仅剩一个元素，如此便可得到一个有序序列了。
通过以上步骤我们也可以发现：
对于「升序排列」数组，需用到大根堆；
对于「降序排列」数组，则需用到小根堆。
"""class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * (n+1)
dp[0] = True
# dp[i] 表示 s 的前 i 位是否可以用 wordDict 中的单词表示
for i in range(n):
for j in range(i+1, n+1):
if dp[i] and s[i:j] in wordDict:
dp[j] = True
return dp[-1]# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next: return head
a = head; b = head.next
b.next, a.next = a, self.swapPairs(b.next)
# b是新的头节点
return b
# 时间复杂度：O(n)
# 空间复杂度：O(n)
# 递归class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums: return
res = nums[0]
pre_max = nums[0]
pre_min = nums[0]
for num in nums[1:]:
cur_max = max(pre_max * num, pre_min * num, num)
cur_min = min(pre_max * num, pre_min * num, num)
res = max(res, cur_max)
pre_max = cur_max
pre_min = cur_min
return resclass Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
l = r = 0
while r < len(nums):
if nums[r] != 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r += 1class Solution:
def findMin(self, nums: List[int]) -> int:
l = 0; r = len(nums) - 1
while l < r:
m = l + r >> 1
if nums[m] > nums[r]:
l = m + 1
else:
r = m
return nums[l]class Solution:
def largestNumber(self, nums: List[int]) -> str:
# 第一步：定义比较函数，把最大的放左边
# 第二步：排序
# 第三步：返回结果
def compare(x, y): return int(y+x) - int(x+y)
nums = sorted(map(str, nums), key=cmp_to_key(compare))
return "0" if nums[0]=="0" else "".join(nums)# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
self.res = ''
def dfs_s(root):
if not root:
# 二叉树构建必须是前序+中序；前序+后序；中序+后续。如果只采用一种就必须使用占位符，这里的 None 是占位符号，也可以用 #
# 二叉搜索树可以使用一种遍历构建
self.res += 'None' + ','
return
else:
self.res += str(root.val) + ','
dfs_s(root.left)
dfs_s(root.right)
dfs_s(root)
return self.res
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if not data: return
s = data.split(',')
self.u = 0
def dfs_d():
if s[self.u] == 'None':
self.u += 1
return
else:
root = TreeNode(int(s[self.u]))
self.u += 1
root.left = dfs_d()
root.right = dfs_d()
return root
return dfs_d()
# 时间复杂度：在序列化和反序列化函数中，我们只访问每个节点一次，因此时间复杂度为 O(n)，其中 n 是节点数，即树的大小。
# 空间复杂度：在序列化和反序列化函数中，我们递归会使用栈空间，故渐进空间复杂度为 O(n)。
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效)