免备案网站空间怎样增加网站流量

免备案网站空间,怎样增加网站流量,重庆公司名字,链接提交百度站长平台188.买卖股票的最佳时机IV 文章讲解/视频讲解 题目描述#xff1a; 给定一个整数数组 prices #xff0c;它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意#xff1a;你不能同时…188.买卖股票的最佳时机IV文章讲解/视频讲解题目描述给定一个整数数组 prices 它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。示例 1输入k 2, prices [2,4,1]输出2 解释在第 1 天 (股票价格 2) 的时候买入在第 2 天 (股票价格 4) 的时候卖出这笔交易所能获得利润 4-2 2。示例 2输入k 2, prices [3,2,6,5,0,3]输出7 解释在第 2 天 (股票价格 2) 的时候买入在第 3 天 (股票价格 6) 的时候卖出, 这笔交易所能获得利润 6-2 4。随后在第 5 天 (股票价格 0) 的时候买入在第 6 天 (股票价格 3) 的时候卖出, 这笔交易所能获得利润 3-0 3 。提示0 k 1000 prices.length 10000 prices[i] 1000思路本题作为昨天III的进阶版算得上是名副其实的hard了昨天的III是说最多可以买卖2次也就是限定在了可以买卖0次1次2次。但是本题给的是最多可以买卖k次这就要稍微发散一下思维了。1.确定dp数组及其下标含义dp[i][j] 第i天的状态为j所剩下的最大现金是dp[i][j]j的状态表示为0 表示不操作1 第一次买入2 第一次卖出3 第二次买入4 第二次卖出.....规律其实很明显了除了0以外只要是j为单数就是买入j为偶数就是卖出。因为题目规定最多交易k次所以范围定为 2 * k 1也就是k买入 k卖出 1初始 2k 12.确定递推公式dp[i][j]只能通过两种情况推出来要么前一天就已经是目前的状态了dp[i -1][j]。要么前一天与今天的状态相反比如前一天没持有今天持有把股票买入了那么我们手里的现金就得减去买股票的钱也就是dp[i -1][j -1] - price[i]。还有可能是前一天持有今天不持有了股票抛掉了那么我们手里的现金就多出来了卖出股票的钱即dp[i -1][j -1] price[i]。我们很容易就能发现这两个公式唯一的差别就是加减号上再仔细一想只有当j是奇数今天买入时我们要减当j是偶数是今天卖出时我们就加。那我们就直接用一个Math.pow( -1 , j)计算-1的j次方并且用计算出来的结果去乘price[i]直接就能用一行代码搞定加减号的问题如下dp[i - 1][j - 1] Math.pow(-1, j) * prices[i]最后我们只需要比较两种情况谁大就行了所以递推公式完整代码如下dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - 1] Math.pow(-1, j) * prices[i])3.dp数组的初始化毋庸置疑还是第0天要初始化这个昨天就有一步一步递推了j为单数时全部初始化为-price[0]容易错写成-price[i]偶数直接全赋值为0即可。4.确定遍历顺序从递归公式其实已经可以看出一定是从前向后遍历因为dp[i]依靠dp[i - 1]的数值。5.举例推导dp数组以输入[1,2,3,4,5]k2为例。最后一次卖出一定是利润最大的dp[prices.size() - 1][2 * k]即红色部分就是最后求解。代码示例function maxProfit(k: number, prices: number[]): number { const length: number prices.length if (length 0) return 0 const dp: number[][] new Array(length).fill(0).map(_ new Array(k * 2 1).fill(0)) for (let i 1; i k; i) { dp[0][i * 2 - 1] -prices[0] } for (let i 1; i length; i) { for (let j 1; j 2 * k 1; j) { dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - 1] Math.pow(-1, j) * prices[i]) } } return dp[length - 1][2 * k] };309.买卖股票的最佳时机含冷冻期文章讲解/视频讲解题目描述给定一个整数数组其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。示例:输入: [1,2,3,0,2]输出: 3解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]思路本题比较阴间的点在于加入了一个冷冻期那就得区分成四种状态1.持有股票状态 2.保持卖出股票的状态 3.今天卖出股票 4.今天为冷冻期 状态2和状态4在逻辑上是可以合并的但是放代码里就会变得极其混乱所以还是单独拎出来了。1.确定dp数组及其下标含义dp[i][j]第i天状态为j所剩的最多现金为dp[i][j]j的状态为0状态一1状态二2状态三3状态四注意这里都是持有并非一定买入保持买入或卖出的意思是可能前几天就买入或者卖出了然后一直没有操作2.确定递推公式这是本题的主要难点需要一个状态一个状态分析总共四行代码状态一保持买入要么前一天就已经买入了。要么今天买入这又能分两种情况了前一天是冷却期状态四前一天是保持卖出的状态状态二那么dp[i][0] max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);状态二保持卖出可以是前一天就已经是卖出状态了也可以是前一天处于冷冻期状态四所以dp[i][1] max(dp[i - 1][1], dp[i - 1][3]);状态三今天卖股票只有一种情况昨天手上有股票今天才能有东西卖即dp[i][2] dp[i - 1][0] prices[i];状态四今天冷冻期也只有一种情况昨天把股票卖了今天才能处于冷冻期dp[i][3] dp[i - 1][2];3.dp数组如何初始化还是主要讨论第0天怎么初始化首先dp[0][0]持有股票状态肯定等于-price[0]这是毋庸置疑的只能是当天买入股票。剩下的三种状态只能初始化为0如果初始化为其他数值第一天买入股票后手里剩的现金数量就对不上账了可以自己带进去试试看。4.确定遍历顺序从递归公式上可以看出dp[i] 依赖于 dp[i-1]所以是从前向后遍历。5.举例推导dp数组以 [1,2,3,0,2] 为例dp数组如下最后结果是取 状态二状态三和状态四的最大值更容易就会把状态四忘了状态四是冷冻期最后一天如果是冷冻期也可能是最大值。代码示例function maxProfit(prices: number[]): number { const length: number prices.length if (length 0) return 0 const dp: number[][] new Array(length).fill(0).map(_ []) dp[0][0] -prices[0] dp[0][1] dp[0][2] dp[0][3] 0 for (let i 1; i length; i) { dp[i][0] Math.max(dp[i - 1][0], Math.max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i])) dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][3]) dp[i][2] dp[i - 1][0] prices[i] dp[i][3] dp[i - 1][2] } const lastrE1: number[] dp[length - 1] return Math.max(lastrE1[1], lastrE1[2], lastrE1[3]) };714.买卖股票的最佳时机含手续费文章讲解/视频讲解题目描述给定一个整数数组 prices其中第 i 个元素代表了第 i 天的股票价格 非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易但是你每笔交易都需要付手续费。如果你已经购买了一个股票在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意这里的一笔交易指买入持有并卖出股票的整个过程每笔交易你只需要为支付一次手续费。示例 1:输入: prices [1, 3, 2, 8, 4, 9], fee 2输出: 8解释: 能够达到的最大利润:在此处买入 prices[0] 1在此处卖出 prices[3] 8在此处买入 prices[4] 4在此处卖出 prices[5] 9总利润: ((8 - 1) - 2) ((9 - 4) - 2) 8.注意:0 prices.length 50000.0 prices[i] 50000.0 fee 50000.思路本题和前面两题比起来简直就是小儿科这道题更像是“122.买卖股票的最佳时机II”的进阶版本唯一区别就是卖股票要多一个减去手续费的操作。所以只单独讲解递推公式部分本题dp数组的含义是dp[i][0] 表示第i天持有股票所得最多现金。 dp[i][1] 表示第i天不持有股票所得最多现金。那么如果第i天我们持有股票可以从两种状态推出来要么i -1 天就持有股票了今天维持现状而已。要么i-1 天没持有股票今天把股票买进来了那现在的现金就得扣掉今天的股票价格所以dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]);而如果第i天没持有股票同样两种可能可以是昨天就没持有今天保持不变。也可以是昨天持有股票今天卖掉了那么现在手里的现金就能加上今天股票的卖价但是注意还得扣掉手续费此处是与“122.买卖股票的最佳时机II”唯一有差别的点即dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee);其他代码完全一致代码示例function maxProfit(prices: number[], fee: number): number { const length: number prices.length if (length 0) return 0 const dp: number[][] new Array(length).fill(0).map(_ []) dp[0][0] -prices[0] dp[0][1] 0 for (let i 1; i length; i) { dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]) dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee) } return dp[length - 1][1] };