题目一、
75. 颜色分类（打卡）
def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ # lenth = len(nums) # count_1 = nums.count(1) # count_2 = nums.count(2) # count_0 = lenth - count_1 - count_2 # for i in range(lenth): # if i < count_0: # nums[i] = 0 # elif i < count_0 + count_1: # nums[i] = 1 # else: # nums[i] = 2 # return nums # 三指针(三路快排) r1 = r2 = -1 for i in range(len(nums)): if nums[i] < 2: r2 += 1 if i != r2: nums[r2], nums[i] = nums[i], nums[r2] if nums[r2] < 1: r1 += 1 if r1 != r2: nums[r1], nums[r2] = nums[r2], nums[r1] return nums
题目二、
class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 res_max = -float('inf') min_p = prices[0] for i in range(1, len(prices)): res_max = max(res_max, prices[i] - min_p) min_p = min(min_p, prices[i]) return res_max if res_max > 0 else 0
题目三、
def maxProfit(self, prices: List[int]) -> int: # 转换为寻找上升区间大小 i= 0 res = 0 for j in range(1, len(prices)): if prices[j] < prices[j-1]: res += prices[j-1] - prices[i] i = j # 处理末尾 elif j == len(prices) - 1: res += prices[j] - prices[i] return res
题目四、
def maxProfit(self, prices: List[int]) -> int: lenth = len(prices) if lenth < 2: return 0 dp_next = [0 for _ in range(lenth)] dp_pre = [0 for _ in range(lenth)] minval = prices[0] maxval = prices[-1] # 0-i最优 for i in range(1, lenth): dp_next[i] = max(dp_next[i-1], prices[i] - minval) minval = min(minval, prices[i]) # i~lenth-1最优 for i in range(lenth-2, -1, -1): dp_pre[i] = max(dp_pre[i+1], maxval - prices[i]) maxval = max(maxval, prices[i]) dp = [dp_next[i] + dp_pre[i] for i in range(lenth)] return max(dp)
题目五、
def numDecodings(self, s: str) -> int: dp = [1] + [0] * len(s) s = '9' + s for i in range(1, len(s)): if 10 <= int(s[i-1:i+1]) <=26: dp[i] += dp[i-2] if s[i] != '0': dp[i] += dp[i-1] return dp[-1]
题目六、
def uniquePaths(self, m: int, n: int) -> int: # m * n # rows = n; cols = m # 记忆化搜索 # if n == 1 or m == 1: # return 1 # memo = [[-1 for _ in range(m)] for _ in range(n)] # def dfs(i, j): # if i >= n or j >= m: # return 0 # if i == n-1 and j == m-1: # return 1 # if memo[i][j] == -1: # memo[i][j] = dfs(i+1, j) + dfs(i, j+1) # return memo[i][j] # dfs(0,0) # return memo[0][0] # 动态规划 dp = [[-1 for _ in range(m)] for _ in range(n)] for i in range(n): for j in range(m): if (i == 0 or j == 0): dp[i][j] = 1; else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[-1][-1]
题目七、
# 与62不同，这里的处理下边界。 def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: n = len(obstacleGrid) m = len(obstacleGrid[0]) dp = [[-1 for _ in range(m)] for _ in range(n)] for i in range(n): for j in range(m): if obstacleGrid[i][j] == 1: dp[i][j] = 0 elif i == 0 and j == 0: dp[i][j] = 1 elif i == 0: dp[i][j] = dp[i][j-1] elif j == 0: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[-1][-1]