百度网站 收录最好看免费观看高清大全英雄联盟

百度网站 收录,最好看免费观看高清大全英雄联盟,网站安全建设,androidapp开发入门下面我把 LeetCode 3652#xff1a;按策略买卖股票的最佳时机 完整做一遍#xff1a;从建模 → 思路 → 算法 → 代码#xff08;含详细注释#xff09;#xff0c;一步一步来。 原题#xff1a; 给你两个整数数组 prices 和 strategy#xff0c;其中#xff1a;prices…下面我把LeetCode 3652按策略买卖股票的最佳时机完整做一遍从建模 → 思路 → 算法 → 代码含详细注释一步一步来。原题给你两个整数数组 prices 和 strategy其中prices[i] 表示第 i 天某股票的价格。 strategy[i] 表示第 i 天的交易策略其中 -1 表示买入一单位股票。 0 表示持有股票。 1 表示卖出一单位股票。 同时给你一个 偶数 整数 k你可以对 strategy 进行 最多一次 修改。一次修改包括 选择 strategy 中恰好 k 个 连续 元素。 将前 k / 2 个元素设为 0持有。 将后 k / 2 个元素设为 1卖出。 利润 定义为所有天数中 strategy[i] * prices[i] 的 总和 。 返回你可以获得的 最大 可能利润。注意 没有预算或股票持有数量的限制因此所有买入和卖出操作均可行无需考虑过去的操作 做出这道题并给出详细解释分析和注释一、题意重述用“数学 业务”语言给定prices[i]第i天股价strategy[i]第i天策略-1买入 → 对利润贡献-prices[i]0持有 → 贡献01卖出 → 贡献prices[i]原始利润[profit \sum strategy[i] \times prices[i]]你可以做最多一次修改修改规则选一个长度为k的连续子数组前k/2天 → 全部改成0后k/2天 → 全部改成1⚠️k是偶数目标修改 0 次或 1 次使总利润最大二、关键思维问题本质是什么1️⃣ 原利润是固定的baseProfit Σ strategy[i] * prices[i]我们只需要关心“一次修改最多能额外增加多少利润”2️⃣ 修改 对一段区间的“利润差值”设修改区间是[l, r]长度k其中[l, l k/2 - 1]→ 改为0[l k/2, r]→ 改为1原贡献Σ strategy[i] * prices[i]新贡献前半段0 后半段prices[i]增量 新 - 原三、把“增量”拆成两个部分 前半段变成 0原来strategy[i] * prices[i] 现在0 增量- strategy[i] * prices[i] 后半段变成卖出原来strategy[i] * prices[i] 现在prices[i] 增量(1 - strategy[i]) * prices[i]✅ 单次修改的总增量[\Delta \sum_{前半段} (-strategy[i] \cdot prices[i])\sum_{后半段} ((1 - strategy[i]) \cdot prices[i])]四、算法思路滑动窗口为什么用滑动窗口区间长度固定为k要枚举所有连续长度为k的区间每次移动只加减一个元素O(n)核心变量baseProfit不修改的利润delta当前窗口的利润增量maxDelta所有窗口中最大的增量滑动时怎么更新设当前窗口[i - k 1, i]新进入的元素i若i在后半段 → 加(1 - strategy[i]) * prices[i]移出的元素i - k若它原来在前半段 → 减-strategy[x] * prices[x]若在后半段 → 减(1 - strategy[x]) * prices[x]五、完整 Java 实现带详细注释classSolution{publiclongmaxProfit(int[]prices,int[]strategy,intk){intnprices.length;// 1. 计算原始利润longbaseProfit0;for(inti0;in;i){baseProfit(long)strategy[i]*prices[i];}// 如果 k 为 0 或无法修改if(k0||kn){returnbaseProfit;}inthalfk/2;longdelta0;longmaxDelta0;// 2. 初始化第一个窗口 [0, k-1]for(inti0;ik;i){if(ihalf){// 前半段 → 变成 0delta-(long)strategy[i]*prices[i];}else{// 后半段 → 变成卖出delta(long)(1-strategy[i])*prices[i];}}maxDeltaMath.max(0,delta);// 3. 滑动窗口for(intik;in;i){intouti-k;// 移除 outif(outouthalf){delta--(long)strategy[out]*prices[out];}else{delta-(long)(1-strategy[out])*prices[out];}// 加入 iif(ioutk-half){delta-(long)strategy[i]*prices[i];}else{delta(long)(1-strategy[i])*prices[i];}maxDeltaMath.max(maxDelta,delta);}// 4. 原始利润 最佳增量returnbaseProfitmaxDelta;}}六、复杂度分析项目复杂度时间O(n)空间O(1)七、为什么这题是「中等」但难度偏高题目描述是业务语言真正考的是数学建模能力把“策略变化”转为“区间增量”很多人卡在不知道“利润增量”怎么计算想 DP其实不需要