Leetcode Hot 200
3. 无重复字符的最长子串
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:res = 0visited = 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 res206. 反转链表
# 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, headwhile cur:# 存储当前链表的下一个节点为临时变量tmp = cur.next# 当前链表的下一个指向前一个链表cur.next = pre# pre, cur整体往后移动一个位置pre, cur = cur, tmpreturn pre146. LRU 缓存
from collections import OrderedDict
class LRUCache:def __init__(self, capacity: int):# OrderedDict的key会按照插入的顺序排列，不是key本身排序self.capacity = capacityself.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] = valueif 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)215. 数组中的第K个最大元素
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 + 1x = a[l + r >> 1]while i < j:i += 1while a[i] < x: i += 1j -= 1while a[j] > x: j -= 1if i < j: a[i], a[j] = a[j], a[i]s1 = j - l + 1if 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个数是正序，本题是逆序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 reverseKGroup(self, head: ListNode, k: int) -> ListNode:# 判断是否有k个节点def cal_len(head):p = headcnt = 0while p:cnt += 1p = p.nextif cnt >= k: return Truereturn False# 翻转k个节点def reverseK(head, k):pre, cur = None, headwhile k:tmp = cur.nextcur.next = prepre, cur = cur, tmpk -= 1return pre, cur# 递归def dfs(head, k):if not cal_len(head): return headpre, cur = reverseK(head, k)head.next = dfs(cur, k)return prereturn dfs(head, k)15. 三数之和
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 - 1if i > 0 and nums[i] == nums[i-1]: continuewhile l < r:sums = nums[i] + nums[l] + nums[r]if sums < 0: l += 1elif sums > 0: r -= 1else:res.append([nums[i], nums[l], nums[r]])# nums[l] nums[r] 去重while l < r and nums[l] == nums[l+1]: l += 1while l < r and nums[r] == nums[r-1]: r -= 1# 最后再多走一步l += 1; r -= 1return res53. 最大子数组和
class Solution:def maxSubArray(self, nums: List[int]) -> int:n = len(nums)dp = [0] * ndp[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)912. 排序数组
# python
class Solution:def sortArray(self, nums: List[int]) -> List[int]:def quick_sort(a, l, r):if l >= r: return ai = l - 1; j = r + 1; x = a[l + r >> 1]while i < j:i += 1while a[i] < x: i += 1j -= 1while a[j] > x: j -= 1if i < j: a[i], a[j] = a[j], a[i]quick_sort(a, l, j); quick_sort(a, j+1, r)return areturn quick_sort(nums, 0, len(nums)-1)# python 模拟 c++ do while 循环
# while True: do() if fail_condition: break
# do(); while condtion: do()21. 合并两个有序链表
# 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 = list1list1 = list1.nextelse:cur.next = list2list2 = list2.nextcur = cur.next# 合并后 list1 和 list2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可cur.next = list1 if list1 else list2return head.next1. 两数之和
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:# 遍历列表同时查字典map = dict()for i, n in enumerate(nums):m = target - nif m in map:return [map[m], i]else:map[n] = i # 这句不能放在if语句之前，解决list中有重复值或target-num=num的情况102. 二叉树的层序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass 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 res5. 最长回文子串
class Solution:def palindrome(self, s: str, left: int, right: int) -> str:while(left>=0 and right<len(s) and s[left]==s[right]):left-=1right+=1return 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 s1res = res if len(res)>len(s2) else s2return res33. 搜索旋转排序数组
class Solution:def search(self, nums: List[int], target: int) -> int:if not nums: return -1l = 0; r = len(nums) - 1# 无重复数，在有序区间查找while l <= r:m = l + r >> 1if nums[m] == target: return m # 因为存在找不到的情况，故在此return# 可以用nums[l]和nums[m]判断有序，也可以用nums[m]和nums[r]判断有序elif nums[l] <= nums[m]: # 左半部分是有序# target落在左半部分有序区域内，去掉mif nums[l] <= target < nums[m]:r = m - 1else:l = m + 1else: # 右半部分是有序# target落在右半部分有序区域内，去掉mif nums[m] < target <= nums[r]:l = m + 1else:r = m - 1return -1# 2.1
# 时间复杂度：O(logn)
# 空间复杂度：O(1)121. 买卖股票的最佳时机
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 maxprofit20. 有效的括号
class Solution:def isValid(self, s: str) -> bool:if len(s) % 2 == 1: return Falsedict = {'(':')','[':']','{':'}'}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 Falsereturn not stack141. 环形链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def hasCycle(self, head: ListNode) -> bool:slow, fast = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast: return Truereturn False88. 合并两个有序数组
class 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 = 0while p1 < m or p2 < n:if p1 == m:res.append(nums2[p2])p2 += 1elif p2 == n:res.append(nums1[p1])p1 += 1elif nums1[p1] <= nums2[p2]:res.append(nums1[p1])p1 += 1else:res.append(nums2[p2])p2 += 1nums1[:] = res103. 二叉树的锯齿形层序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:if not root: return []res = []q = [root]cnt = 0while 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 += 1return res200. 岛屿数量
class 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])): returnif grid[i][j] != '1': returngrid[i][j] = '2'; # 将格子标记为「已遍历过」 dfs(grid, i - 1, j)dfs(grid, i + 1, j)dfs(grid, i, j - 1)dfs(grid, i, j + 1)res = 0m, 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 += 1return res236. 二叉树的最近公共祖先
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass 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 rootl = self.lowestCommonAncestor(root.left, p, q)r = self.lowestCommonAncestor(root.right, p, q)if not l: return rif not r: return lreturn root46. 全排列
class Solution:def permute(self, nums: List[int]) -> List[List[int]]:# 数字不重复res = []def backtrack(nums, path):if len(path) == len(nums):res.append(path[:])returnfor num in nums:if num in path: continuepath.append(num)backtrack(nums, path)path.pop()backtrack(nums, [])return res54. 螺旋矩阵
class 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 - 1res = []num, tar = 1, m * nwhile num <= tar:for i in range(l, r + 1): # left to rightif num <= tar:res.append(matrix[t][i])num += 1t += 1for i in range(t, b + 1): # top to bottomif num <= tar:res.append(matrix[i][r])num += 1r -= 1for i in range(r, l - 1, -1): # right to leftif num <= tar:res.append(matrix[b][i])num += 1b -= 1for i in range(b, t - 1, -1): # bottom to topif num <= tar:res.append(matrix[i][l])num += 1l += 1return res160. 相交链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:p = headA; q = headBwhile p != q:p = p.next if p else headBq = q.next if q else headAreturn p92. 反转链表 II
# 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.nextcur = p.nextpre = Nonefor _ in range(right-left+1):tmp = cur.nextcur.next = prepre, cur = cur, tmpp.next.next = curp.next = prereturn dummpy.next23. 合并 K 个升序链表
# 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.nextlists[i] = lists[i].nextif lists[i]: heapq.heappush(heap, (lists[i].val, i))return h.next# 时间复杂度nlogk415. 字符串相加
class Solution:def addStrings(self, num1: str, num2: str) -> str:i, j = len(num1)-1, len(num2)-1res = ''carry = 0while i >= 0 or j >= 0:n1 = int(num1[i]) if i >= 0 else 0n2 = int(num2[j]) if j >= 0 else 0tmp = n1 + n2 + carrycarry = tmp // 10res = str(tmp % 10) + resi -= 1; j -= 1return '1' + res if carry else res
300. 最长递增子序列
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) - 1index = rwhile l <= r:m = l + r >> 1if d[m] >= nums[i]:index = mr = m - 1else:l = m + 1d[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 数组。142. 环形链表 II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def detectCycle(self, head: ListNode) -> ListNode:slow, fast = head, headwhile True:if not fast or not fast.next: return None# # 先走一步再判断，要不然刚开始就退出了slow = slow.nextfast = fast.next.nextif slow == fast: breakslow = headwhile slow != fast:fast = fast.nextslow = slow.nextreturn slow42. 接雨水
class Solution:def trap(self, height: List[int]) -> int:# max minres = 0left = 0; right = len(height) - 1# leftMax[i] 表示下标 i 及其左边的位置中 height 的最大高度，rightMax[i] 表示下标 i 及其右边的位置中 height 的最大高度。积水量由两边 height 的最大高度的的较小值和当前高度值决定。当使用双指针时，左指针移动时，假设右边有一个无穷大的柱子，右指针移动时，假设左边有一个无穷大的柱子。leftmax = rightmax = 0while 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 += 1else:res += rightmax - height[right]right -= 1return res# 时间复杂度：O(n)
# 空间复杂度：O(1)143. 重排链表
# 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.nextwhile fast and fast.next:slow, fast = slow.next, fast.next.next#截断mid, slow.next = slow.next, Nonereturn middef reverseList(self, head: ListNode) -> ListNode:pre, cur = None, headwhile cur:# 存储当前链表的下一个节点为临时变量tmp = cur.next# 当前链表的下一个指向前一个链表cur.next = pre# pre, cur整体往后移动一个位置pre, cur = cur, tmpreturn predef merge(self, l1: ListNode, l2: ListNode):h = cur = ListNode()while l1 and l2:cur.next = l1l1 = l1.nextcur = cur.nextcur.next = l2l2 = l2.nextcur = cur.nextcur.next = l1 if l1 else l2return h.nextdef reorderList(self, head: ListNode) -> None:"""Do not return anything, modify head in-place instead."""if not head: returnl = headr = self.partition(head) r = self.reverseList(r)self.merge(l, r)124. 二叉树中的最大路径和
# 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)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]:def dfs(root: TreeNode):if root is None: return dfs(root.left)res.append(root.val)dfs(root.right)res = []dfs(root)return res232. 用栈实现队列
class 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()19. 删除链表的倒数第 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: ListNode, n: int) -> ListNode:h = ListNode(0, head)slow = h; fast = headfor i in range(n):fast = fast.nextwhile fast:fast = fast.nextslow = slow.nextslow.next = slow.next.nextreturn h.next72. 编辑距离
class 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] = ifor j in range(n + 1):dp[0][j] = jfor i in range(1, m + 1):for j in range(1, n + 1):if word1[i-1] == word2[j-1]:# passdp[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]704. 二分查找
class Solution:def search(self, nums: List[int], target: int) -> int:l = 0; r = len(nums) - 1while l <= r:m = (l + r) // 2if nums[m] == target: return melif nums[m] < target: l = m + 1else: r = m - 1return -14. 寻找两个正序数组的中位数
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:def getK(k):i = 0; j = 0while 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 + 1i = n_i + 1else:k -= n_j - j + 1j = n_j + 1m = len(nums1); n = len(nums2)size = m + nif 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)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 []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 res56. 合并区间
class 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
1143. 最长公共子序列
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] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]
# 不连续82. 删除排序链表中的重复元素 II
# 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 = headp = dummpywhile p.next:q = p.next.nextwhile q and q.val == p.next.val: q = q.nextif p.next.next == q: p = p.nextelse: p.next = qreturn dummpy.next70. 爬楼梯
class Solution:def climbStairs(self, n: int) -> int:p = 0; q = 1for i in range(n):p, q = q, p+qreturn q148. 排序链表
# 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.nextwhile fast and fast.next:slow, fast = slow.next, fast.next.nextmid, slow.next = slow.next, Nonereturn middef merge(self, l: Optional[ListNode], r: Optional[ListNode]) -> Optional[ListNode]:cur = head = ListNode()while l and r:if l.val <= r.val:cur.next = ll = l.nextelse:cur.next = rr = r.nextcur = cur.next# 合并后 l 和 r 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可cur.next = l if l else rreturn head.nextdef sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head or not head.next: return headleft = head; right = self.mid(head)l = self.sortList(left)r = self.sortList(right)return self.merge(l, r)31. 下一个排列
class Solution:def nextPermutation(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""n = len(nums)i = n - 2while i >= 0 and nums[i] >= nums[i+1]: i -= 1j = n - 1while i >= 0 and j >= 0 and nums[i] >= nums[j]: j -= 1nums[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) 使其变为升序，而无需对该区间进行排序。
"""93. 复原 IP 地址
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))returnif 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:breakbacktrace(0)return res2. 两数相加
# 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 = 0while l1 or l2 or carry != 0:n1 = l1.val if l1 else 0n2 = l2.val if l2 else 0n = n1 + n2 + carrycarry = n // 10cur.next = ListNode(n % 10)if l1: l1 = l1.nextif l2: l2 = l2.nextcur = cur.nextreturn dummpy.nextx 的平方根
class Solution:def mySqrt(self, x: int) -> int:# 由于 x 平方根的整数部分是满足 k^2≤x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。l = 0; r = xres = -1while l <= r:m = (l + r) // 2if m * m <= x:res = ml = m + 1else:r = m - 1return res8. 字符串转换整数 (atoi)
import re
class Solution:def myAtoi(self, str: str) -> int:INT_MAX = 2147483647 INT_MIN = -2147483648str = 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) #返回值22. 括号生成
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 ans41. 缺失的第一个正数
from 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 num239. 滑动窗口最大值
class 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剑指 Offer 22. 链表中倒数第k个节点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:p = q = headwhile k:q = q.nextk -= 1while q:p = p.nextq = q.nextreturn p76. 最小覆盖子串
from 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] += 1j = 0; cnt = 0for i in range(len(s)):hw[s[i]] += 1if hw[s[i]] <= ht[s[i]]: cnt += 1while j <= i and hw[s[j]] > ht[s[j]]:hw[s[j]] -= 1j += 1if cnt == len(t):if not res or len(res) > i - j + 1:res = s[j: i+1]return res165. 比较版本号
class 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 -1return 0
# 时间复杂度：O(n+m)
# 空间复杂度：O(n+m)43. 字符串相乘
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 = 0y = int(num2[i])curr = ["0"] * (n - i - 1)for j in range(m - 1, -1, -1):product = int(num1[j]) * y + addcurr.append(str(product % 10))add = product // 10if add > 0:curr.append(str(add))curr = "".join(curr[::-1])ans = self.addStrings(ans, curr)return ansdef addStrings(self, num1: str, num2: str) -> str:i, j = len(num1) - 1, len(num2) - 1add = 0ans = list()while i >= 0 or j >= 0 or add != 0:x = int(num1[i]) if i >= 0 else 0y = int(num2[j]) if j >= 0 else 0result = x + y + addans.append(str(result % 10))add = result // 10i -= 1j -= 1return "".join(ans[::-1])
32. 最长有效括号
class Solution:def longestValidParentheses(self, s: str) -> int:if not s: return 0res = 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)# 当前全部数减去剩余无法配对的数（单身）即reselse: res = max(res, i - stack[-1])return res105. 从前序与中序遍历序列构造二叉树
# 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 Noneroot = 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 root151. 反转字符串中的单词
class Solution:def reverseWords(self, s: str) -> str:return " ".join(s.split()[::-1])322. 零钱兑换
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 144. 二叉树的前序遍历
# 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: returnres.append(root.val)dfs(root.left)dfs(root.right)res = []dfs(root)return res