天津专业网站建设公司,网站设计网站建设网站制作,做婚姻网站流程,anwsion wordpress目录978. 最长湍流子数组题目思路分析以及代码1052. 爱生气的书店老板题目思考分析与初步代码优化思路以及优化代码1208. 尽可能使字符串相等题目思考分析以及代码978. 最长湍流子数组
https://leetcode-cn.com/problems/longest-turbulent-subarray/
题目
当 A 的子数组 A[… 目录978. 最长湍流子数组题目思路分析以及代码1052. 爱生气的书店老板题目思考分析与初步代码优化思路以及优化代码1208. 尽可能使字符串相等题目思考分析以及代码 978. 最长湍流子数组
https://leetcode-cn.com/problems/longest-turbulent-subarray/
题目
当 A 的子数组 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]。 也就是说如果比较符号在子数组中的每个相邻元素对之间翻转则该子数组是湍流子数组。
返回 A 的最大湍流子数组的长度。
示例1 输入[9,4,2,10,7,8,8,1,9] 输出5 解释(A[1] A[2] A[3] A[4] A[5]) 示例2 输入[4,8,12,16] 输出2 示例 3 输入[100] 输出1 提示 1 A.length 40000 0 A[i] 10^9
思路分析以及代码
这一题是典型的滑动窗口问题。 我的大致思路如下 1、获取差分数组 2、从左到右比对差分数组观察相邻两个元素是否异号(一个大于0 一个小于0或者相反) 3、如果异号说明符合条件更新窗口值右边界继续扩展 4、否则说明当前[left,right)中都不符合条件,需要直接将左边界更新到原有的右边界。 5、意外情况下面有几种意外情况我是特殊处理的 1、原数组小于等于1直接返回数组大小 2、如果差分数组中全部都是0此时返回1 class Solution {
public:int juge(int a , int b){if((a 0 b 0) || (a 0 b 0)) return true;else return false;}int maxTurbulenceSize(vectorint arr) {if(arr.size() 1) return arr.size();int n arr.size();vectorint diff(n - 1);for(int i 0; i n - 1; i){diff[i] arr[i1] - arr[i];}int left 0 ,right 1;int max_window_size 1;int zero_diff_times 0;if(diff[0] 0) zero_diff_times;while(right diff.size()){if(juge(diff[right],diff[right - 1])){max_window_size max(max_window_size,right - left 1);}else{if(diff[right] 0) zero_diff_times;left right;}right;}if(zero_diff_times diff.size()) return 1;return max_window_size1;}
};1052. 爱生气的书店老板
https://leetcode-cn.com/problems/grumpy-bookstore-owner/
题目
今天书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客customers[i]会进入书店所有这些顾客都会在那一分钟结束后离开。
在某些时候书店老板会生气。 如果书店老板在第 i 分钟生气那么 grumpy[i] 1否则 grumpy[i] 0。 当书店老板生气时那一分钟的顾客就会不满意不生气则他们是满意的。
书店老板知道一个秘密技巧能抑制自己的情绪可以让自己连续 X 分钟不生气但却只能使用一次。
请你返回这一天营业下来最多有多少客户能够感到满意的数量。 示例 输入customers [1,0,1,2,1,1,7,5], grumpy [0,1,0,1,0,1,0,1], X 3 输出16 解释 书店老板在最后 3 分钟保持冷静。 感到满意的最大客户数量 1 1 1 1 7 5 16. 提示 1 X customers.length grumpy.length 20000 0 customers[i] 1000 0 grumpy[i] 1 思考分析与初步代码
初步思路 1、从第一个时间段开始遍历遍历每个窗口长度为X的时间段并且计算这个时间段内老板生气的时间顾客来的人数。 2、依次遍历完整个时间段找到时间段内老板生气的时间顾客来的人数最多的人数。 3、最后再遍历一遍原数组记录下老板不生气时候来的总人数 4、两个结果相加得到最终结果。
class Solution {
public:int maxSatisfied(vectorint customers, vectorint grumpy, int X) {int max_sum_start 0;int max_sum 0;for(int start 0; start customers.size() - X 1; start){int sum 0;for(int i start; i start X ; i ){if(grumpy[i] 1) sum customers[i];}if(sum max_sum){max_sum sum;max_sum_start start;}}//cout max_sum max_sum endl;int result 0;for(int i 0; i customers.size(); i){if(grumpy[i] 0) resultcustomers[i];}return resultmax_sum;}
};很显然时间复杂度是O(N * X)
优化思路以及优化代码
关于长度固定的滑动窗口有一点我们要熟悉的是窗口每次滑动时变化的只有头尾两个元素所以我们只针对这两个元素进行处理就行。 不过对于第一个窗口需要特殊对待需要先进行填充。 接下来的窗口中如果新进来的时间是生气的加上顾客量。如果新出去的时间是生气的那么减去顾客量。每次滑动都需要更新最大值。
class Solution {
public:int maxSatisfied(vectorint customers, vectorint grumpy, int X) {int sum 0;//计算不生气时来的顾客总数for(int i 0; i customers.size(); i){if(grumpy[i] 0) sumcustomers[i];}int left 0, right 0;//第一个区域while(right X){if(grumpy[right] 1) sum customers[right];right;}int max_sum sum;while(right customers.size()){//生气的时间段被移除窗口总顾客减少if(grumpy[left] 1) sum - customers[left];//生气的时间段被移入窗口总顾客增加if(grumpy[right] 1) sum customers[right];max_sum max(max_sum,sum);left;right;}return max_sum;}
};1208. 尽可能使字符串相等
题目
给你两个长度相同的字符串s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销开销可能为 0也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时总开销应当小于等于该预算这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串则返回 0。
示例 1 输入s “abcd”, t “bcdf”, cost 3 输出3 解释s 中的 “abc” 可以变为 “bcd”。开销为 3所以最大长度为 3。 示例 2 输入s “abcd”, t “cdef”, cost 3 输出1 解释s 中的任一字符要想变成 t 中对应的字符其开销都是 2。因此最大长度为 1。 示例 3 输入s “abcd”, t “acde”, cost 0 输出1 解释你无法作出任何改动所以最大长度为 1。 提示 1 s.length, t.length 10^5 0 maxCost 10^6 s 和 t 都只含小写英文字母。 思考分析以及代码
这一题是一个非常典型的滑动窗口题。 1、首先我们构建差分绝对值数组
vectorint diff(s.size());
for(int i 0; i diff.size(); i)
{diff[i] abs(s[i] - t[i]);
}2、然后我们建立滑动窗口的左右边界在差分数组上移动 3、什么时候扩展窗口 当我们现在存有的cost - 右边新纳入的cost 0 的时候我们可以继续扩展窗口 4、反之如果小于0说明不能继续扩展了。但是由于我们求的是最大窗口长度所以此时也不需要缩小窗口只需要将整个窗口平移即可。记住平移的时候要将新移除的cost加到当前cost上算是弥补损失。 5、更新窗口最大长度的操作必然是在扩展窗口的时候啦 这一题思路应该还是比较清晰的。当然也有个地方有点不好搞那就是第三点是0 还是 0.如果有时间的话可以自己手动推导一下如果没有就两个都试一下选择答案正确的即可.
class Solution {
public:int equalSubstring(string s, string t, int maxCost) {//构建相差数组vectorint diff(s.size());for(int i 0; i diff.size(); i){diff[i] abs(s[i] - t[i]);}int left 0, right 0;int max_length 0;while(right diff.size()){//扩大窗口int new_In diff[right];maxCost maxCost - new_In;if(maxCost 0){max_length max(max_length,right -left 1);}else{int new_Out diff[left];maxCost new_Out;left;}right;}return max_length;}
};
