手机网站导航代码河南网站关键词优化

手机网站导航代码,河南网站关键词优化,wordpress简约灯箱,宁波网站建设公司排名题目链接#xff1a;3652. 按策略买卖股票的最佳时机#xff08;中等#xff09; 算法原理#xff1a; 解法一#xff1a;前缀和定长滑动窗口 14ms击败5.74% 时间复杂度O(N) ①核心思路#xff1a;max(不修改时的利润#xff0c;修改后能得到的最大利润) 以下prices[i]用…题目链接3652. 按策略买卖股票的最佳时机中等算法原理解法一前缀和定长滑动窗口14ms击败5.74%时间复杂度O(N)①核心思路max(不修改时的利润修改后能得到的最大利润)以下prices[i]用p[i]表示strategy[i]用s[i]表示②修改后能得到的最大利润通过定长滑动窗口获得因为长度为k的滑动窗口中前k/2为0后k/2为1前k/2与s数组相乘后为0故只取后k/2的利润③定义前缀和和后缀和快速获得窗口前部分和窗口后部分不修改时能获得的利润注意防止p数组和s数组索引越界访问所以定义如下//保证索引1~index long[] prevnew long[n1];//前缀和 long[] suffnew long[n2];//后缀和 //前缀和prev[i]:i之前的前缀和不包括i for(int i1;in;i) prev[i]prev[i-1]p[i-1]*s[i-1]; //后缀和suff[i]:i-1之后的后缀和包括i-1 //统一含义后缀和suff[i]:i-2之后的后缀和不包括i-2 for(int in;i1;i--) suff[i]suff[i1]p[i-1]*s[i-1];其中suff[right2] → 原数组 (right2)-1 right1 ~ n-1正好是窗口 right 号之后的元素不含窗口 right 号以防有些小伙伴看不懂索引的对应关系博主下面附上了手画图解便于理解④定长滑动窗口获得窗口内修改后能获得的利润进窗口sum累加窗口内能获得时的利润窗口后k/2部分的利润sum-前k/2部分的利润更新max不修改时的利润修改后拼接三个部分[0,left-1][left,right][right1,n-1]的利润出窗口left出窗口⑤小优化注意在统计窗口内前k/2部分利润的时候用循环计算会导致时间复杂度变成O(nk)在LeetCode会超时因此需要预处理p数组的前缀和来优化用前缀和相减的方式在O(1)的时间复杂度下快速统计解法二前缀和7ms击败44.13%时间复杂度O(N)图解如下①遍历每个i在i后面取个长度为k的区间 [i-k,i-1]不往前取是防止越界且取后面好分析利用前缀和来解②定义sum[i]p[i]*s[i]的前缀和不包括i位置定义sumsell[i]p[i]的前缀和不包括i位置那么不修改时的总利润自然为sum[n]③其余如上图解修改时取到的最大利润为三个部分的总和sum[i-k]sum[n]-sum[i]sumsell[i]-sumsell[i-k/2]④注意ret初始化为最小值Long.MIN_VALUE,因为可能出现负数LeetCode的测试用例会导致初始化为-0x3f3f3f3f也不能通过的解法三滑动窗口5ms击败89.54%时间复杂度O(N)设不修改时利润total相比不修改时利润增加了sum因为最大利润maxsum可能是负数所以返回值为 totalmax(maxsum,0)滑动窗口[i-k,i-1]找maxsum的过程中左半窗口[i-k,i-k/2-1]修改前策略为s[i]修改后策略为0利润增加p[j]*(0-s[j])之和j在左半窗口右半窗口[i-k/2,i-1]修改前策略为s[i]修改后策略为1利润增加p[j]*(1-s[j])之和j在右半窗口所以窗口滑动时有窗口首位置、尾位置和中间位置改变首位置进窗口sum增加了p[i]*(1-s[i])中间位置i-k/2的元素更新从右半窗口移到左半窗口s数组值从1变成0sum减少了p[i-k/2]尾位置出窗口sum减少了p[i-k]*(-s[i-k])Java代码class Solution { //解法一优化前的代码 public long maxProfit(int[] p, int[] s, int k) { int np.length; //先计算不修改时的最大利润 long total0; for(int i0;in;i) totalp[i]*s[i]; //计算修改后能获得的最大利润 //保证索引1~index long[] prevnew long[n1];//前缀和 long[] suffnew long[n2];//后缀和 //前缀和prev[i]:i之前的前缀和不包括i for(int i1;in;i) prev[i]prev[i-1]p[i-1]*s[i-1]; //后缀和suff[i]:i-1之后的后缀和包括i-1 //统一含义后缀和suff[i]:i-2之后的后缀和不包括i-2 for(int in;i1;i--) suff[i]suff[i1]p[i-1]*s[i-1]; long rettotal,sum0; for(int right0;rightn;right){ //进窗口 sump[right]; int leftright-k1; if(left0) continue; //更新 //计算窗口内的前k/2个和 long prevsum0; for(int ileft;ileftk/2;i) prevsump[i]; //计算窗口内的后k/2个和 long suffsumsum-prevsum; //拼接三个部分[0,left-1][left,right][right1,n-1] long tmpsuffsumprev[left]suff[right2]; //不修改和修改后能拿的最大利润取最大值 retMath.max(ret,tmp); //出窗口 sum-p[left]; } return ret; } }class Solution { //解法一优化后的代码 public long maxProfit(int[] p, int[] s, int k) { int np.length; //先计算不修改时的最大利润 long total0; for(int i0;in;i) totalp[i]*s[i]; //计算修改后能获得的最大利润 //保证索引1~index long[] prevnew long[n1];//前缀和 long[] suffnew long[n2];//后缀和 //前缀和prev[i]:i之前的前缀和不包括i for(int i1;in;i) prev[i]prev[i-1]p[i-1]*s[i-1]; //后缀和suff[i]:i-1之后的后缀和包括i-1 //统一含义后缀和suff[i]:i-2之后的后缀和不包括i-2 for(int in;i1;i--) suff[i]suff[i1]p[i-1]*s[i-1]; long rettotal,sum0; //优化预处理区间和 long[] prefixnew long[n1]; //prefix[i]:i之前的前缀和,不包括i for(int i1;in;i) prefix[i]prefix[i-1]p[i-1]; for(int right0;rightn;right){ //进窗口 sump[right]; int leftright-k1; if(left0) continue; //更新 //计算窗口内的前k/2个和 //优化用前缀和相减代替原本的遍历 long prevsumprefix[leftk/2]-prefix[left]; //计算窗口内的后k/2个和 long suffsumsum-prevsum; //拼接三个部分[0,left-1][left,right][right1,n-1] long tmpsuffsumprev[left]suff[right2]; //不修改和修改后能拿的最大利润取最大值 retMath.max(ret,tmp); //出窗口 sum-p[left]; } return ret; } }class Solution { //解法二单纯前缀和解法 public long maxProfit(int[] p, int[] s, int k) { int np.length; long[] sumnew long[n1]; long[] sumsellnew long[n1]; for(int i1;in;i){ sum[i]sum[i-1]p[i-1]*s[i-1]; sumsell[i]sumsell[i-1]p[i-1]; } long retLong.MIN_VALUE;//可能出现负数 for(int ik;in;i) retMath.max(ret,sum[i-k]sum[n]-sum[i]sumsell[i]-sumsell[i-k/2]); return Math.max(sum[n],ret); } }class Solution { //解法三滑动窗口 public long maxProfit(int[] p, int[] s, int k) { long total0,maxsum0,sum0; for(int i0;ip.length;i){ //计算不修改时的最大利润 totalp[i]*s[i]; //进窗口 sump[i]*(1-s[i]); //还未形成窗口时 if(ik-1){ //在下一轮循环中中间下标的元素从右半部分移到左半部分s[i-k/21]从1变成0 if(ik/2-1) sum-p[i-k/21]; continue; } //更新 maxsumMath.max(maxsum,sum); //出窗口 //中间下标i-k/21元素右半部分移到左半部分s[i-k/21]从1变成0 //尾下标i-k1元素出窗口 sum-p[i-k/21]-p[i-k1]*s[i-k1]; } return totalmaxsum; } }