网站开发 发布,找人做自建房图纸去哪个网站,有哪些做问卷调查的网站,类似于建设通的网站公司里偷偷刷题记录
做一下笔记
求解子数组方式#xff1a; 两种方案#xff1a; 通用方案就是前缀和查找 另一种是递增序列可用的滑动窗口
有些题目如果给出来的数字有正#xff0c;负。那么一定就要转化成前缀和。 如果是全正数组#xff0c;可以采用前缀和二分查找的…公司里偷偷刷题记录
做一下笔记
求解子数组方式 两种方案 通用方案就是前缀和查找 另一种是递增序列可用的滑动窗口
有些题目如果给出来的数字有正负。那么一定就要转化成前缀和。 如果是全正数组可以采用前缀和二分查找的方式。但是这个效率似乎没有滑动窗口高不知道是不是leetcode数据量的问题没有专门压测评估过。
习题解答
leetcode713 题目https://leetcode.cn/problems/subarray-product-less-than-k/ 乘积小于 K 的子数组 C 方案采用前缀和的形式
#include iostreamusing namespace std;
class Solution {
public:int numSubarrayProductLessThanK(vectorint nums, int k) {if (k 0) {return 0;}int n nums.size();vectordouble logPrefix(n 1);for (int i 0; i n; i) {logPrefix[i 1] logPrefix[i] log(nums[i]);//cout logPrefix[i] endl;}// cout logPrefix.end() - logPrefix.begin() endl;//cout logPrefix.end() endl;double logk log(k);int res 0;//for (int j 0; j n; j) {// int mid upper_bound(logPrefix.begin(), logPrefix.begin() j 1, logPrefix[j 1] - log(k) 1e-10) - logPrefix.begin();// res j - mid 1;//}for (int j 0; j n; j) {// 定义边界int left 0;int right j 1;// 定义返回值一般是右端int mid_res j 1;// 定义特殊判断条件若有double val logPrefix[j 1] - logk 1e-10;// 二分循环 while (left right) {// 获取中点int mid (left right) / 2;// 二分判断if (logPrefix[j1] - logPrefix[mid] 1e-10 logk) {// 满足条件赋值mid_res mid;right mid; // 根据实际情况向左找} else {left mid 1; // 向右找。}}// 找到后统计这个一行是本题的关键。res j 1 - mid_res;}return res;}
};C语言采用滑动窗口
int numSubarrayProductLessThanK(int* nums, int numsSize, int k){// 乘机肯定不会小于1或者0if (k 1) {return 0;}int sum 1;int left 0;int count 0;// 滑窗时候右指针一般是快指针用循环实现// 左指针一般是慢指针通过条件判断移动for (int right 0; right numsSize; right) {sum * nums[right];while (sum k) {sum / nums[left];}// 因为都是正数所以我们可以用滑动窗口也就是快慢指针去操作// 每经过一个快指针我们可以这么统计// 既然从left累乘到right都满足元素严格小于k// 那么从left到right中的任意一个下标移动到right都可以满满足小于k// 那么不重复的统计子数组的数量就是从right - left 1count right - left 1;}return count;
}
