LeetCode
滑动窗口算法
LeetCode第1176题：
你的好友是一位健身爱好者。前段日子，他给自己制定了一份健身计划。现在想请你帮他评估一下这份计划是否合理。 他会有一份计划消耗的卡路里表，其中 calories[i] 给出了你的这位好友在第 i 天需要消耗的卡路里总量。 为了更好地评估这份计划，对于卡路里表中的每一天，你都需要计算他 「这一天以及之后的连续几天」 （共 k 天）内消耗的总卡路里 T： 如果 T < lower，那么这份计划相对糟糕，并失去 1 分； 如果 T > upper，那么这份计划相对优秀，并获得 1 分； 否则，这份计划普普通通，分值不做变动。 请返回统计完所有 calories.length 天后得到的总分作为评估结果。 注意：总分可能是负数。
示例一
输入：calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3 输出：0 解释：calories[0], calories[1] < lower 而 calories[3], calories[4] > upper, 总分 = 0.
示例二
输入：calories = [3,2], k = 2, lower = 0, upper = 1 输出：1 解释：calories[0] + calories[1] > upper, 总分 = 1.
示例三
输入：calories = [6,5,0,0], k = 2, lower = 1, upper = 5 输出：0 解释：calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, 总分 = 0.
看完这个题目基本上明白题意了，看了一下题目的评论，才知道这是滑动窗口算法。再百度一下滑动窗口算法。发现有一篇文章讲的很清楚。
https://blog.csdn.net/sty945/article/details/79846516
其中提到对于这个算法有一个很经典的题：给定一个大小为n的整形数组，计算长度为k的子数组的最大值。例如：
{1，2，3，4，5，6} //有这样一个数组，求长度为3的子数组之和最大为多少 //对于这个数组来说数组之和最大并且长度为3的子数组肯定就是{4，5，6} //那么用代码实现的过程就是滑动窗口算法实现的过程
代码：
int maxSum(int arr[], int n, int k) //arr为原数组{1,2,3,4,5,6}，n为数组长度，k为子数组长度 { if (n < k)//如果原数组为{1,2}长度n=2;求长度k=3的子数组没有意义。 { cout << "Invaild"; return -1; } int max_sum = 0; for (int i=0; i<k; i++)//先求第一个窗格的和 { max_sum += arr[i]; } int windows_sum = max_sum;//max_sum=6 for (int i=k; i<n; i++)//往下求后面的窗格 { /* i=k=3 windows_sum=windows_sum+arr[3]-arr[0]=6+4-1=9 {2,3,4}=9; 相当于向后移动求和 */ windows_sum += arr[i] - arr[i - k]; max_sum = max(max_sum, windows_sum); } return max_sum; }
那么对于上面健身的题也是一样的道理，只是多了几个比较再加一个分数。
代码：
class Solution { public int dietPlanPerformance(int[] calories, int k, int lower, int upper) { if(calories.length<k)//如果数组长度小于k没有意义 { return 0; } int ans=0; int sum=0; for(int i=0;i<k;i++){//先求第一个窗格 sum+=calories[i]; } if(sum<lower){ans--;}//做判断定分数 if(sum>upper){ans++;} for(int i=k;i<calories.length;i++){//求后面的窗格 sum+=calories[i]-calories[i-k]; if(sum<lower){ans--;}//再来判断分数 if(sum>upper){ans++;} } return ans;//返回分数 } }
LeetCode第26题：删除排序数组中重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例
给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超出新长度后面的元素。
这道题现在想起来不难，但是第一次看见还是卡在那里,直接看官方的代码
代码：
public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int i = 0; for (int j = 1; j < nums.length; j++) { if (nums[j] != nums[i]) { i++; nums[i] = nums[j]; } } return i + 1; }
官方讲解
数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要 nums[i] = nums[j]，我们就增加 j 以跳过重复项。 当我们遇到 nums[j]!=nums[i]时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]）的值复制到 nums[i+1]。 然后递增i，接着我们将再次重复相同的过程，直到 j 到达数组的末尾为止。
