Leetcode Hot 200 下
468. 验证IP地址
class Solution:def validIPAddress(self, queryIP: str) -> str:def isIPv4(ip: str) -> bool:return all(s and s.isdigit() and not(s[0] == '0' and len(s) > 1) and 0 <= int(s) <= 255 for s in sp) if len(sp := ip.split(".")) == 4 else Falsedef isIPv6(ip: str) -> bool:return all(s and len(s) <= 4 and all(c in "0123456789ABCDEFabcdef" for c in s) for s in sp) if len(sp := ip.split(":")) == 8 else Falseif "." in queryIP and ":" not in queryIP and isIPv4(queryIP):return "IPv4"elif ":" in queryIP and "." not in queryIP and isIPv6(queryIP):return "IPv6"return "Neither"560. 和为 K 的子数组
class Solution:def subarraySum(self, nums: List[int], k: int) -> int:res = 0pre = 0mp = defaultdict(int)mp[0] = 1for num in nums:pre += numres += mp[pre-k]mp[pre] += 1return res138. 复制带随机指针的链表
"""
# Definition for a Node.
class Node:def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):self.val = int(x)self.next = nextself.random = random
"""class Solution:def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':if not head: return Noned = dict()p = headwhile p:d[p] = Node(p.val)p = p.nextp = headwhile p:d[p].next = d.get(p.next)d[p].random = d.get(p.random)p = p.nextreturn d[head]209. 长度最小的子数组
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:n = len(nums)res = n + 1; sums = 0start = 0; end = 0while end < n:sums = sums + nums[end]while sums >= target:res = min(res, end - start + 1)sums -= nums[start]start += 1end += 1return res if res != n + 1 else 0# 时间复杂度：O(n)
# 空间复杂度：O(1)739. 每日温度
class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:stack, ans = [], [0] * len(temperatures)# 1.若栈为空或当日温度小于栈顶温度，则直接入栈# 2.若当日温度大于栈顶温度，说明栈顶元素升温日找到，将栈顶元素出栈，计算其与当日相差的天数for day, tmp in enumerate(temperatures):while stack and tmp > stack[-1][0]:stack_tmp, stack_day = stack.pop()ans[stack_day] = day - stack_daystack.append((tmp, day))return ans136. 只出现一次的数字
class Solution:def singleNumber(self, nums: List[int]) -> int:res = 0for num in nums:res ^= numreturn res498. 对角线遍历
class Solution:def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:res = []m = len(mat); n = len(mat[0])for k in range(m+n-1):if k % 2 == 0:res += [mat[x][k-x] for x in range(min(m-1,k), max(-1,k-n), -1)]else:res += [mat[x][k-x] for x in range(max(0,k-n+1),min(m,k+1))]return res剑指 Offer 36. 二叉搜索树与双向链表
"""
# Definition for a Node.
class Node:def __init__(self, val, left=None, right=None):self.val = valself.left = leftself.right = right
"""
class Solution:def dfs(self, root: 'Node') -> 'Node':if not root: returnself.dfs(root.left)# 双向链表root.left = self.preself.pre.right = root# 右移指针self.pre = rootself.dfs(root.right)def treeToDoublyList(self, root: 'Node') -> 'Node':if not root: returnself.pre = head = Node()self.dfs(root)# 首尾相连self.pre.right, head.right.left = head.right, self.prereturn head.right224. 基本计算器
class Solution:def calculate(self, s: str) -> int:ops = [1]sign = 1res = 0n = len(s)i = 0while i < n:if s[i] == ' ':i += 1elif s[i] == '+':sign = ops[-1]i += 1elif s[i] == '-':sign = -ops[-1]i += 1elif s[i] == '(':ops.append(sign)i += 1elif s[i] == ')':ops.pop()i += 1else:num = 0while i < n and s[i].isdigit():num = num * 10 + ord(s[i]) - ord('0')i += 1res += num * signreturn res剑指 Offer 09. 用两个栈实现队列
class CQueue:def __init__(self):self.s1, self.s2 = [], []def appendTail(self, value: int) -> None:self.s1.append(value)def deleteHead(self) -> int:if not self.s2:while self.s1: self.s2.append(self.s1.pop())return self.s2.pop() if self.s2 else -1# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()460. LFU 缓存
class Node:def __init__(self, key, val, pre=None, nex=None, freq=0):self.pre = preself.nex = nexself.freq = freqself.val = valself.key = keydef insert(self, nex):nex.pre = selfnex.nex = self.nexself.nex.pre = nexself.nex = nexdef create_linked_list():head = Node(0, 0)tail = Node(0, 0)head.nex = tailtail.pre = headreturn (head, tail)class LFUCache:def __init__(self, capacity: int):self.capacity = capacityself.size = 0self.minFreq = 0self.freqMap = collections.defaultdict(create_linked_list)self.keyMap = {}def delete(self, node):if node.pre:node.pre.nex = node.nexnode.nex.pre = node.preif node.pre is self.freqMap[node.freq][0] and node.nex is self.freqMap[node.freq][-1]:self.freqMap.pop(node.freq)return node.keydef increase(self, node):node.freq += 1self.delete(node)self.freqMap[node.freq][-1].pre.insert(node)if node.freq == 1:self.minFreq = 1elif self.minFreq == node.freq - 1:head, tail = self.freqMap[node.freq - 1]if head.nex is tail:self.minFreq = node.freqdef get(self, key: int) -> int:if key in self.keyMap:self.increase(self.keyMap[key])return self.keyMap[key].valreturn -1def put(self, key: int, value: int) -> None:if self.capacity != 0:if key in self.keyMap:node = self.keyMap[key]node.val = valueelse:node = Node(key, value)self.keyMap[key] = nodeself.size += 1if self.size > self.capacity:self.size -= 1deleted = self.delete(self.freqMap[self.minFreq][0].nex)self.keyMap.pop(deleted)self.increase(node)912. 排序数组
class Solution:def merge(self, left: list, right: list) -> list:res = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:res.append(left[i])i += 1else:res.append(right[j])j += 1if i == len(left):res.extend(right[j:])else:res.extend(left[i:])return resdef sortArray(self, nums: List[int]) -> List[int]:n = len(nums)if n <= 1: return numsm = n // 2l = self.sortArray(nums[:m])r = self.sortArray(nums[m:])return self.merge(l, r)207. 课程表
class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:edges = collections.defaultdict(list)indeg = [0] * numCoursesfor info in prerequisites:edges[info[1]].append(info[0])indeg[info[0]] += 1q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])visited = 0while q:visited += 1u = q.popleft()for v in edges[u]:indeg[v] -= 1if indeg[v] == 0:q.append(v)return visited == numCourses402. 移掉 K 位数字
class Solution:def removeKdigits(self, num: str, k: int) -> str:numStack = []# 构建单调递增的数字串for digit in num:while k and numStack and numStack[-1] > digit:numStack.pop()k -= 1numStack.append(digit)# 如果 K > 0，删除末尾的 K 个字符finalStack = numStack[:-k] if k else numStack# 抹去前导零return "".join(finalStack).lstrip('0') or "0"958. 二叉树的完全性检验
# 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 isCompleteTree(self, root: Optional[TreeNode]) -> bool:q = [root]f = Falsewhile q:node = q.pop(0)if not node: f = Trueelse:if f: return Falseq.append(node.left)q.append(node.right)return True61. 旋转链表
class Solution:def rotateRight(self, head: ListNode, k: int) -> ListNode:# 若链表为空，返回headif not head:return head# 获取链表的长度n = 0cur = headwhile cur:n += 1cur = cur.next# 若k的长度大于n，将k对n求余k = k % n# 若k==0表示循环了一整遍，直接返回headif k == 0:return head# 创建快慢指针slow = fast = head# fast指针先走k步while k:fast = fast.nextk -= 1# 让fast指针走到队尾while fast.next:fast = fast.nextslow = slow.next# 此时show.next为新的链表头h = slow.next# 断开slow.nextslow.next = None# 链表首位相接fast.next = head# 返回新的链表头return h11. 盛最多水的容器
class Solution:def maxArea(self, height: List[int]) -> int:res = 0l = 0; r = len(height) - 1while l < r:# 相同条件下边界距离越远，面积越大，所以设置左右指针从两边向中间移动；哪个边界小，哪个边界移动重新寻找机会，希望用边界高度的增加弥补两边界距离的减小if height[l] < height[r]:res = max(res, (r - l) * height[l])l += 1else:res = max(res, (r - l) * height[r])r -= 1return res剑指 Offer 54. 二叉搜索树的第k大节点
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def kthLargest(self, root: TreeNode, k: int) -> int:#先尝试中序遍历保存所有节点，再找倒数第k个节点def inOrder(root):if not root: returninOrder(root.left)self.inorder.append(root.val)inOrder(root.right) self.inorder = []inOrder(root)return self.inorder[-k]剑指 Offer 10- II. 青蛙跳台阶问题
class Solution:def numWays(self, n: int) -> int:p = 0; q = 1for i in range(n):p, q = q, p+qreturn q % 100000000779. 单词搜索
class Solution(object):# 定义上下左右四个行走方向directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]def exist(self, board, word):""":type board: List[List[str]]:type word: str:rtype: bool"""m = len(board)if m == 0:return Falsen = len(board[0])visited = [[0 for _ in range(n)] for _ in range(m)]for i in range(len(board)):for j in range(len(board[0])):if board[i][j] == word[0]:# 将该元素标记为已使用visited[i][j] = 1if self.backtrack(i, j, visited, board, word[1:]) == True:return Trueelse:# 回溯visited[i][j] = 0return Falsedef backtrack(self, i, j, visited, board, word):if len(word) == 0:return Truefor direct in self.directs:cur_i = i + direct[0]cur_j = j + direct[1]if cur_i >= 0 and cur_i < len(board) and cur_j >= 0 and cur_j < len(board[0]) and board[cur_i][cur_j] == word[0]:# 如果是已经使用过的元素，忽略if visited[cur_i][cur_j] == 1:continue# 将该元素标记为已使用visited[cur_i][cur_j] = 1if self.backtrack(cur_i, cur_j, visited, board, word[1:]) == True:return Trueelse:# 回溯visited[cur_i][cur_j] = 0return False剑指 Offer 51. 数组中的逆序对
class Solution:def merge_sort(self, a: list, l: int, r: int) -> int:if l >= r: return 0tmp = []m = l + r >> 1i = l; j = m + 1res = self.merge_sort(a, l, m) + self.merge_sort(a, m + 1, r)while i <= m and j <= r:if a[i] <= a[j]:tmp.append(a[i])i += 1else:res += m - i + 1tmp.append(a[j])j += 1tmp += a[i: m + 1]; tmp += a[j: r + 1]a[l: r + 1] = tmpreturn resdef reversePairs(self, nums: List[int]) -> int:return self.merge_sort(nums, 0, len(nums) - 1)59. 螺旋矩阵 II
class Solution:def generateMatrix(self, n: int) -> List[List[int]]:l, r, t, b = 0, n - 1, 0, n - 1res = [[0 for _ in range(n)] for _ in range(n)]num, tar = 1, n * nwhile num <= tar:for i in range(l, r + 1): # left to rightif num <= tar:res[t][i] = numnum += 1t += 1for i in range(t, b + 1): # top to bottomif num <= tar:res[i][r] = numnum += 1r -= 1for i in range(r, l - 1, -1): # right to leftif num <= tar:res[b][i] = numnum += 1b -= 1for i in range(b, t - 1, -1): # bottom to topif num <= tar:res[i][l] = numnum += 1l += 1return res47. 全排列 II
class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:nums.sort()self.res = []check = [0 for i in range(len(nums))]self.backtrack([], nums, check)return self.resdef backtrack(self, sol, nums, check):if len(sol) == len(nums):self.res.append(sol)returnfor i in range(len(nums)):if check[i] == 1:continueif i > 0 and nums[i] == nums[i-1] and check[i-1] == 0:continuecheck[i] = 1self.backtrack(sol+[nums[i]], nums, check)check[i] = 0
55. 跳跃游戏
class Solution:def canJump(self, nums: List[int]) -> bool:end = 0for i in range(len(nums)):if i > end: return Falseend = max(end, i+nums[i])return True40. 组合总和 II
from typing import Listclass Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:def dfs(begin, path, residue):if residue == 0:res.append(path[:])returnfor index in range(begin, size):if candidates[index] > residue:breakif index > begin and candidates[index - 1] == candidates[index]:continuepath.append(candidates[index])dfs(index + 1, path, residue - candidates[index])path.pop()size = len(candidates)if size == 0:return []candidates.sort()res = []dfs(0, [], target)return res123. 买卖股票的最佳时机 III
class Solution:def maxProfit(self, prices: List[int]) -> int:if not prices: return 0k = 2n = len(prices)k = min(k, n // 2)buy = [0] * (k + 1)sell = [0] * (k + 1)buy[0], sell[0] = -prices[0], 0for i in range(1, k + 1):buy[i] = sell[i] = float("-inf")for i in range(1, n):buy[0] = max(buy[0], sell[0] - prices[i])for j in range(1, k + 1):buy[j] = max(buy[j], sell[j] - prices[i])sell[j] = max(sell[j], buy[j - 1] + prices[i]); return max(sell)26. 删除有序数组中的重复项
class Solution:def removeDuplicates(self, nums: List[int]) -> int:j = 1for i in range(1, len(nums)):if nums[i] != nums[j-1]:nums[j] = nums[i]j += 1return j剑指 Offer 42. 连续子数组的最大和
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)50. Pow(x, n)
class Solution:def myPow(self, x: float, n: int) -> float:res = 1if n < 0: n = -n; x = 1 / xwhile n:if n % 2 == 1: res *= x# if n & 1: res *= xx = x * xn //= 2# n >>= 1return res518. 零钱兑换 II
class Solution:def change(self, amount: int, coins: List[int]) -> int:# dp[x] 表示金额之和等于 x 的硬币组合数# 动态规划的边界是 dp[0]=1。只有当不选取任何硬币时，金额之和才为 0，因此只有 1 种硬币组合dp = [0] * (amount + 1)dp[0] = 1for coin in coins:for i in range(coin, amount + 1):dp[i] += dp[i - coin]return dp[amount]145. 二叉树的后序遍历
# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:def dfs(root: TreeNode):if root is None: return dfs(root.left)dfs(root.right)res.append(root.val)res = []dfs(root)return res剑指 Offer 40. 最小的k个数
class Solution:def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:if len(arr) <= k: return arrdef quikSort(l, r):i, j = l + 1, rwhile True:while i < r and arr[i] <= arr[l]: i += 1while j > l and arr[j] > arr[l]: j -= 1if i >= j: breakarr[i], arr[j] = arr[j], arr[i]arr[l], arr[j] = arr[j], arr[l]if k < j: quikSort(l, j-1)if k > j: quikSort(j+1, r)return arr[:k]return quikSort(0,len(arr)-1)7. 整数反转
class Solution:def reverse(self, x: int) -> int:res = int((str(x) if x > 0 else str(-x) + "-")[::-1])return res if -231 < res < 231 else 074. 搜索二维矩阵
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:row = len(matrix); col = len(matrix[0])l = 0; r = row * col - 1while l <= r:m = l + r >> 1num = matrix[m//col][m%col]if num == target:return Trueelif num < target:l = m + 1else:r = m - 1return False# 展开成一维数组
# 时间复杂度：O(logmn)，其中 m 和 n 分别是矩阵的行数和列数。
# 空间复杂度：O(1)剑指 Offer 10- I. 斐波那契数列
class Solution:def fib(self, n: int) -> int:p = 0; q = 1for i in range(n):p, q = q, p+qreturn p % 1000000007440. 字典序的第K小数字
class Solution:def getSteps(self, cur: int, n: int) -> int:steps, first, last = 0, cur, curwhile first <= n:steps += min(last, n) - first + 1first *= 10last = last * 10 + 9return stepsdef findKthNumber(self, n: int, k: int) -> int:cur = 1k -= 1while k:steps = self.getSteps(cur, n)if steps <= k:k -= stepscur += 1else:cur *= 10k -= 1return cur450. 删除二叉搜索树中的节点
# 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 deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:if not root: return Noneif root.val > key: root.left = self.deleteNode(root.left, key) # 去左子树删除elif root.val < key: root.right = self.deleteNode(root.right, key) # 去右子树删除# 当前节点就是要删除的节点else:if not root.left: return root.right # 当前节点无左子树，不要写成 root = root.right，这样会多走一步报空值异常if not root.right: return root.left # 当前节点无右子树，不要写成 root = root.left，这样会多走一步报空值异常else: # 当前节点左右子树都有node = root.rightwhile node.left: # 寻找欲删除节点右子树的最左节点node = node.leftnode.left = root.left # 将欲删除节点的左子树成为其右子树最左节点的左子树root = root.right # 欲删除节点的右子树顶替其位置，节点被删除return root# 根据二叉搜索树的性质:
# 1. 如果目标节点大于当前节点值，则去右子树中删除；
# 2. 如果目标节点小于当前节点值，则去左子树中删除；
# 3. 如果目标节点就是当前节点，分为以下三种情况：
# 3.1 其无左子：其右子顶替其位置，删除了该节点；
# 3.2 其无右子：其左子顶替其位置，删除了该节点；
# 3.3 其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。# 时间复杂度：O（H），H是树的高度，寻找目标节点最坏情况需要O（H），删除操作最坏情况也需要O（H）；
# 空间复杂度：O（H），递归栈的深度最坏情况为树的高度；剑指 Offer 04. 二维数组中的查找
class Solution:def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:if not matrix: return Falsem = len(matrix); n = len(matrix[0])i = 0; j = n - 1while i < m and j >= 0:if matrix[i][j] == target: return Trueelif matrix[i][j] < target: i += 1else: j -= 1return False75. 颜色分类
class Solution:def sortColors(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""if len(nums) < 2: return# 循环不变量确定循环变量 # 0 in [0, p0), 1 in [p0, p1), 2 in [p2, len(nums)]p1 = 0; p0 = 0; p2 = len(nums) - 1# 循环变量 p1 > p2 时， 跳出循环while p1 <= p2:if nums[p1] == 0: # 0, 1交换，由于交换到右边的是1, 所以根据第二个if条件p1++nums[p1], nums[p0] = nums[p0], nums[p1]p0 += 1p1 += 1elif nums[p1] == 1:p1 += 1else: # nums[p1] == 2nums[p1], nums[p2] = nums[p2], nums[p1]# 由于不知道交换回来的nums[p2]的值，所以不对循环变量 p1 操作，进入下一次循环判断p2 -= 1# 归并排序思想剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
class Solution:def exchange(self, nums: List[int]) -> List[int]:l = 0; r = len(nums) - 1while l <= r:while l <= r and nums[l] % 2 == 1:l += 1while l <= r and nums[r] % 2 == 0:r -= 1if l > r: breaknums[l], nums[r] = nums[r], nums[l]return nums230. 二叉搜索树中第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 dfs(root):if not root: returndfs(root.left)self.res.append(root.val)dfs(root.right)self.res = []dfs(root)return self.res[k-1]225. 用队列实现栈
class MyStack:def __init__(self):self.q = []def push(self, x: int) -> None:n = len(self.q)self.q.append(x) for _ in range(n):self.q.append(self.q.pop(0))def pop(self) -> int:return self.q.pop(0)def top(self) -> int:return self.q[0]def empty(self) -> bool:return not self.q# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()# 入栈操作时，首先获得入栈前的元素个数 nn，然后将元素入队到队列，再将队列中的前 nn 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。135. 分发糖果
class Solution:def candy(self, ratings: List[int]) -> int:left = [1 for _ in range(len(ratings))]right = left[:]for i in range(1, len(ratings)):if ratings[i] > ratings[i - 1]: left[i] = left[i - 1] + 1count = left[-1]for i in range(len(ratings) - 2, -1, -1):if ratings[i] > ratings[i + 1]: right[i] = right[i + 1] + 1count += max(left[i], right[i])return count
剑指 Offer 62. 圆圈中最后剩下的数字
class Solution:def lastRemaining(self, n: int, m: int) -> int:f = 0for i in range(2, n+1):# dp[n,m] = 0 n = 1# dp[n,m] = (dp[n-1,m] + m) % n n > 1f = (f + m) % ireturn f45. 跳跃游戏 II
class Solution:def jump(self, nums: List[int]) -> int:res = 0end = max_v = 0for i in range(len(nums)-1):max_v = max(max_v, i+nums[i])if i == end:end = max_vres += 1return res
# 1.维护几个变量：当前所能达到的最远位置 end，下一步所能跳到的最远位置 max_pos，最少跳跃次数 setps。
# 2.遍历数组 nums 的前 len(nums) - 1 个元素：
# 每次更新第 i 位置下一步所能跳到的最远位置 max_pos。
# 如果索引 i 到达了 end 边界，则：更新 end 为新的当前位置 max_pos，并令步数 setps 加 1。
# 3.最终返回跳跃次数 steps。# 时间复杂度：O(n)O(n)。一重循环遍历的时间复杂度是 O(n)O(n)，所以总体时间复杂度为 O(n)O(n)。
# 空间复杂度：O(1)O(1)。只用到了常数项的变量，所以总体空间复杂度为 O(1)O(1)。91. 解码方法
class Solution:def numDecodings(self, s: str) -> int:n = len(s)dp = [1] + [0] * nfor i in range(1, n + 1):if s[i - 1] != '0':dp[i] += dp[i - 1]if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:dp[i] += dp[i - 2]return dp[n]329. 矩阵中的最长递增路径
class Solution:def longestIncreasingPath(self, matrix: List[List[int]]) -> int:if not matrix:return 0h,w = len(matrix),len(matrix[0])store = [[None]*(w) for i in range(h)]m = 0 #储存max路径值def search_nearby(i,j):nonlocal mcompare = [] #储存可以比较的候选人#这个楼主很懒,还没想怎么简化下面的代码#反正下面四个代码块就是分别看一下上、下、左、右哪些格子的值可以当做候选人比较#上if i != 0 and matrix[i-1][j] < matrix[i][j]: #有上边且上边小于当前数的话compare.append(store[i-1][j]) if store[i-1][j] else compare.append(search_nearby(i-1,j))#左if j != 0 and matrix[i][j-1] < matrix[i][j]: #有左边且左边小于当前数的话compare.append(store[i][j-1]) if store[i][j-1] else compare.append(search_nearby(i,j-1))#下if i != h-1 and matrix[i+1][j] < matrix[i][j]: #有下边且下边小于当前数的话compare.append(store[i+1][j]) if store[i+1][j] else compare.append(search_nearby(i+1,j))#右if j != w-1 and matrix[i][j+1] < matrix[i][j]: #有右边且右边小于当前数的话compare.append(store[i][j+1]) if store[i][j+1] else compare.append(search_nearby(i,j+1))store[i][j] = max(compare)+1 if compare else 1#如果没有compare说明这是一个很小的数，是一个起始点，能组成的长度只有1#有的话就原来最长路径+1m = max(m,store[i][j])return (store[i][j])for i in range(h):for j in range(w):if not store[i][j]:search_nearby(i,j)return m572. 另一棵树的子树
# 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 dfs(self, p, q):if not p and not q: return Trueif not p or not q: return Falsereturn p.val == q.val and self.dfs(p.left, q.left) and self.dfs(p.right, q.right)def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:if not root and not subRoot: return Trueif not root or not subRoot: return Falsereturn self.dfs(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)328. 奇偶链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head:return headodd = head; even = evenHead = head.nextwhile even and even.next:odd.next = even.nextodd = odd.nexteven.next = odd.nexteven = even.nextodd.next = evenHeadreturn head114. 二叉树展开为链表
# 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."""res = []def dfs(root):if root is None: returnres.append(root)dfs(root.left) dfs(root.right)dfs(root)for i in range(1, len(res)):pre, cur = res[i-1], res[i]pre.left = Nonepre.right = cur# 前序遍历
# 时间复杂度：O(n)
# 空间复杂度：O(n)208. 实现 Trie (前缀树)
class Trie:def __init__(self):self.children = [None] * 26self.isEnd = Falsedef searchPrefix(self, prefix: str) -> "Trie":node = selffor ch in prefix:ch = ord(ch) - ord("a")if not node.children[ch]:return Nonenode = node.children[ch]return nodedef insert(self, word: str) -> None:node = selffor ch in word:ch = ord(ch) - ord("a")if not node.children[ch]:node.children[ch] = Trie()node = node.children[ch]node.isEnd = Truedef search(self, word: str) -> bool:node = self.searchPrefix(word)return node is not None and node.isEnddef startsWith(self, prefix: str) -> bool:return self.searchPrefix(prefix) is not None# 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)9. 回文数
class Solution:def isPalindrome(self, x: int) -> bool:return str(x) == str(x)[::-1]剑指 Offer 26. 树的子结构
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None#1.先序遍历树A中的每个节点， 2.再判断A中每个节点是否包含Bclass Solution:#子结构def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:#包含def dfs(A: TreeNode, B: TreeNode) -> bool:# 当节点B为空：说明树B已匹配完成（越过叶子节点），因此返回True；if not B: return True# 当节点A为空：说明已经越过树A叶子节点，即匹配失败，返回False； # 当节点A和B的值不同：说明匹配失败，返回False；if not A or A.val != B.val: return Falsereturn dfs(A.left,B.left) and dfs(A.right,B.right)if not A or not B: return Falsereturn dfs(A,B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)189. 轮转数组
class Solution:def rotate(self, nums: List[int], k: int) -> None:"""Do not return anything, modify nums in-place instead."""n = len(nums)k %= ntmp = nums[-k:] + nums[:-k]nums[:] = tmp[:]384. 打乱数组
class Solution:def __init__(self, nums: List[int]):self.nums = numsself.original = nums.copy()def reset(self) -> List[int]:self.nums = self.original.copy()return self.numsdef shuffle(self) -> List[int]:for i in range(len(self.nums)):j = random.randrange(i, len(self.nums))self.nums[i], self.nums[j] = self.nums[j], self.nums[i]return self.nums# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()125. 验证回文串
class Solution:def isPalindrome(self, s: str) -> bool:# isalnum() 方法检测字符串是否由字母和数字组成。t = ''.join(c.lower() for c in s if c.isalnum())return t == t[::-1]10. 正则表达式匹配
class Solution:def isMatch(self, s: str, p: str) -> bool:m, n = len(s), len(p)def matches(i: int, j: int) -> bool:if i == 0:return Falseif p[j - 1] == '.':return Truereturn s[i - 1] == p[j - 1]dp = [[False] * (n + 1) for _ in range(m + 1)]dp[0][0] = Truefor i in range(m + 1):for j in range(1, n + 1):if p[j - 1] == '*':dp[i][j] |= dp[i][j - 2]if matches(i, j - 1):dp[i][j] |= dp[i - 1][j]else:if matches(i, j):dp[i][j] |= dp[i - 1][j - 1]return dp[m][n]
