四川建设主管部门网站,网站建设思路设计,什么是网站开发类课程,自己动手建设公司门户网站子数组系列 1. 环形⼦数组的最⼤和2. 乘积最大子数组3. 等差数列划分4. 最长湍流子数组5. 单词拆分6. 环绕字符串中唯⼀的子字符串 1. 环形⼦数组的最⼤和
1.题目链接#xff1a;环形⼦数组的最⼤和 2.题目描述#xff1a;给定一个长度为 n 的环形整数数组 nums #xff0c… 子数组系列 1. 环形⼦数组的最⼤和2. 乘积最大子数组3. 等差数列划分4. 最长湍流子数组5. 单词拆分6. 环绕字符串中唯⼀的子字符串 1. 环形⼦数组的最⼤和
1.题目链接环形⼦数组的最⼤和 2.题目描述给定一个长度为 n 的环形整数数组 nums 返回 nums 的非空 子数组 的最大可能和 。 环形数组 意味着数组的末端将会与开头相连呈环状。形式上 nums[i] 的下一个元素是 nums[(i 1) % n] nums[i] 的前一个元素是 nums[(i - 1 n) % n] 。 子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上对于子数组 nums[i], nums[i 1], …, nums[j] 不存在 i k1, k2 j 其中 k1 % n k2 % n 。
示例 1 输入nums [1,-2,3,-2] 输出3 解释从子数组 [3] 得到最大和 3 示例 2 输入nums [5,-3,5] 输出10 解释从子数组 [5,5] 得到最大和 5 5 10 示例 3 输入nums [3,-2,2,-3] 输出3 解释从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3 提示 n nums.length 1 n 3 * 10^4 -3 * 10^4 nums[i] 3 * 10^4 3.问题分析这道题对于一个数组来说逻辑上首尾是相连的求子数组的最大和直接求肯定是求不出来的还记得清上篇多状态中有道打家劫舍II也是对于环形数组求解那道题中一个房子如果偷的话那么相邻的房子就不能再偷我们对首尾进行详细分析对[0, n - 2]和[1, n - 1]区间分别进行操作这道题和那道题没关系哈提出来只是让大家回忆一下接下来就是这道题的思路说难也不难但是确实不好太想到首先会有两种结果1. 结果在数组的内部包括整个数组2. 结果在数组⾸尾相连的⼀部分上。整个数组的总和sum是不变的如果结果在数组⾸尾相连的⼀部分上那么数组中间就会空出来一部分选不上中间没选上的数组和就是子数组和的最小值所以这道题求一个最大子数组和与一个最小子数组和然后用sum减去最小子数组和与所求最大子数组和作比较返回最大的那一个即可。
状态表示f[i] 表⽰以 i 做结尾的所有⼦数组中和的最大值g[i] 表⽰以 i 做结尾的所有⼦数组中和的最⼩值。状态转移方程f[i] 的所有可能可以分为以下两种1.⼦数组的⻓度为 1 此时 f[i] nums[i] 2.⼦数组的⻓度⼤于 1 此时 f[i] 应该等于 以 i - 1 做结尾的所有⼦数组中和的最⼤值再加上 nums[i] 也就是 f[i - 1] nums[i] 。由于要的是最⼤值因此应该是两种情况下的最⼤值因此可得转移⽅程f[i] max(nums[i], f[i - 1] nums[i])g[i]的分析与f[i]基本相同可得g[i]的状态转移方程为g[i] min(nums[i], g[i - 1] nums[i])。初始化要求f[i]那么就需要知道f[i - 1]的值所以只需要处理i - 1越界这种情况通常增加一个辅助结点即可增加辅助结点后要记得nums[i - 1]要减1 初始化为 f[0] g[0] 0 。填表顺序从左往右。返回值找出f[i]中最大g[i]中最小用sum - min(g[i])返回减去的值和f[i]中的最大值。有个特殊情况就是当相减的数为0即数组中的数全为负数此时应该返回f[i]中的最大值否则就返回减去的值和f[i]中的最大值。
4.代码如下
class Solution
{
public:int maxSubarraySumCircular(vectorint nums) {int n nums.size();vectorint f(n 1), g(n 1);int sum 0;int fmax INT_MIN; //f数组中的最大值int gmin INT_MAX; //g数组中的最小值for (int i 1; i n; i){f[i] max(f[i - 1] nums[i - 1], nums[i - 1]);fmax max(fmax, f[i]);g[i] min(g[i - 1] nums[i - 1], nums[i - 1]);gmin min(gmin, g[i]);sum nums[i - 1];}gmin sum - gmin;return gmin 0 ? fmax : max(fmax, gmin);}
};2. 乘积最大子数组
1.题目链接添加链接描述 2.题目描述给你一个整数数组 nums 请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。 测试用例的答案是一个 32位 整数。 子数组 是数组的连续子序列。
示例 1: 输入: nums [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例 2: 输入: nums [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 提示: 1 nums.length 2 * 10^4 -10 nums[i] 10 nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数 3.问题分析如果用一个dp表来表示乘积最大的子数组就会发现当出现负数时一个dp表是不能表示出来的负数乘负数可能会是最大的乘积。所以可以用两个dp表来表示一个表为f表示前i个元素子数组乘积的最大值另一个表为g表示前i个元素中子数组乘积的最小值。
状态表示如上所述f表表示前i个元素子数组乘积的最大值g表表示前i个元素中子数组乘积的最小值。状态转移方程对于 f[i] 也就是「以 i 为结尾的所有⼦数组的最⼤乘积」对于所有⼦数组可以分为下⾯三种形式 1.⼦数组的⻓度为 1 也就是 nums[i] 2.⼦数组的⻓度⼤于 1 但 nums[i] 0 此时需要的是 i - 1 为结尾的所有⼦数组的最⼤乘积 f[i - 1] 再乘上 nums[i] 也就是 nums[i] * f[i - 1] 3.⼦数组的⻓度⼤于 1 但 nums[i] 0 此时需要的是 i - 1 为结尾的所有⼦数组的最⼩乘积 g[i - 1] 再乘上 nums[i] 也就是 nums[i] * g[i - 1] 综上所述 f[i] max(nums[i], max(nums[i] * f[i - 1], nums[i] * g[i - 1]) )。 对于 g[i] 也就是以 i 为结尾的所有⼦数组的最⼩乘积分析结果如同f[i]。初始化要求 i 结尾的需要知道i - 1位置的值所以可以增加一个辅助结点求的是乘积的结果所以f[0] 1; g[0] 1。填表顺序从左往右。返回值返回f表中最大的元素。
4.代码如下
class Solution
{
public:int maxProduct(vectorint nums) {int n nums.size();vectorint f(n 1), g(n 1);f[0] g[0] 1;int ret INT_MIN;for (int i 1; i n; i){int x nums[i - 1], y f[i - 1] * nums[i - 1], z g[i - 1] * nums[i - 1];f[i] max(x, max(y, z));g[i] min(x, min(y, z));ret max(ret, f[i]);}return ret;}
};3. 等差数列划分
1.题目链接等差数列划分 2.题目描述 如果一个数列 至少有三个元素 并且任意两个相邻元素之差相同则称该数列为等差数列。 例如[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。 给你一个整数数组 nums 返回数组 nums 中所有为等差数组的 子数组个数。 子数组 是数组中的一个连续序列。 3.算法流程
状态表示 这道题以某一个位置为结尾进行分析如图1dp[i] 表示以 i 位置的元素为结尾的等差数列有多少种。状态转移方程 1.如图2假设上述4个位置构成等差数列红线1表示以i-1为结尾的等差数列的数量将红线1向后移动一格那么这条红线是不是就可以代表以i为结尾的等差数列但是刚好少了黑线2这种情况所以以i为结尾的等差数列个数等于(红线1)以i-1为结尾的等差数列个数1黑线2这种多出来的情况即dp[i] dp[i - 1] 1(如果是等差数列的话)。 2.如果以i为结尾的元素不构成等差数列那么这个位置的dp[i]0因为dp表示以i位置的元素为结尾的等差数列的个数。 之后将以所有元素为结尾的等差数列加起来即为所求。初始化 前两个位置的元素⽆法构成等差数列因此 dp[0] dp[1] 0 。填表顺序从左往右。返回值要求的是所有的等差数列的个数因此需要返回整个 dp 表⾥⾯的元素之和。
4.代码如下
class Solution
{
public:int numberOfArithmeticSlices(vectorint nums) {int n nums.size();vectorint dp(n);int ret 0;for (int i 2; i n; i){if ((nums[i] - nums[i-1]) (nums[i-1] - nums[i-2]))dp[i] dp[i-1] 1;ret dp[i];}return ret;}
};4. 最长湍流子数组
1.题目链接最长湍流子数组 2.题目描述给定一个整数数组 arr 返回 arr 的 最大湍流子数组的长度 。 如果比较符号在子数组中的每个相邻元素对之间翻转则该子数组是 湍流子数组 。 更正式地来说当 arr 的子数组 A[i], A[i1], …, A[j] 满足仅满足下列条件时我们称其为湍流子数组 若 i k j 当 k 为奇数时 A[k] A[k1]且当 k 为偶数时A[k] A[k1] 或 若 i k j 当 k 为偶数时A[k] A[k1] 且当 k 为奇数时 A[k] A[k1]。
示例 1 输入arr [9,4,2,10,7,8,8,1,9] 输出5 解释arr[1] arr[2] arr[3] arr[4] arr[5] 示例 2 输入arr [4,8,12,16] 输出2 示例 3 输入arr [100] 输出1 3.问题分析这道题需要找最长交错的子数组交错就是 i 位置的比 i - 1 的值要大小i 1位置的比 i 位置要小大可以说要求交错的最长子数组。首先想用一个dp表来解决会发现数组中的值一会比前一个大一会又比前一个小用一个dp表表示不了再用两个dp表来试试数组中的元素一会大一会小那么就用f[i]来表示 i 位置的元素比 i - 1 中的元素大所存的最长子数组用g[i]来表示 i 位置的元素比 i - 1 中的元素小所存的最长子数组这样表示这道题就会很容易求出来。
状态表示f[i]来表示 i 位置的元素比 i - 1 中的元素大所存的最长子数组用g[i]来表示 i 位置的元素比 i - 1 中的元素小所存的最长子数组。状态转移方程1.arr[i] arr[i - 1] 如果 i 位置的元素⽐ i - 1 位置的元素⼤说明接下来应该去找 i -1 位置结尾并且 i - 1 位置元素⽐前⼀个元素⼩的序列那就是 g[i - 1] 。更新 f[i] 位置的值 f[i] g[i - 1] 1 2.arr[i] arr[i - 1] 如果 i 位置的元素⽐ i - 1 位置的元素⼩说明接下来应该去找 i - 1 位置结尾并且 i - 1 位置元素⽐前⼀个元素⼤的序列那就是f[i - 1] 。更新 g[i] 位置的值 g[i] f[i - 1] 1 arr[i] arr[i - 1] 不构成湍流数组。初始化两个dp表中所有的值可以初始化为1.因为最短的长度为1然后从 i 1开始遍历i - 1 0dp表是不会越界的所以这道题就不用增加辅助结点。填表顺序从左往右依次填写。返回值返回两个dp表中的最大值。
4.代码如下
class Solution
{
public:int maxTurbulenceSize(vectorint arr) {int n arr.size();vectorint f(n, 1), g(n, 1);int ret 1;for (int i 1; i n; i){if (arr[i] arr[i - 1])f[i] g[i - 1] 1;else if (arr[i] arr[i - 1])g[i] f[i - 1] 1;ret max(ret, max(f[i], g[i]));}return ret;}
};5. 单词拆分
1.题目链接单词拆分 2.题目描述给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
示例 1 输入: s “leetcode”, wordDict [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。 示例 2 输入: s “applepenapple”, wordDict [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。 注意你可以重复使用字典中的单词。 示例 3 输入: s “catsandog”, wordDict [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false 提示 1 s.length 300 1 wordDict.length 1000 1 wordDict[i].length 20 s 和 wordDict[i] 仅由小写英文字母组成 wordDict 中的所有字符串互不相同 3.问题分析要利用字典中出现的单词拼接出 s 那么就可以认为从s中的0位置拿一个子数组与字典中的元素匹配然后再向后拿一个子数组匹配如果s中的每个子数组都可以在字典中找到那么可以利用字典中出现的单词拼接出 s 。
状态标识dp[i] 表⽰ [0, i] 区间内的字符串能否被字典中的单词拼接⽽成。状态转移方程对于 dp[i] 为了确定当前的字符串能否由字典⾥⾯的单词构成根据最后⼀个单词的起始位置 j 可以将其分解为前后两部分 前⾯⼀部分 [0, j - 1] 区间的字符串 后⾯⼀部分 [j, i] 区间的字符串。其中前⾯部分我们可以在 dp[j - 1] 中找到答案后⾯部分的⼦串可以在字典⾥⾯找到。因此 当dp[j - 1] true并且后⾯部分的⼦串 s.substr(j, i - j 1) 能够在字典中找到那么 dp[i] true 。初始化增加一个辅助结点dp[0]表示0个字符能否被拼接而成0个字符串也就是空串所以dp[0] true因为增加了一个辅助结点所以遍历s是要减1 。填表顺序从左往右返回值返回 dp[n] 位置的布尔值。 4.代码如下
class Solution
{
public:bool wordBreak(string s, vectorstring wordDict){//将字典⾥⾯的单词存在哈希表⾥⾯unordered_setstring hash;for (auto s : wordDict) hash.insert(s);int n s.size();vectorbool dp(n 1);dp[0] true; // 保证后续填表是正确的for (int i 1; i n; i) // 填 dp[i]{for (int j i; j 1; j--) //最后⼀个单词的起始位置{if (dp[j - 1] hash.count(s.substr(j - 1, i - j 1))) //添加辅助结点对应的位置为j - 1{dp[i] true;break;}}}return dp[n];}
};6. 环绕字符串中唯⼀的子字符串
1.题目链接环绕字符串中唯⼀的子字符串 2.问题描述 定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串所以 base 看起来是这样的 “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”. 给你一个字符串 s 请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
示例 1 输入s “a” 输出1 解释字符串 s 的子字符串 “a” 在 base 中出现。 示例 2 输入s “cac” 输出2 解释字符串 s 有两个子字符串 (“a”, “c”) 在 base 中出现。 示例 3 输入s “zab” 输出6 解释字符串 s 有六个子字符串 (“z”, “a”, “b”, “za”, “ab”, and “zab”) 在 base 中出现。 提示 1 s.length 10^5 s 由小写英文字母组成 3.问题分析这道题其实可以说寻找递增子数组的个数比如如果只有a到y并且元素不重复用一个dp表i 位置表示的是以 i 结尾子数组的个数将每块相连的递增子数组个数相加即将dp表中的元素求和现在再加一个z并且z到a可以看作是连接的那么就加个if语句将这种情况判断一下即可然后再加一个条件元素可以重复但是题中所求子数组是不能重复dp表是的是以i为结尾子数组的个数比如aababc(“a”,“b”,“c”,“ab”,“bc”,“abc”)对于后面的abc来说已经包含前面的ab了所以只用求出以某个结尾的最大子数组的个数用一个哈希数组可以来解决如果s[i]的元素一样那么就保留dp[i]中的最大值。
状态表示dp[i] 表⽰以 i 位置的元素为结尾的所有⼦串⾥⾯有多少个在 base 中出现过。状态转移方程就是寻找递增子数组的个数如等差数列划分即dp[i] dp[i - 1] 1(如果是等差数列的话)。初始化这道题的长度可以为1而等差序列划分最少要为3所以将dp表都初始化为1.填表顺序从左往右。返回值返回哈希数组中元素的和。
代码如下
class Solution
{
public:int findSubstringInWraproundString(string s){int n s.size();// 1. 利⽤ dp 求出每个位置结尾的最⻓连续⼦数组的⻓度vectorint dp(n, 1);for (int i 1; i n; i)if (s[i] - 1 s[i - 1] || (s[i - 1] z s[i] a))dp[i] dp[i - 1] 1;// 2. 计算每⼀个字符结尾的最⻓连续⼦数组的⻓度int hash[26] { 0 };for (int i 0; i n; i)hash[s[i] - a] max(hash[s[i] - a], dp[i]);// 3. 将结果累加起来int sum 0;for (auto x : hash) sum x;return sum;}
};
