2024.8.26 Python，最大子数和与动态规划，最小路径和，分割回文串，字典序排数，最长重复子数组（动态规划）
1.最大子数和
接上周的文章：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
方法一：
class Solution:
def maxSubArray(self,nums:List[int])->int:
tmp=nums[0] #当前当下的列表和
n=len(nums)
res=tmp #结果
for i in range(1,n):
if tmp+nums[i]>nums[i]: #tmp对nums[i]是有利的，那么就留下tmp
res=max(res,tmp+nums[i]) #max的对象是nums[i]+tmp还有res，为什么不需要加tmp是因为判断结束后就已经决定拓展了，res里存了之前的tmp，假如nums[i]是个复数，那么res就胜出了
tmp+=nums[i] #列表加进nums[i]
else: #说明tmp该丢了
res=max(res,tmp+nums[i],tmp,nums[i]) #在场的各位都最后做一次对比吧最后的波纹了
tmp=nums[i] #丢了重开
return res
代码逻辑：
这个题为什么不用tmp+nums[i]>tmp来判断，反而是用tmp + nums[i] > nums[i]：
tmp+nums[i]>tmp这个条件只是简单判断加入当前元素是否能让和变大，但它忽略了一个重要情况：如果 nums[i] 本身比 tmp + nums[i] 更大（即当前元素自身的值已经大于累加之前的和），我们就应该重新开始新的子数组，而不是继续扩展之前的子数组。也就是说，添加这个判断的目的不是为了决定要不要nums[i]而是现在要不要tmp也就是说是保留还是新建，是生存还是毁灭问题，tmp如果加了nums[i]比nums[i]还小，那么tmp就该丢了
为什么 tmp + nums[i] > nums[i] 更合理
tmp + nums[i] > nums[i] 这个条件能够很好地捕捉到何时应该开始一个新的子数组，因为它考虑了当前元素是否比累积和加上当前元素还要大。
方法二动态规划
现在创造一个新的列表，列表中的每一个元素下标和之前的元素一一对应，但是这个列表代表nums[i]为最后一个元素的数组最大和，这个列表名字叫dp的话，那么就有以下的列表：
nums=[-2,1,-3,4,-1,2,1,-5,4]
dp= [-2,1,-2,4, 3,5,6, 1,5]
这个处理的规律是，dp[i]=max(dp[i-1]+nums[i],nums[i])这样处理之后找dp的最大值即可
代码如下：
class Solution:
def maxSubArray(self,nums:List[int])->int:
dp=[0]
dp[0]=nums[0]
for i in range(1,len(nums)):
dp.append(max(dp[i-1]+nums[i],nums[i]))
return max(dp)
也就是说上面所谓的暴力法其实就是动态规划
2.最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入：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
方法一：
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
nr=len(grid)
nc=len(grid[0])
res=[]
sums=0
def dfs(r,c,sums):
sums+=grid[r][c]
if r==nr-1 and c==nc-1:
res.append(sums)
return
if r!=nr-1:
dfs(r+1,c,sums)
if c!=nc-1:
dfs(r,c+1,sums)
dfs(0,0,sums)
return min(res)
深度优先搜索的写法，这是我自己写出来的办法，蠢但是能解决一定的问题，但是最后还是超时了，所以不推荐。
***方法二：***动态规划
上一个题中的dp[i]为一维的，而这次的dp变成了二维的，所谓动态规划就是说，我们在计算的过程中可以不需要从头再来计算一次，我们可以通过前人的经验来去总结规律，比如青蛙跳高问题，青蛙可以一次跳两个也可以一次跳一格，那么他跳到第n个格有多少种可能的跳法，我们就是要找到一些规律来去总结这个问题，比如现在就只有abcd四格，那么从a到b有一种，a到c有两种，那么a到d就有2+1=3种，那么a到e就是a到d加a到c。以此类推
也就是说我们要找到dp之间的规律，在跳青蛙这个题中dp的规律就是dp[n]=dp[n-1]+dp[n-2]
class Solution:
def minPathSum(self,grid:List[List[int]])->int:
nr=len(grid)
nc=len(grid[0])
dp=grid
for r in range(nr):
for c in range(nc):
if r==0 and c==0: continue
if r==0: dp[0][c]=dp[0][c-1]+grid[0][c]
elif c==0: dp[r][0]=dp[r-1][0]+grid[r][0]
else: dp[r][c]=min(dp[r-1][c],dp[r][c-1])+grid[r][c]
return dp[nr-1][nc-1]
逻辑就是，到达当前框的最小值，等于到达当前框的上方的框的最小值，和到达当前框的左边的框的最小值相比较，谁小谁加当前框的值。动态规划看不懂的就去CSDN搜动态规划出来的第一篇文章。
3.分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串 。返回 s 所有可能的分割方案。
class Solution:
def partition(self, s: str) -> List[List[str]]:
n = len(s)
f = [[True] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
f[i][j] = (s[i] == s[j]) and f[i + 1][j - 1]
ret = list()
ans = list()
def dfs(i: int):
if i == n:
ret.append(ans[:])
return
for j in range(i, n):
if f[i][j]:
ans.append(s[i:j+1])
dfs(j + 1)
ans.pop()
dfs(0)
return ret
代码逻辑：
讲道理，我这道题几乎完全没有看懂，这个题的逻辑太绕了，我将尽可能的把我的理解写出来，首先是两个for循环，这里的i是起始，j是终止，如果最后判断下来，将是一个左下的三角矩阵有变化，右上包括对角的元素都是True。ret是最后的结果，ans是小列表，dfs我理解的事以i为起始开始分割，遇见合适的就append，然后再下一个，我感觉这个代码我打死都自己写不出来。
4.字典序排数
给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
示例 1：
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例 2：
输入：n = 2
输出：[1,2]
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
ans=[0]*n
nums=1
for i in range(n):
ans[i]=nums
if nums*10<=n:
nums*=10
else:
while nums%10==9 or nums+1>n:
nums//=10
nums+=1
return ans
逆天顺序，代码就是这么个代码，也没啥好说的，就有10就乘10，没十就判断尾数是不是9或者nums+1就超，地板除10+1，进入下一次循环
方法二：dfs，难想
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
def dfs(k,res):
if k<=n:
res.append(k)
k=10*k
if k<=n:
for i in range(10): #目的是为了在下一层应用字典排序
dfs(k+i,res)
res=[]
for i in range(1,10):
dfs(i,res)
return res
这个更能体现字典的排序的方法，i=1，那就是1的字典，重点在于这个k+i，不是+1哦
方法三：
return sorted(range(1,n+1), key=str)
这样就已经够了
5.最长重复子数组
提示
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m,n=len(nums1),len(nums2)
dp=[[0]*(n+1) for _ in range(m+1)] #最后算下来是第一层没在循环中用上
ans=0
for i in range(1,m+1):
for j in range(1,n+1):
if nums1[i-1]==nums2[j-1]:
dp[i][j]=dp[i-1][j-1]+1 #第一层设定的目的是为了在这一步的dp[i-1][j-1]有数字
ans=max(ans,dp[i][j])
return ans
这个题给我做火了，为什么要用i-1和j-1我想不来，我照着抄完我肯定能理解为啥，但是这个题我完全不能想明白，等我自己做的时候会是什么样子，我完全不会想到j-1和i-1的事情。
代码逻辑：
1.dp比mn多一层
2.for循环里，i和j其实是dp的下标，不是nums的下标，所以要减一，他把nums的i-1等于j-1的时候，的长度存进了dp[i][j]里，所以他的范围是dp[m][n]存了最后一个数字。
方法二：滑动窗口
class Solution:
def findLength(self, A:List[int],B:List[int])->int:
def maxLength(addA:int,addB:int,length:int)->int:
ret=k=0
for i in range(length):
if A[addA+i]==B[addB+i]:
k+=1
ret=max(ret,k)
else:
k=0
return ret
n,m=len(A),len(B)
ret=0
for i in range(n):
length=min(m,n-i)
ret=max(ret,maxLength(i,0,length))
for i in range(m):
length=min(n,m-i)
ret=max(ret,maxLength(0,i,length))
return ret
完全看不懂
6.最短的桥
给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
返回必须翻转的 0 的最小数目。
示例 1：
输入：grid = [[0,1],[1,0]]
输出：1
示例 2：
输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2
示例 3：
输入：grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1
方法一：广度优先搜索
class Solution:
def shortestBridge(self,grid:List[List[int]])->int:
n=len(grid)
for i,row in enumerate(grid):
for j,v in enumerate(row):
if v!=1:
continue
island=[]
grid[i][j]=-1
q=deque([(i,j)]) #双端队列，里边是列表，列表里是元组
while q:
x,y=q.popleft()
island.append((x,y))
for nx,ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):
if 0<=nx<n and 0<=ny<n and grid[nx][ny]==1:
grid[nx][ny]=-1
q.append((nx,ny))
step = 0
q = island
while True:
tmp = q
q = []
for x, y in tmp:
for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):
if 0 <= nx < n and 0 <= ny < n:
if grid[nx][ny] == 1:
return step
if grid[nx][ny] == 0:
grid[nx][ny] = -1
q.append((nx, ny))
step += 1
这个代码不需要判断step就可以直接最短，是因为，广度优先搜索就是一层一层的在找，所以一层一层的找一定能找到一个最近的岛屿，所以这个代码一定要学习