陌上香坊是做盗版的网站吗,网站建设运营,乐清市网站建设哪家性价比高,赣州快车公众号文章目录 35.最大子数组和35.1题目35.2解法#xff1a;动规35.2.1动规思路35.2.2代码实现 36.判断子序列36.1题目36.2解法#xff1a;动规36.2.1动规思路36.2.2代码实现 37.不同的子序列37.1题目37.2解法#xff1a;动规37.2.1动规思路37.2.2代码实现 35.最大子数组和
35.1… 文章目录 35.最大子数组和35.1题目35.2解法动规35.2.1动规思路35.2.2代码实现 36.判断子序列36.1题目36.2解法动规36.2.1动规思路36.2.2代码实现 37.不同的子序列37.1题目37.2解法动规37.2.1动规思路37.2.2代码实现 35.最大子数组和
35.1题目
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组
是数组中的一个连续部分。
示例一
输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6 示例二
输入nums [1]
输出135.2解法动规
35.2.1动规思路 确定dp数组以及下标含义 dp[i]下标为i的子数组的最大子数组和为dp[i] 确定递推公式dp[i]Math.max( dp[i-1]nums[i]nums[i]) dp数组初始化dp[0]Math.max(0,nums[i]) 确定遍历顺序从前往后 举例推导
35.2.2代码实现 public int maxSubArray(int[] nums) {int[] dpnew int[nums.length];int resultnums[0];dp[0]nums[0];for(int i1;inums.length;i){dp[i]Math.max(dp[i-1]nums[i],nums[i]);resultMath.max(result,dp[i]);}return result;}36.判断子序列
36.1题目
给定字符串 s 和 t 判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。
进阶
如果有大量输入的 S称作 S1, S2, … , Sk 其中 k 10亿你需要依次检查它们是否为 T 的子序列。在这种情况下你会怎样改变代码
示例一
输入s abc, t ahbgdc
输出true示例二
输入s axc, t ahbgdc
输出false36.2解法动规
36.2.1动规思路 确定dp数组以及下标含义: dp(i)(j)表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同的子序列的长度为dp(i)(j) 确定递推公式 2.1 s[i-1]t[j-1]t中找到了一个字符在s中也出现即dp(i)(j)dp(i-1)(j-1)1 2.2 s[i-1]!t[j-1]t下标j-1位置的字符和s下标i-1位置的字符不同即dp(i)(j)dp(i)(j-1) dp数组初始化dp(i)(0)和dp(0)(j)位置的元素没有意义 确定遍历顺序从上到下 举例推导
36.2.2代码实现 public boolean isSubsequence(String s, String t) {int[][] dpnew int[s.length()1][t.length()1];for(int i1;is.length();i){for(int j1;jt.length();j){if(s.charAt(i-1)t.charAt(j-1)){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]dp[i][j-1];}}}return dp[s.length()][t.length()]s.length();}37.不同的子序列
37.1题目
给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数结果需要对 109 7 取模。
示例一
输入s rabbbit, t rabbit
输出3
解释
如下所示, 有 3 种可以从 s 中得到 rabbit 的方案。
rabbbit
rabbbit
rabbbit示例二
输入s babgbag, t bag
输出5
解释
如下所示, 有 5 种可以从 s 中得到 bag 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag37.2解法动规
37.2.1动规思路 求解求子序列s组装成t的几种方法 确定dp数组以及下标含义 dp(i)(j)以下标i-1为结尾的s子序列中 出现 以下标j-1为结尾的t子序列的个数 为dp(i)(j) 确定递推公式 3.1 s[i-1]j[j-1]两种情况取s[i-1]或不取即dp(i)(j)dp(i-1)(j-1)dp(i-1)(j) 3.2 s[i-1]![j-1]只能不取s[i-1]即dp(i)(j)dp(i-1)(j) dp数组初始化 dp(i)(0)子序列s组装成空串的方法肯定有一种 dp(0)(j)无意义 确定遍历顺序从上到下 举例推导
37.2.2代码实现 public int numDistinct(String s, String t) {int[][] dpnew int[s.length()1][t.length()1];//初始化for(int i0;is.length();i){dp[i][0]1;}for(int i1;is.length();i){for(int j1;jt.length();j){if(s.charAt(i-1)t.charAt(j-1)){//两种情况取/不取dp[i][j]dp[i-1][j-1]dp[i-1][j];}else{dp[i][j]dp[i-1][j];}}}return dp[s.length()][t.length()];}
