关键词:
[JavaScript 刷题] DP - 买卖股票的最佳时机,leetcode 121
github repo 地址: https://github.com/GoldenaArcher/js_leetcode,Github 的目录 大概 会更新的更勤快一些。
题目地址:121. Best Time to Buy and Sell Stock
题目
如下:
You are given an array
prices
whereprices[i]
is the price of a given stock on thei^th
day.You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return
0
.
解题思路
Best Time to Buy and Sell Stock 整个系列应该算都是比较高频和经典的 DP 问题了,不管怎么说都推荐刷一下以及理解一下这套题的核心思路。
这道题比较简单,题目规定是:
- 只可以买卖一次股票
- 需要获得最大利润
做法为使用一个变量去保存最小值和最大利润,每次便遍历时候保存 m i n ( c u r r , m i n ) min(curr, min) min(curr,min),随后更新最大利润 m a x ( m a x , c u r r − m i n ) max(max, curr - min) max(max,curr−min) 即可。
以 [6, 2, 7, 1, 3, 5]
为例:
-
min = 6
,maxProfit = 0
-
min = 2
,maxProfit = 4
-
min = 2
,maxProfit = 5
-
min = 1
,maxProfit = 5
注意,虽然这里 min 变成了 1,不过最大利润是由 7 − 2 7 - 2 7−2 形成的,后面也不会产生比这个还要大的利润。
-
min = 1
,maxProfit = 5
-
min = 1
,maxProfit = 5
保存 min
主要是为了方便计算后面的差值以便更新最大利润。
使用 JavaScript 解题
/**
* @param string s
* @return number
*/
var firstUniqChar = function (s)
const map = new Map();
for (let i = 0; i < s.length; i++)
const ch = s[i];
if (map.has(ch))
map.get(ch)[0]++;
else
map.set(ch, [1, i]);
for (const [char, freq] of map)
if (freq[0] === 1) return freq[1];
return -1;
;
java刷题--121买卖股票的最佳时机(代码片段)
java刷题--121买卖股票的最佳时机题目代码结果题目代码publicclassSolutionpublicintmaxProfit(intprices[])intminprice=Integer.MAX_VALUE;intmaxprofit=0;for(inti=0;i<prices.length;i++)if(prices[i]<mi 查看详情
122.买卖股票的最佳时机ii(代码片段)
122.买卖股票的最佳时机II思路dp的定义依旧是dp[i][0]表示持有,dp[i][1]表示没有。可以多次买卖,计算持有时将上次的利润加上。可以利用滚动数组节约空间返回滚动数组最后的下标需要用size确定classSolutionpublicintmaxProfit(in... 查看详情
122.买卖股票的最佳时机ii(代码片段)
122.买卖股票的最佳时机II思路dp的定义依旧是dp[i][0]表示持有,dp[i][1]表示没有。可以多次买卖,计算持有时将上次的利润加上。可以利用滚动数组节约空间返回滚动数组最后的下标需要用size确定classSolutionpublicintmaxProfit(in... 查看详情
代码随想录算法训练营第四十九天|121买卖股票的最佳时机122买卖股票的最佳时机ii(代码片段)
代码随想录算法训练营第四十九天|121买卖股票的最佳时机122买卖股票的最佳时机IILeetCode121买卖股票的最佳时机题目:121.买卖股票的最佳时机动规五部曲:确定dp数组以及下标的含义**dp[i][0]表示第i天持有股票所得最多现金**确... 查看详情
123.买卖股票的最佳时机iii(代码片段)
123.买卖股票的最佳时机III思路dp,最多只能买卖两次,每天有五种状态,其中四种需要讨论。dp[i][]每天的各个状态的利润。卖出的利润一定比买入的利润大dp初始化时,看作第一天可以多次买入卖出。例如第一天... 查看详情
123.买卖股票的最佳时机iii(代码片段)
123.买卖股票的最佳时机III思路dp,最多只能买卖两次,每天有五种状态,其中四种需要讨论。dp[i][]每天的各个状态的利润。卖出的利润一定比买入的利润大dp初始化时,看作第一天可以多次买入卖出。例如第一天... 查看详情
123.买卖股票的最佳时机iii(三维dp)(代码片段)
123.买卖股票的最佳时机III 解释见如下代码: classSolutionpublic:intmaxProfit(vector<int>&prices)if(prices.size()==0)//容易忘的点return0;intdp[prices.size()+10][2][3];//天数有票没票第几次交易了for(inti= 查看详情
leetcode刷题python309.最佳买卖股票时机含冷冻期(代码片段)
1题目给定一个整数数组prices,其中第prices[i]表示第i天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):卖出股票后,你无法在第... 查看详情
309.最佳买卖股票时机含冷冻期dp(代码片段)
...以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。卖出股票后,你无法在第二天买入股票(即冷冻期为1天)。示例:输入:[1,2,3,0,2]输出:3... 查看详情
leetcode刷题100天—121.买卖股票的最佳时机(数组+双指针)—day24(代码片段)
前言:作者:神的孩子在歌唱大家好,我叫运智121.买卖股票的最佳时机难度简单1812收藏分享切换为英文接收动态反馈给定一个数组prices,它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择某一天买... 查看详情
leetcode刷题100天—121.买卖股票的最佳时机(数组+双指针)—day24(代码片段)
前言:作者:神的孩子在歌唱大家好,我叫运智121.买卖股票的最佳时机难度简单1812收藏分享切换为英文接收动态反馈给定一个数组prices,它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择某一天买... 查看详情
刷题38——买卖股票的最佳时机(力扣)
70.买卖股票的最佳时机题目链接来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock题目描述给定一个数组,它的第 i个元素是一支给定股票第i天的价格。如果你最多只允许完成一笔交易(即买入和... 查看详情
188.买卖股票的最佳时机iv(代码片段)
188.买卖股票的最佳时机IV思路dp二维数组的含义是第i天第k次交易状态(买入卖出)的利润;初始化dp数组时,所有的买入都是-price[0];所有的卖出都是0;递推的是第k次买入和卖出的利润;最后要返回的最后... 查看详情
leetcode刷题python122.买卖股票的最佳时机ii(代码片段)
1题目给你一个整数数组prices,其中prices[i]表示某支股票第i天的价格。在每一天,你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买,然后在同一天出售。返回你能获得的最大... 查看详情
leetcode刷题python714.买卖股票的最佳时机含手续费(代码片段)
1题目给定一个整数数组prices,其中prices[i]表示第i天的股票价格;整数fee代表了交易股票的手续费用。你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就... 查看详情
714.买卖股票的最佳时机含手续费(代码片段)
714.买卖股票的最佳时机含手续费思路在卖出比较的时候减去手续费即可classSolutionpublicintmaxProfit(int[]prices,intfee)intsize=prices.length;if(size==0)return0;//0持有股票,1无股票int[][]dp=newint[size][2];dp[0][0] 查看详情
leetcode刷题9.买卖股票的最佳时机——java版(代码片段)
我真的服了,这种题还要玩文字游戏?测试用例居然还有[]???,都空了你还买什么股票???——leetcode此题热评前言哈喽,大家好,我是一条。糊涂算法,难得糊涂。通过今天... 查看详情
leetcode买卖股票的最佳时机含手续费(代码片段)
动态规划简单题我们设置二维数组dp[size][2],其中dp[i][0]代表第i天不持有股票的最大价值其中dp[i][1]代表第i天持有股票的最大价值当天持有股票可以从前一天持有股票和前一天不持有股票现今买入转换得来当天不持有股票可... 查看详情