当前位置：网站首页>刷题记录(leetcode)
刷题记录(leetcode)
2022-04-21 09:30:00 【pearz】
贪心算法
121. 买卖股票的最佳时机
地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
描述：
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
实例1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票
实例2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
答案：
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
int min = 0;
int max = 0;
for (int i = 1; i < prices.length; i++) {
min = prices[i] < prices[min] ? i : min;
max = prices[i] >= prices[min] ? i : max;
if (min < max) {
res = Math.max(res, prices[max] - prices[min]);
}
}
return res;
}
}
122. 买卖股票的最佳时机 II
地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
描述：
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。
返回 你能获得的最大利润 。
实例1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
实例2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
实例3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
答案：
class Solution {
public int maxProfit(int[] prices) {
int result = 0;
for (int i = 1; i < prices.length; i++) {
result += Math.max(prices[i] - prices[i - 1], 0);
}
return result;
}
}
714. 买卖股票的最佳时机含手续费
地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
描述：
给定一个整数数组 prices，其中 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
实例1：
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6
答案：
class Solution {
public int maxProfit(int[] prices, int fee) {
//当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利
int buy = prices[0] + fee;
int sum = 0;
for (int p : prices) {
if (p + fee < buy) {
buy = p + fee;
} else if (p > buy){
sum += p - buy;
buy = p;
}
}
return sum;
}
}
动态规划
121. 买卖股票的最佳时机
地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
描述：
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
实例1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票
实例1：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
答案：
class Solution {
public int maxProfit(int[] prices) {
int length = prices.length;
int[][] dp = new int[length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < length; i++) {
//第i天不持有股票(前一天不持有/前一天持有)
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
//第i天持有股票（前一天持有/前一天不持有）
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[length - 1][0];
}
}
122. 买卖股票的最佳时机 II
地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
描述：
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。
返回 你能获得的最大利润 。
实例1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
实例2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
实例3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
答案：
class Solution {
public int maxProfit(int[] prices) {
int length = prices.length;
int[][] dp = new int[length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < length; i++) {
//第i天不持有股票(前一天不持有/前一天持有)
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
//第i天持有股票（前一天持有/前一天不持有）
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[length - 1][0];
}
}
123.买卖股票的最佳时机 III
地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
描述：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
实例1：
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
实例2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
实例3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
实例4
输入：prices = [1]
输出：0
答案：
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
//dp[i][0]代表当天没有操作
//dp[i][1]代表当天为第一次买入
//dp[i][2]代表当天为第一次卖出
//dp[i][3]代表当天为第二次买入
//dp[i][4]代表当天为第二次卖出
int[][] dp = new int[len][5];
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[len - 1][4];
}
}
188.买卖股票的最佳时机 IV
地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-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 。
答案：
class Solution {
public int maxProfit(int k, int[] prices) {
int len = prices.length;
if (len == 0) {
return 0;
}
int[][] dp = new int[len][k * 2 + 1];
for (int i = 1; i <= k; i++) {
dp[0][2 * i - 1] = -prices[0];
}
for (int i = 1; i < len; i++) {
for (int j = 1; j <= k; j++) {
//第i天为第j次买入
dp[i][2 * j - 1] = Math.max(dp[i - 1][2 * j - 1], dp[i - 1][2 * j - 2] - prices[i]);
//第i天为第j次卖出
dp[i][2 * j] = Math.max(dp[i - 1][2 * j], dp[i - 1][2 * j - 1] + prices[i]);
}
}
return dp[len - 1][2 * k];
}
}
309. 最佳买卖股票时机含冷冻期
地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
描述：
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
实例1：
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
实例2：
输入: prices = [1]
输出: 0
答案：
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
//dp[i][0]表示当日不持有，dp[i][1]表示当日持有
int[][] dp = new int[len][2];
dp[0][1] = -prices[0];
dp[1][0] = Math.max(dp[0][0], dp[0][1] + prices[1]);
dp[1][1] = Math.max(dp[0][1], dp[0][0] - prices[1]);
for (int i = 2; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
//dp[i - 1][1]代表前一天持有的情况
//dp[i - 2][0] - prices[i]代表前一天不持有的情况，但是前一天不能为卖出的状态，因为前一天卖出则今天不能买入，所有此时为i-2天不持有状态
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
}
return dp[len - 1][0];
}
}
714. 买卖股票的最佳时机含手续费
地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
描述：
给定一个整数数组 prices，其中 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
实例2：
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6
答案：
class Solution {
public int maxProfit(int[] prices, int fee) {
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][1] = -prices[0] - fee;
for (int i = 1; i < len; 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[len - 1][0];
}
}
版权声明
本文为[pearz]所创，转载请带上原文链接，感谢
https://blog.csdn.net/pearz/article/details/124257290
边栏推荐
猜你喜欢
Pipy MQTT 代理之（三）Logging
计算器（力扣）
Geek challenge 2019 upload 1
Multithreaded small copy set (New Edition 2)
Handler asynchronous message passing mechanism (I) common basic usage of handler
Open3d读写ply点云文件
Open3d reads and writes PCD point cloud files
CC00019.CloudJenkins—————————————
纯c语言链表实现学生信息管理系统.(你学会了吗？)
Dark blue - Visual slam - Section 6 exercise
随机推荐
1146: 吃糖果
【概率论与数理统计】1.4 条件概率
【总结】1296- 总结 12 个常见移动端 H5 与 Hybrid 开发问题
Handler asynchronous message passing mechanism (2) create handler in sub thread
PageRank case Airport
给网站添加pjax无刷新，换页音乐不中断
报告解读下载 | 首份《中国数据库行业分析报告》重磅发布！
【栈和队列】C语言简单应用 ⌊栈和队列互相实现，循环队列⌉
synchronized真的很重么？
CC00019. CloudJenkins—————————————
CC10000.CloudJenkins—————————————
深蓝-视觉slam-第六节习题
[Netty ]自己实现一个redis客户端难吗？
1167: number of reversals (pointer topic)
1161: string length (pointer)
Zabbix 5.4 Server安装
SurfaceView高性能绘制（四）代码实践篇-绘制多张图片
1161: 字符串长度（指针专题）
纯c语言链表实现学生信息管理系统.(你学会了吗？)
Linux中，MySQL的常用命令