假设你有一个数组,长度为,其中是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益 1. 你最多可以对该股票有笔交易操作,一笔交易代表着一次买入与一次卖出,但是再次购买前必须卖出之前的股票 2. 如果不能获取收益,请返回0 3. 假设买入卖出均无手续费 数据范围: 1. 0 <= prices.length <= 1000 2. 0 <= prices[i] <= 1000 3. 0 <= k <= 100-笔试面试资料

这是qklbishe.com第19245 篇笔试面试资料
提供答案分析,通过本文《假设你有一个数组,长度为,其中是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益
1. 你最多可以对该股票有笔交易操作,一笔交易代表着一次买入与一次卖出,但是再次购买前必须卖出之前的股票
2. 如果不能获取收益,请返回0
3. 假设买入卖出均无手续费

数据范围: 1. 0 <= prices.length <= 1000 2. 0 <= prices[i] <= 1000 3. 0 <= k <= 100-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

假设你有一个数组假设你有一个数组,长度为,其中是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益   1. 你最多可以对该股票有笔交易操作,一笔交易代表着一次买入与一次卖出,但是再次购买前必须卖出之前的股票    2. 如果不能获取收益,请返回0   3. 假设买入卖出均无手续费            数据范围:    1. 0 &lt;= prices.length &lt;= 1000    2. 0 &lt;= prices[i] &lt;= 1000    3. 0 &lt;= k &lt;= 100,长度为假设你有一个数组,长度为,其中是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益   1. 你最多可以对该股票有笔交易操作,一笔交易代表着一次买入与一次卖出,但是再次购买前必须卖出之前的股票    2. 如果不能获取收益,请返回0   3. 假设买入卖出均无手续费            数据范围:    1. 0 &lt;= prices.length &lt;= 1000    2. 0 &lt;= prices[i] &lt;= 1000    3. 0 &lt;= k &lt;= 100,其中假设你有一个数组,长度为,其中是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益   1. 你最多可以对该股票有笔交易操作,一笔交易代表着一次买入与一次卖出,但是再次购买前必须卖出之前的股票    2. 如果不能获取收益,请返回0   3. 假设买入卖出均无手续费            数据范围:    1. 0 &lt;= prices.length &lt;= 1000    2. 0 &lt;= prices[i] &lt;= 1000    3. 0 &lt;= k &lt;= 100是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益
1. 你最多可以对该股票有假设你有一个数组,长度为,其中是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益   1. 你最多可以对该股票有笔交易操作,一笔交易代表着一次买入与一次卖出,但是再次购买前必须卖出之前的股票    2. 如果不能获取收益,请返回0   3. 假设买入卖出均无手续费            数据范围:    1. 0 &lt;= prices.length &lt;= 1000    2. 0 &lt;= prices[i] &lt;= 1000    3. 0 &lt;= k &lt;= 100笔交易操作,一笔交易代表着一次买入与一次卖出,但是再次购买前必须卖出之前的股票
2. 如果不能获取收益,请返回0
3. 假设买入卖出均无手续费
数据范围:
1. 0 <= prices.length <= 1000
2. 0 <= prices[i] <= 1000
3. 0 <= k <= 100
Java

假设你有一个数组,长度为,其中是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益   1. 你最多可以对该股票有笔交易操作,一笔交易代表着一次买入与一次卖出,但是再次购买前必须卖出之前的股票    2. 如果不能获取收益,请返回0   3. 假设买入卖出均无手续费            数据范围:    1. 0 &lt;= prices.length &lt;= 1000    2. 0 &lt;= prices[i] &lt;= 1000    3. 0 &lt;= k &lt;= 100 零葬

暴力递归

从左往右尝试,需要如下的几个可变参数(固定不变的参数不讨论):
  1. 当前是第几天day;
  2. 还剩下几次交易次数rest;
  3. 当前的收益profit;
  4. 之前是不是刚卖掉股票notBuy。
如此一来,我们有两个base case需要结算当前的收益,并更新最大收益:(1) 已经来到了最后一天;(2) 交易数已经用完。对于普遍的情况,我们需要考虑之前是不是卖掉了股票:(1) 如果刚卖掉过股票,此时可以选择买与不买;(2) 如果刚买过股票,此时可以选择卖与不卖。由此得到如下的暴力递归解法,其实这个解法已经可以通过大部分用例了(16/18)。
import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param prices int整型一维数组       * @param k int整型       * @return int整型      */     int maximumProfit = 0;     public int maxProfit (int[] prices, int k) {         // write code here         recurrent(prices, 0, k, 0, true);         return maximumProfit;     }          private void recurrent(int[] prices, int depth, int rest, int profit, boolean notBuy) {         if(depth == prices.length || rest == 0){             // 来到最后一天或交易数已经用完,结算收益             maximumProfit = Math.max(maximumProfit, profit);             return;         }         if(notBuy){             // 还没买过可以买或者不买             recurrent(prices, depth + 1, rest, profit, notBuy);    // 不买             recurrent(prices, depth + 1, rest, profit - prices[depth], !notBuy);      // 买         }else{             // 当前可以选择卖与不卖             recurrent(prices, depth + 1, rest, profit, notBuy);    // 不卖             recurrent(prices, depth + 1, rest - 1, profit + prices[depth], !notBuy);    // 卖         }     } } 

动态规划

根据递归的逻辑,我们可以改出动态规划。首先我们可以知道,profit参数是要填到dp表中的值,它并不是一个可变参数;depth是由大到小,直接遍历prices数组即可,也不算是个可变参数;因此可变参数有操作次数rest和当前手里是否持股notBuy,布尔类型的值可以用0和1代替。构造dp表,dp[i][0]表示进行过i次交易后手上已无股的最大收益,dp[i][1]表示进行过i次交易后手上还有股的最大收益。
import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param prices int整型一维数组       * @param k int整型       * @return int整型      */     public int maxProfit (int[] prices, int k) {         // write code here         int n = prices.length;         if(n == 0) return 0;         int[][] dp = new int[k + 1][2];         for(int i = 0; i <= k; i++){             dp[i][1] = -prices[0];     // 首日买入均为负债情况         }         for(int day = 1; day < n; day++){             for(int rest = 1; rest <= k; rest++){                 // 要保证第day天手上无股票,可以在前一天持股的基础上卖掉也可以直接从前一天无股的状态转移过来                 dp[rest][0] = Math.max(dp[rest][0], dp[rest][1] + prices[day]);                 // 要保证第day天手上有股票,可以在前一天无股的基础上买入也可以直接从前一天有股的状态转移过来                 dp[rest][1] = Math.max(dp[rest][1], dp[rest - 1][0] - prices[day]);             }         }         return dp[k][0];     } } 

今天 22:53:55 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 假设你有一个数组,长度为,其中是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益 1. 你最多可以对该股票有笔交易操作,一笔交易代表着一次买入与一次卖出,但是再次购买前必须卖出之前的股票 2. 如果不能获取收益,请返回0 3. 假设买入卖出均无手续费 数据范围: 1. 0 <= prices.length <= 1000 2. 0 <= prices[i] <= 1000 3. 0 <= k <= 100-笔试面试资料

提供最优质的资源集合

立即查看 了解详情