吃掉LeetCode之2022/2/5

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

代码思路：

感觉应该叫动态规划，但二维动态规划会超时，那么就转化为一维，精简些。
我们让最大利润为今天出售减去以前最小购入，然后维护前面最小购入值就行。

class Solution:def maxProfit(self, prices: List[int]) -> int:minn,maxx=1000000,0for i in prices:if i<minn:minn=iif i-minn>maxx:maxx=i-minnreturn maxx

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]

代码思路：

1. 单指针，先将0换到前面，在将1换到0后面

class Solution:def sortColors(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""n=len(nums)pos=0for i in range(n):if nums[i]==0:nums[i],nums[pos]=nums[pos],nums[i]pos+=1for i in range(pos,n):if nums[i]==1:nums[i],nums[pos]=nums[pos],nums[i]pos+=1

2. 双指针,原理和原来差不多，都是维护指针，然后交换

class Solution:def sortColors(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""n = len(nums)pos0 = pos1 = 0for i in range(n):if nums[i] == 1:nums[i], nums[pos1] = nums[pos1], nums[i]pos1 += 1elif nums[i] == 0:nums[i], nums[pos0] = nums[pos0], nums[i]if pos0 < pos1:nums[i], nums[pos1] = nums[pos1], nums[i]pos0 += 1pos1 += 1

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

代码思路：

动态规划，定义dp数组，$dp[i][j]$为从第一个到$i，j$位置的最小路径和，然后状态转移方程为
$$dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]$$
然后按这个思路处理一下边界就OK了

class Solution:def minPathSum(self, grid: List[List[int]]) -> int:n,m=len(grid),len(grid[0])dp=[[100000]*(m+1) for _ in range(n+1)]dp[1][1],dp[1][0],dp[0][1]=grid[0][0],0,0for i in range(n):for j in range(m):dp[i+1][j+1]=min(dp[i][j+1],dp[i+1][j])+grid[i][j]return dp[n][m]