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]是有利的，那么就留下tmpres=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=0def 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=gridfor r in range(nr):for c in range(nc):if r==0 and c==0: continueif 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[:])returnfor 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]*nnums=1for i in range(n):ans[i]=numsif nums*10<=n:nums*=10else:while nums%10==9 or nums+1>n:nums//=10nums+=1return 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*kif 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=0for 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=0for i in range(length):if A[addA+i]==B[addB+i]:k+=1ret=max(ret,k)else:k=0return retn,m=len(A),len(B)ret=0for 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:continueisland=[]grid[i][j]=-1q=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]=-1q.append((nx,ny))step = 0q = islandwhile True:tmp = qq = []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 stepif grid[nx][ny] == 0:grid[nx][ny] = -1q.append((nx, ny))step += 1

这个代码不需要判断step就可以直接最短，是因为，广度优先搜索就是一层一层的在找，所以一层一层的找一定能找到一个最近的岛屿，所以这个代码一定要学习