婚恋网站建设成本,xd软件可做网站吗,抖音代运营电销话术,自己搭建网站的步骤1.最大子数组
题目链接#xff1a;53. 最大子数组和 - 力扣#xff08;LeetCode#xff09; 题目描述#xff1a;找出nums数组中的最大和连续数组#xff0c;并返回其最大和
算法讲解#xff1a;动态规划
1.状态表示#xff1a;经验题目要求
经验#xff1a;以某位…1.最大子数组
题目链接53. 最大子数组和 - 力扣LeetCode 题目描述找出nums数组中的最大和连续数组并返回其最大和
算法讲解动态规划
1.状态表示经验题目要求
经验以某位置为结尾什么什么什么
在这道题中因为要找出最大和的连续子数组并返回这个最大和所以在这道题中可以将dp[i]表示为以i位置为结尾的所有子数组中的最大和
2.状态转移方程
做这种线性dp的问题要画图来分析由于要找出以i位置为结尾的所有子数组的最大和首先就要找出nums数组所有以i为结尾的子数组此时找出的子数组可以划分为两种情况一种是长度为1的子数组另一种情况是长度大于1的子数组。
第一种情况长度为1的子数组
长度为1的子数组就是nums[i]此时的子数组的最大和就是nums[i]所以此时dp[i]nums[i]
第二种情况长度大于1的子数组
当子数组的长度大于1时此时子数组可以看成由一个以单独nums[i]组成的数组和一个以i-1的位置为结尾的数组组成的数组如下图 此时要想求dp[i]此时就要知道以i-1位置为结尾的子数组的最大和根据状态表示可以用dp[i-1]表示以i-1位置为结尾的子数组的最大和此时dp[i]dp[i-1]nums[i]
因为要求的是最大和所以最终的状态转移方程为 dp[i]Math.max(nums[i]dp[i-1]nums[i]) 3.初始化
此时由于求dp[i]时会用到dp[i-1]所以要初始化dp[0]dp[0]表示以第1个位置为结尾的所有子数组的最大和因为0是数组的起始位置此时就要将dp[0]nums[0]
4.填表顺序
从左往右填dp表即可
5.返回值
要返回dp表中的最大值
代码实现
//暴力枚举
class Solution {public int maxSubArray(int[] nums) {int nnums.length;int retInteger.MIN_VALUE;int sum0;for(int i0;in;i){for(int ji;jn;j){if(ij) sum0;sumnums[j];retMath.max(ret,sum);}}return ret;}
}//动态规划
class Solution {public int maxSubArray(int[] nums) {int nnums.length;int[] dpnew int[n];dp[0]nums[0];for(int i1;in;i)dp[i]Math.max(dp[i-1]nums[i],nums[i]);int retdp[0];for(int i0;in;i)if(retdp[i]) retdp[i];return ret;}
}
2.环形数组的最大和
题目链接918. 环形子数组的最大和 - 力扣LeetCode 题目解析不用看图片中的题目看也看不懂只需要知道nums是一个环形数组就行了
算法讲解
1.状态表示
首先分析一下题目由于nums数组是一个环形数组所以在环形数组中选择的子数组会有两种情况如下图 第一种情况就是子数组是在nums中的蓝色部分此时直接求出蓝色部分的子数组中最大和即可 第二种情况就是选中的子数组一部分是在尾部一部分在头部因为是环形数组所以这两部分也是连续的但是此时直接求出最大和是有点困难的但是可以装换一下思路 因为nums数组的总和是固定的此时要求最大和只要求出中间那部分子数组中的最小和通过总和减去中间部分的最小和可以间接得到最大和如下图 所以此时就会有两种状态表示 f[i]表示以i位置为结尾的所有子数组中的最大和 g[i]表示以i位置为结尾的所有子数组中的最小和 2.状态转移方程
因为有两个状态表示所以状态转移方程也有两种
推算f[i]推算f[i]时子数组也可以分为两种分别是长度为1的子数组和长度不为1的子数组如下图 当子数组的长度为1时此时子数组就是nums[i]所以此时f[i]nums[i]
当子数组的长度大于1时此时要计算f[i]就要知道以i-1位置为结尾的所有子数组中的最大和根据f[i]的状态表示f[i-1]可以表示以i-1位置为结尾的所有子数组中的最大和此时f[i]f[i-1]nums[i]
因为要求的是最大和所以f[i]的状态转移方程为 f[i]Math.max(nums[i]nums[i]f[i-1]) 推理g[i]的状态转移方程的过程一模一样同理可得 g[i]Math.min(nums[i]nums[i]g[i-1]) 3.初始化
此时为了方便初始化可以多创建一部分空间来实现初始化初始化时有两个注意事项
第一个注意事项虚拟空间填的值要保证后面的填表正确
假设没有多创建空间原本f[0]和g[0]要填的值就是nums[0]如果多创建了空间后原本的f[0]和g[0]就变成了f[1]和g[1]此时的f[0]和g[0]就是多创建的空间此时要想nums[0]被选上只要将f[0]和g[0]初始化为0即可因为nums[0]0的结果还是nums[0]
4.填表顺序
由于填表时用到了i-1所以要从左往右填表
5.返回值
此时是有一个细节的如果nums数组中全是负数此时直接返回fmax即可如果数组中不全是负数返回Math.max(fmaxsum-gmin)即可
代码实现
//我写的版本
class Solution {public int maxSubarraySumCircular(int[] nums) {int nnums.length;if(n1) return nums[0];int sum0;for(int i0;in;i) sumnums[i];int[] fnew int[n1];int[] gnew int[n1];f[0]g[0]0;for(int i1;in1;i){f[i]Math.max(nums[i-1],f[i-1]nums[i-1]);g[i]Math.min(nums[i-1],g[i-1]nums[i-1]);}int maxInteger.MIN_VALUE;int minInteger.MAX_VALUE;for(int i1;in1;i){if(maxf[i]) maxf[i];if(ming[i]) ming[i];}return summin?max:Math.max(max,sum-min);}
}//另一个版本
class Solution {public int maxSubarraySumCircular(int[] nums) {int nnums.length;int[] fnew int[n1];int[] gnew int[n1];int maxInteger.MIN_VALUE;int minInteger.MAX_VALUE;int sum0;for(int i1;in1;i){int xnums[i-1];f[i]Math.max(nums[i-1],nums[i-1]f[i-1]);maxMath.max(max,f[i]);g[i]Math.min(nums[i-1],nums[i-1]g[i-1]);minMath.min(min,g[i]);sumx;}return summin ? max : Math.max(max,sum-min);}
}
3.乘积最大子数组
题目链接152. 乘积最大子数组 - 力扣LeetCode 题目描述在nums数组中找出一个非空连续子数组且该子数组的乘积最大并返回该子数组的乘积
算法讲解动态规划
1.状态表示
其实这道题和第二道题很相似一开始肯定只会想到用一个dp[i]来表示以i位置为结尾的所有子数组的最大和但是这道题求的是乘积且nums数组中的nums[i]可能出现负数的情况当f[i]是一个很大的数时如果接着遇到nums[i]是一个负数那么之后f[i]就会变成一个很小的数所以此时还要记录以i位置为结尾的的所有子数组中的最小和所以最终的状态表示有2个 f[i]表示以i位置为结尾的所有子数组中的最大乘积 g[i]表示以i位置为结尾的所有子数组总的最小乘积 2.状态表示
因为状态表示有两个所以推算状态方程时也有两种
1.推算f[i]的状态转移方程
在推算f[i]时子数组也可以分为2种情况可以分为长度为1的子数组和长度大于1的子数组如下图 当子数组的长度为1时此时nums[i]就是子数组此时f[i]nums[i]
当子数组的长度不为1时如果按照我们平时的惯性思维此时要求f[i]就要先求出f[i-1]也就是要求出以i-1位置为结尾时的所有子数组中的最大乘积此时就得出f[i]f[i-1]*nums[i]但是这一道题的nums[i]有可能是负数的情况一个小的数与一个负数相乘就会变成一个大的数而g[i]就表示以i位置为结尾的所有子数组中的最小乘积所以此时f[i]g[i-1]*nums[i]
如下图 但是要求的是最大乘积所以最终f[i]的状态转移方程为 f[i]max(nums[i],f[i-1]*nums[i],g[i-1]*nums[i]) 同理可得g[i]的状态转移方程 g[i]min(nums[i],g[i-1]*nums[i-1],f[i-1]*nums[i-1]) 3.初始化
在这里依旧选择创建虚拟节点来实现初始化有两个注意事项
第一个注意事项虚拟节点填的值要保证后面的天表正确
填加了虚拟节点后此时的f[1]就是原来的f[0]此时初始化f[1]时是要将f[1]初始化为nums[0]的但是初始化时用到了f[i]max(nums[i],f[i-1]*nums[i],g[i-1]*nums[i]) 此时要保证max时让nums[i]被选到此时直接将f[0]和g[0]初始化为1就行了因为nums[i]*1的结果也是nums[i]
第二个注意事项注意下标的映射关系
4.填表顺序
要从左往右同时填f表和g表
5.代码实现
class Solution {public int maxProduct(int[] nums) {int nnums.length;if(n1) return nums[0];int[] fnew int[n1];int[] gnew int[n1];f[0]1;g[0]1;int retInteger.MIN_VALUE;for(int i1;in1;i){f[i]Math.max(nums[i-1],Math.max(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));g[i]Math.min(nums[i-1],Math.min(g[i-1]*nums[i-1],f[i-1]*nums[i-1]));if(f[i]ret) retf[i];}return ret;}
}
4.乘积为正数的最长子数组的长度
题目链接1567. 乘积为正数的最长子数组长度 - 力扣LeetCode 题目描述返回nums数组中乘积为正数的最长子数组的长度
算法讲解动态规划
1.状态表示经验题目要求
根据题目要求首先会设计出一个状态表示用f[i]来表示
f[i]表示以i位置为结尾的所有子数组中乘积为正数的最长长度
g[i]表示以i位置为结尾的所有子数组中乘积为负数的最长长度
2.状态转移方程
因为是子数组问题子数组的情况任然可以分为2中情况分别是长度为1的子数组和长度大于1的子数组如下图 推算f[i]
第一种情况子数组长度为1时
当子数组的长度为1时也是有两种情况的分别是nums[i]大于0和nums[i]0的情况。
当nums[i]0时此时f[i]1当nums[i]0时此时f[i]0
当子数组的长度大于1时也是有两种情况的分别是nums[i]大于0和nums[i]0的情况。
当nums[i]0时此时首先要知道以i-1位置为结尾的所有子数组中乘积为正数的最长长度根据f[i]的状态表示可以用f[i-1]来表示以i-1位置为结尾的所有子数组中乘积为正数的最长长度此时f[i]f[i-1]1
当nums[i]0时因为f[i]表示以i位置为结尾的所有子数组中乘积为正数的最长长度因为正数*负数等于负数所以此时还要知道以i-1为位置为结尾的所有子数组中乘积为负数的最长长度所以此时还要另外设计一个状态表示用g[i]表示以i位置为结尾的所有子数组中乘积为负数的最长长度此时就可以用g[i-1]来表示以i-1为位置为结尾的所有子数组中乘积为负数的最长长度此时惯性思维就直接让f[i]g[i-1]1了但是这样是不对的如果g[i-1]0说明i位置前面的数字全是正数相乘如果此时nums[i]0的话此时f[i]是等于0的因为子数组都要包含i位置这个数据如果按照上面的f[i]g[i-1]1此时计算的f[i]是等于1的所以此时的状态转移方程为 f[i] g[i-1]0 ? 0 : g[i-1]1 分析总结图如下 所以此时在推算状态转移方程时也要分为2中情况
第一种情况nums[i]0时此时f[i]Math.max(1,f[i-1]1)可以简化成f[i]f[i-1]1
第二种情况nums[i]0时此时f[i]Math.max(0,g[i-1]0?0:g[i-1]1) 可以简化成f[i]g[i-1]0?0:g[i-1]1
如下图 推算g[i]:
此时推算g[i]的过程和上面一模一样有一个细节不同
不同之处
当子数组的长度1时此时推算g[i]时有一个nums[i]0的情况此时可能惯性思维直接推出g[i]g[i-1]1但是这是不对的如果此时g[i-1]0说明前面都是正数相乘此时再加上nums[i]0此时g[i]是等于0的如果根据上面的g[i]g[i-1]1此时计算的g[i]是等于1的所以此时g[i]g[i-1]0?0:g[i-1]1 根据上面的分析总结图推出g[i]的状态转移方程
第一种情况nums[i]0时此时g[i]Math.max(0,g[i-1]0?0:g[i-1]1) 可以简化成g[i]g[i-1]0?0:g[i-1]1
第二种情况nums[i]0时此时g[i]Math.max(1,f[i-1]1)可以简化成f[i]f[i-1]1
3.初始化
这里依旧是选择多创建一部分空间实现初始化
根据一个表分析即可此时用g表来分析此时g[1]初始化有两种情况当nums[0]0时要将g[1]初始化为1所以根据g[i]状态转移方程小于0的情况此时要将g[0]初始化为0当nums[0]0时此时要将g[i]初始化为0根据g[i]状态转移方程大于0的情况此时要将f[0]初始化为0
第二个注意事项注意下标的映射关系
4.填表顺序
从左往右同时填两个表即可
5.返回值
返回f表中的最大值
代码实现
class Solution {public int getMaxLen(int[] nums) {int nnums.length;int[] fnew int[n1];int[] gnew int[n1];f[0]0;g[0]0;int retInteger.MIN_VALUE;for(int i1;in1;i){int xnums[i-1];if(x0){f[i]f[i-1]1;g[i]g[i-1]0?0:g[i-1]1;}else if(x0){f[i]g[i-1]0?0:g[i-1]1;g[i]f[i-1]1;}retMath.max(ret,f[i]);}return ret;}
}
5.等差数列划分
题目链接413. 等差数列划分 - 力扣LeetCode 题目解析返回nums数组中能够成等差数列的子数组的个数
算法讲解动态规划
1.状态表示经验题目要求
由于题目要求返回nums数组中所有为等差数列的子数组的个数此时就可以将状态表示
dp[i]表示以i位置元素为结尾的所有子数组中能构成等差数列的个数
2.状态转移方程
首先要知道如果[a,b,c,d]这4个数构成等差数列如果此时c,d,e也能构成等差数列此时a.b,c,d,e也是能构成等差数列的
现在开始分析因为构成等差数列至少需要3个元素所以分析时要至少以3个元素开始分析如下图 假设此时这3个元素是abc此时分析这三个数能否构成等差数列
第一种情况如果abc这3个数构成等差数列也就是nums[i]-nums[i-1]nums[i-1]-nums[i-1]此时如果要求出dp[i]首先就要知道以ab为结尾的所有子数组中能构成等差数列的子数组个数以ab结尾就是以b结尾此时就可以用dp[i-1]来表示以b结尾的所有子数组中能构成等差数列的个数此时dp[i]就是在dp[i-1]的基础上加1即可这里的加1是指dp[i-1]中没有包含a,b,c这种情况如下图 第二种情况abc这三个元素不构成等差数列如果abc这三个元素不够成等差数列那么此时abcd就也不会构成等差数列了此时直接让dp[i]0即可
3.初始化
因为构成等差数列至少需要3个数据所以要将dp[0]和dp[1]都初始化为0
4.填表顺序
从左往右填表即可
5.返回值
因为要返回能构成等差数列的子数组个数所以要用一个ret来记录
代码实现
class Solution {public int numberOfArithmeticSlices(int[] nums) {int nnums.length;if(n1||n2) return 0;int[] dpnew int[n];int ret0;for(int i2;in;i){if(nums[i]-nums[i-1]nums[i-1]-nums[i-2]){dp[i]dp[i-1]1;retdp[i];}else{dp[i]0;}}return ret;}
}
6.最长湍流子数组
题目链接978. 最长湍流子数组 - 力扣LeetCode 题目解析啥事湍流子数组呢数组中的数据呈现下面的趋势就是湍流数组如下图 算法讲解动态规划
1.状态表示经验题目要求
首先想到的状态表示肯定是
dp[i]表示以i位置为结尾的所有子数组中最长湍流子数组的长度
根据下面的分析推出两个状态表示
f[i]表示以i位置为结尾的所有子数组中最后呈现上升趋势状态下的最长湍流子数组的长度
g[i]表示以i位置为结尾的所有子数组中最后呈现下降趋势状态下的最长湍流子数组的长度
2.状态转移方程
此时推算dp[i]时由于找到子数组要是湍流子数组所以此时nums[i-1]和nums[i]组成的趋势有上升和下降的两种情况如下图 所以此时单独靠一个状态表示是不能够解决问题还要添加两个状态表示f[i]和g[i]
此时推算f[i]依旧是上图的三种情况来分析f[i]
第一种情况nums[i]nums[i-1]
当nums[i]nums[i-1]最后一段是上升的趋势由于要找的湍流子数组所以此时首先要找出以i-1位置为结尾的所有子数组中最后呈现下降趋势状态的最长湍流子数组的长度根据g[i]的状态表示可以用g[i-1]来表示所以此时f[i]g[i-1]1
第二种情nums[i]nums[i-1]
当nums[i]nums[i-1]此时最后一段呈现下降趋势不符合f[i]的状态表示所以让nums[i]单独成为一个湍流子数组则此时f[i]1
第三种情况nums[i]nums[i-1]
当nums[i]nums[i-1]此时最后一段呈现没有变化的趋势此时不符合f[i]的状态表示所以让nums[i]单独成为一个湍流子数组此时f[i]1
接着来推算g[i]还是上面这三种情况来分析
第一种情况nums[i]nums[i-1]
当nums[i]nums[i-1]最后一段是下降的趋势由于要找的湍流子数组所以此时首先要找出以i-1位置为结尾的所有子数组中最后呈现上升趋势状态的最长湍流子数组的长度根据f[i]的状态表示可以用f[i-1]来表示所以此时g[i]f[i-1]1
第二种情nums[i]nums[i-1]
当nums[i]nums[i-1]此时最后一段呈现上升趋势不符合g[i]的状态表示所以让nums[i]单独成为一个湍流子数组则此时g[i]1
第三种情况nums[i]nums[i-1]
当nums[i]nums[i-1]此时最后一段呈现没有变化的趋势此时不符合g[i]的状态表示所以让nums[i]单独成为一个湍流子数组此时g[i]1
3.初始化
此时可以先将f表和g表都初始化为1因为最坏的情况就是1还有一个好处就是写代码时就不用考虑f[i]和g[i]等于1的情况了
4.填表顺序
从左往右同时填两个表即可
5.返回值
返回f表和g表中的最大值
代码实现
class Solution {public int maxTurbulenceSize(int[] nums) {int nnums.length;int[] fnew int[n];int[] gnew int[n];for(int i0;in;i){f[i]1;g[i]1;}int ret1;for(int i1;in;i){if(nums[i]nums[i-1]){f[i]g[i-1]1;}else if(nums[i]nums[i-1]){g[i]f[i-1]1;}retMath.max(ret,Math.max(f[i],g[i]));}return ret;}
}
7.单词拆分
题目链接139. 单词拆分 - 力扣LeetCode 题目解析判断字符串s能不能有字典中的字符串拼接出来字典中的字符串可以重复使用
算法讲解动态规划
1.状态表示经验题目要求
在这道题因为要判断字符串能不能由字典中的字符串拼接出来可以这样定义状态表示
dp[i]表示[0i]区间内的字符串能否被字典中的字符串拼接而成
当dp[i]true时说明可以由字典中的字符串拼接而成
当dp[i]false时说明不可以由字典中的字符串拼接而成
2.状态转移方程
根据最后一个单词的情况来分析问题此时可以是字符串中的最后一个字符作为单独一个单词来作为最后一个单词也可以是最后一个字符和前面的字符合并成为一个单词作为最后一个单词如下图 此时子字符串就可以分为两种情况了也就是前面一个单词和最后一个单词如下图
此时要向判断dp[i]是true还是false也就是判断能不能由字典中的字符串拼接而成就需要判断前面一个单词能不能由字典中的字符串拼接而成和最后一个单词存不存在于字典中为了方便叙述为了方便叙述用一个变量j来表示最后一个单词的起始位置此处的j是小于等于i且大于等于0的要想则dp[j-1]就是[0j-1]区间内的字符串能否由字典中的单词拼接而成如果dp[j-1]true且最后一个单词存在于字典中则dp[i]就等于true否则dp[i]就等于false如下图 3.初始化
为了方便初始化将创建虚拟节点来实现初始化此时需要注意虚拟节点填的值要保证后面填表正确和下标映射的问题
下标映射这里可以往s的前面加一个空格就可以避免下标映射的问题了
4.填表顺序
从左往右填表即可
5.返回值
返回dp[n]即可
代码实现
为什么第二个循环里面是j1呢因为前面往s前面增加了一个空格让s的长度增加了1所以此时的1就是原本的0
class Solution {public boolean wordBreak(String s, ListString wordDict) {SetString hashnew HashSet(wordDict);int ns.length();boolean[] dpnew boolean[n1];dp[0]true;s s;for(int i1;in1;i){for(int ji;j1;j--){if(dp[j-1]hash.contains(s.substring(j,i1))){dp[i]true;break;}}}return dp[n];}
}
8.环绕字符串中唯一的子字符串
题目链接467. 环绕字符串中唯一的子字符串 - 力扣LeetCode 题目解析计算并返回字符串s中有多少非空不同子串在base中出现
算法讲解动态规划
1.状态表示经验题目要求
因为题目要求返回字符串s中有多少非空不同子串在base中出现根据经验可以这样定义状态表示
dp[i]表示以i位置元素结尾的非空不同子串中有多少个在base中出现
2.状态转移方程
因为我们要在字符串s中找子串所以此时以i位置字符结尾的子串会有两种情况分别是长度为1和长度大于1的情况如下图 所以此时推算dp[i]时也要分为两种情况
第一种情况子串的长度为1
当子串为1时也就是ch[i]单独一个字符作为子串此时是一定会在base中出现的所以此时dp[i]1
第二种情况子串的长度大于1
当子串的长度大于1时如果要计算dp[i]就要先知道以i-1位置为结尾的非空子串有多少个出现在base中根据dp[i]的状态表示可以dp[i-1]来表示
那如何判断以i位置为结尾的非空子串是出现在base中的呢
此时无非就两种情况当ch[i]和ch[i-1]在26个小写的英文中是相邻的也就是ch[i-1]1ch[i]因为base是连续字符串所以还要考虑ch[i-1]z和ch[i]a的情况当这两种情况有一种符合时就代表在base中出现
3.初始化
此时可以先将dp表中的全部数据初始化为1因为此时的最坏情况就是1这样还有一个好处就是写代码时就不用考虑dp[i]1的情况了
4.填表顺序
从左往右填dp表即可
5.返回值
注意返回时是要求不同子串的个数所以还要去重
以saca为例当i等于0时此时子串就是a此时dp[0]1当i等于3时此时子串的情况就有aca和aca的情况此时计算dp[3]时有计算了一次子串为a的情况所以此时要去重
去重策略
根据上面的分析aca的情况就已经包含了a的情况所以在计算ret时相同字符结尾的dp值去最大的那一个即可
如何实现去重策略
定义一个大小为26的int数组遍历dp表将相同字符结尾的dp值中较大的放进数组即可
代码实现
class Solution {public int findSubstringInWraproundString(String s) {char[] chs.toCharArray();int nch.length;int[] dpnew int[n];for(int i0;in;i) dp[i]1;for(int i1;in;i){if(ch[i-1]1ch[i] || ch[i-1]zch[i]a){dp[i]dp[i-1];}}//去重int[] hashnew int[26];for(int i0;in;i)hash[ch[i]-a]Math.max(hash[ch[i]-a],dp[i]);//计算返回结果int ret0;for(int i0;i26;i)rethash[i];return ret;}
}
