import heapq class Solution: def minmumNumberOfHost(self, n: int, startEnd: List[List[int]]) -> int: # 根据活动的开始时间对活动进行排序 startEnd.sort(key=lambda x: x[0]) # 初始化一个最小堆来存储当前正在进行的活动的结束时间 heap = [] # 初始化主持人数量 hosts = 1 ...

class Solution: def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]: for i in range(n): # 先按照对角线交换 for j in range(i+1, n): mat[i][j], mat[j][i] = mat[j][i], mat[i][j] for row in mat:  row.reverse() ...

class Solution: def solve(self , n: int, m: int, a: List[int]) -> List[int]: def func(i, j): while i < j: a[i], a[j] = a[j], a[i] i += 1 j -= 1 m = m % n # 避免过多的移动 func(0, n-1) # 先整体翻转 func(0,...

class Solution: def rob1(self , nums: List[int]) -> int: n = len(nums) if n == 0: return 0 elif n == 1: return nums[0] dp = [0]*n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) # 在进入循环前需要初始化两个 for i in ...

class Solution: def getLongestPalindrome(self, A: str) -> int: n = len(A) if n < 2: return n max_length = 1 def expandAroundCenter(left: int, right: int) -> int: while left >= 0 and right < n and A[left] == A[right]: ...

class Solution: def LIS(self, arr: List[int]) -> int: n = len(arr) if n == 0: return 0 dp = [1] * n # 初始化dp数组，每个元素至少可以单独成为一个子序列 for i in range(1, n): for j in range(i): if arr[i] > arr[j]: dp[i] ...

class Solution: def minMoney(self, arr: List[int], aim: int) -> int: dp = [float('inf')]*(aim+1) dp[0] = 0 for coin in arr: for x in range(coin, aim+1): dp[x] = min(dp[x], dp[x-coin]+1) return dp[-1] if dp[-1] != float('inf') else -...

class Solution: def solve(self, nums: str) -> int: n = len(nums) if n == 0: return 0 dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 if nums[0] != "0" else 0 for i in range(2, n + 1): if nums[i - 1] != "0": ...

class Solution: def minPathSum(self, matrix: List[List[int]]) -> int: if not matrix or not matrix[0]: return 0 n, m = len(matrix), len(matrix[0]) dp = [[0] * m for _ in range(n)] dp[0][0] = matrix[0][0] # 初始化第一行 for j in range(1, ...

class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[0] * n for _ in range(m)] # 初始化第一行和第一列 for i in range(m): dp[i][0] = 1 for j in range(n): dp[0][j] = 1 # 动态规划计算路径数量 for i in range(1, m): ...

class Solution: def LCS(self , str1: str, str2: str) -> str: if len(str1) < len(str2): # 从长度大的字符串开始遍历 str1, str2 = str2, str1 max_len = 0 # 记录最大子串的长度 res = '' for i in range(len(str1)): # 遍历一个字符串，遍历到的字符当作子串的最后一个字符，往前推，如果后面有比前面更长的子串就记录下来 ...

class Solution: def LCS(self, s1: str, s2: str) -> str: m, n = len(s1), len(s2) # 创建一个二维数组来存储最长公共子序列的长度 dp = [[0] * (n + 1) for _ in range(m + 1)] # 填充dp数组 for i in range(1, m + 1): for j in range(1, n + 1): if s1[i - 1] == ...

class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) dp = [0]*n dp[0] = cost[0] dp[1] = cost[1] for i in range(2, n): dp[i] = min(dp[i-1], dp[i-2]) + cost[i] # 特殊状态更新的斐波那楔数列 return min(dp[-1], dp[-...

class Solution: def jumpFloor(self , number: int) -> int: if number == 1: return 1 dp = [0]*number # 其实就是斐波那楔数列，只是dp[0]，dp[1]不同 dp[0], dp[1] = 1, 2 for i in range(2, number): dp[i] = dp[i-1] + dp[i-2] return dp[numb...