IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 只赢不亏的买股票的方法 -> 正文阅读

[数据结构与算法]只赢不亏的买股票的方法

前言

大家好,我是来自于「华为」「程序员小熊」。今天给大家带来一道与「贪心算法」相关的题目,这道题同时也是字节、苹果和亚马逊等互联网大厂的面试题,即力扣上的第 122 题-买卖股票的最佳时机 II。

本文主要介绍「贪心」的策略来解答此题,供大家参考,希望对大家有所帮助。

买卖股票的最佳时机 II

题目描述

?题目描述

示例

示例

解题思路

贪心算法是通过做出一系列选择来求出问题的最优解,在每个决策点,它做出当时看来最佳的选择。通过「局部最优」的选择,寄希望实现「全局最优解」

「举例」

以 prices = [1,4,2,3,7] 为例子,求获得的最大利润,如下图示。

例子

例子

遍历数组 prices,第一天一定买入;

第一次决策

第一次决策

尔后判断判断第二天的价格是否大于第一天,大于则卖出(局部最优);

价格递增时决策

价格递增时决策

卖出后,如果后面一天的价格小于当天的价格,则当天不买,防止亏本;

价格递减时决策

价格递减时决策

以此类推,其采用贪心策略买卖股票的完整决策过程如下动图示

决策的整个过程

决策的整个过程

Show me the Code

「C」

int?maxProfit(int*?prices,?int?pricesSize){
????int?ans?=?0;
????for?(int?i?=?1;?i?<?pricesSize;?++i)?{
????????/*?后一天的价格比前一天高,则卖出(当前最佳策略)?*/
????????ans?+=?fmax(0,?prices[i]?-?prices[i?-?1]);
????}

????return?ans;
}

「C++」

int?maxProfit(vector<int>&?prices)?{
????int?ans?=?0;
????for?(int?i?=?1;?i?<?prices.size();?++i)?{
????????ans?+=?max(0,?prices[i]?-?prices[i?-?1]);
????}

????return?ans;
}

「Java」

int?maxProfit(int[]?prices)?{
????int?ans?=?0;
????for?(int?i?=?1;?i?<?prices.length;?++i)?{
????????ans?+=?Math.max(0,?prices[i]?-?prices[i?-?1]);
????}

????return?ans;
}

「Python3」

def?maxProfit(self,?prices:?List[int])?->?int:
????ans?=?0
????for?i?in?range(1,?len(prices)):
????????ans?+=?max(0,?prices[i]?-?prices[i?-?1])
????
????return?ans?

「Golang」

func?maxProfit(prices?[]int)?int?{
????ans?:=?0
????for?i?:=?1;?i?<?len(prices);?i++?{
????????profit?:=?prices[i]?-?prices[i-1]
????????if?profit?>?0?{
??????????ans?+=?profit
????????}????????
????}?
????
????return?ans???
}

「复杂度分析」

时间复杂度:「O(n)」,其中 n 是数组的长度,需要遍历一遍数组。

空间复杂度:「O(1)」,未开辟额外的空间。

往期贪心算法精彩回顾

如何让贪心的小朋友更开心

动态规划经典题之最长上升子序列最终版

更多精彩

关注公众号「程序员小熊」

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-19 12:18:53  更:2021-08-19 12:19:21 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 20:29:25-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码