七月集训

七月集训

目录

题目一：子数组最大平均数 I

解题思路：

 代码：

题目二：718. 最长重复子数组

问题思路：

代码：

题目三：978. 最长湍流子数组

求解思路：

代码

题目一：子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

解题思路：

设置一个长度为K的“窗口”，不断移动窗口，每次滑动窗口时，计算窗口此时的平均值，直到窗口的右边界为数组的最后一个元素。

需要注意的是结果的数据类型需要为精度更高的double型数据，不然仅仅用float会导致精度不够会导致答案错误。

 代码：

double findMaxAverage(int* nums, int numsSize, int k){int i = 0;double sum = 0;for(i=0; i<k; i++){sum = nums[i] + sum;}double max = sum / k;  //记录数组前k个值的平均数double ave;              //记录每次滑动窗口的平均值for(i=k; i<numsSize; i++){sum = sum + nums[i];   //新增的值sum = sum - nums[i-k]; //需要减去的值ave = sum / k;if(ave >= max)max = ave;}return max;
}

题目二：718. 最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 

问题思路：

代码是看题解的，自己试了数才知道大概是什么意思，思路先空着，有了更深的理解再将思路补上。

代码：

int Find(int *a, int * b, int addA, int addB, int len)
{int ret = 0;int k = 0;for(int i=0; i<len; i++){if(a[i + addA] == b[i + addB])k++;elsek = 0;ret = fmax(ret, k);}return ret;
}int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size){int i;int ret = 0;for(i=0; i< nums1Size; i++)   //{int len = fmin(nums2Size, nums1Size-i);int maxlen = Find(nums1, nums2, i, 0, len);ret = fmax(maxlen, ret);}for(i=0; i< nums2Size; i++){int len = fmin(nums1Size, nums2Size-i);int maxlen = Find(nums1, nums2, 0, i, len);ret = fmax(maxlen, ret);}return ret;}

题目三：978. 最长湍流子数组

问题描述：

给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。

如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。

更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：

若 i <= k < j ：
当 k 为奇数时， A[k] > A[k+1]，且
当 k 为偶数时，A[k] < A[k+1]；
或 若 i <= k < j ：
当 k 为偶数时，A[k] > A[k+1] ，且
当 k 为奇数时， A[k] < A[k+1]。
 

求解思路：

参考星主的办法，设立两个数组，aec以及dec ，分别代表最后两个元素是递增或递减的最长序列。

当arr[i] > arr[i-1]时，有aec[i] = dec[i-1] + 1；

当arr[i] < arr[i-1]时，有dec[i] = aec[i-1] + 1;

遍历数组内的所有元素，通过if语句判断，求出每个位置的aec[i]或者dec[i]的值，将其与当前的最大值比较，更大就替换。

这个规律 可以通过试数的方式，当代码不知道什么意思或者不知道有什么规律的时候，试数是一个很好的办法，多试几个数，就有大概的思路了

代码

int maxTurbulenceSize(int* arr, int arrSize){int ans = 0;int aec[40010];int dec[40010];for(int i=0; i<arrSize; i++){aec[i] = dec[i] = 1;if(i){if(arr[i] > arr[i-1]){aec[i] = dec[i-1]+ 1;}if(arr[i] < arr[i-1]){dec[i] = aec[i-1]+ 1;}}ans = fmax(ans, fmax(aec[i], dec[i]));}return ans;
}