草庐IT

每日算法题之买卖股票的最好时机(一)

loongnuts 2023-04-19 原文

买卖股票的最好时机(一)

描述

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润，请返回0
3.假设买入卖出均无手续费

解法一：暴力(常规大循环解决)

思路步骤：

最显而易见的解法，当然可能并不是最优的解法
声明变量ans=0存放最终答案
两层for循环，分别找到数组中最大的差值，表示利润最大化
比较并更新ans的值
返回ans即为答案

代码

int ans = 0;
for (int i = 0; i < prices.length; i++) {
    for (int j = i+1; j < prices.length; j++) {
        if (prices[j] - prices[i] > ans) {
            ans = prices[j] - prices[i];
        }
    }
}
return ans;

解法二：关于解法一的优化：贪心算法

思路

我们假设自己购买股票，为了达到利润最大化，必然会挑一个历史最低点进行买入,
声明最低价格minPrices
那么在第i天卖出的股票的利润就是Prices[i]-minPrices
一趟遍历记录最低点即可

代码

package esay.JZ63买卖股票的最好时机1;

public class Solution {
    /**
     * @param prices int整型一维数组
     * @return int整型
     */
    public int maxProfit(int[] prices) {
        // write code here
        //1、暴力算法
        /*int ans = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i+1; j < prices.length; j++) {
                if (prices[j] - prices[i] > ans) {
                    ans = prices[j] - prices[i];
                }
            }
        }
        return ans;*/

        //2、贪心算法
        int minPrice = Integer.MAX_VALUE;
        int ans = 0;
        for (int i = 0; i < prices.length; i++) {
            if (minPrice > prices[i]) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > ans) {
                ans = prices[i] - minPrice;
            }
        }
        return ans;
    }
}
每日买卖prices解法ansJava

有关每日算法题之买卖股票的最好时机(一)的更多相关文章

  1. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  2. ruby-on-rails - lovdbyless VS 社区引擎……哪个最好？ - 2

    随着ruby​​被引入为新的编程救世主，我想知道是否有人基于易用性、运行所需的资源、可用性和易定制性而有偏好。两者有更好的吗？ 最佳答案 好吧，任何基于Rails的社交网络应用程序的比较都应该包括insoshi(http://portal.insoshi.com/)。话虽这么说，这三个都非常相似，区别在于实现细节。Lovd和Insoshi都是完整的Rails应用程序；它旨在供您将它们用作入门工具包，并使用您自己的自定义功能对其进行扩展。另一方面，CommunityEngine是一个Rails插件。这意味着您可以更轻松地向现有Rail

  3. 100个python算法超详细讲解：画直线 - 2

    1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva

  4. ruby - 在 Ruby 中实现 Luhn 算法 - 2

    我一直在尝试用Ruby实现Luhn算法。我一直在执行以下步骤:该公式根据其包含的校验位验证数字，该校验位通常附加到部分帐号以生成完整帐号。此帐号必须通过以下测试:从最右边的校验位开始向左移动，每第二个数字的值加倍。将乘积的数字(例如，10=1+0=1、14=1+4=5)与原始数字的未加倍数字相加。如果总模10等于0(如果总和以零结尾)，则根据Luhn公式该数字有效；否则无效。http://en.wikipedia.org/wiki/Luhn_algorithm这是我想出的:defvalidCreditCard(cardNumber)sum=0nums=cardNumber.to_s.s

  5. Ruby 斐波那契算法 - 2

    下面是我写的一个计算斐波那契数列中的值的方法:deffib(n)ifn==0return0endifn==1return1endifn>=2returnfib(n-1)+(fib(n-2))endend它工作到n=14，但在那之后我收到一条消息说程序响应时间太长(我正在使用repl.it)。有人知道为什么会这样吗？ 最佳答案 Naivefibonacci进行了大量的重复计算-在fib(14)fib(4)中计算了很多次。您可以将内存添加到您的算法中以使其更快:deffib(n,memo={})ifn==0||n==1returnnen

  6. ruby-on-rails - 使用 stock_quote gem 中的股票报价作为 acts_as_taggable gem 中的标签？ - 2

    所以我正在使用acts_as_taggablegem提供的标签。这些帖子是我正在标记的内容。我怎么能说类似=>的东西(这里是伪代码)ifacollectionofPostshasatagwithacorrespondingStockQuote,displaythestockquote所以现在我有一个acts_as_taggable的Post资源。这是我的帖子索引操作现在的样子:defindex@stock=StockQuote::Stock.quote("symbol")ifparams[:tag]@posts=Post.tagged_with(params[:tag])else@po

  7. ruby-on-rails - Rails add_index 算法 : :concurrently still causes database lock up during migration - 2

    为了防止在迁移到生产站点期间出现数据库事务错误，我们遵循了https://github.com/LendingHome/zero_downtime_migrations中列出的建议。(具体由https://robots.thoughtbot.com/how-to-create-postgres-indexes-concurrently-in概述)，但在特别大的表上创建索引期间，即使是索引创建的“并发”方法也会锁定表并导致该表上的任何ActiveRecord创建或更新导致各自的事务失败有PG::InFailedSqlTransaction异常。下面是我们运行Rails4.2(使用Acti

  8. ruby - 编写一个 ruby​​ 命令行应用程序；最好的方法是做到这一点？ - 2

    我有一个正在开发的命令行Ruby应用程序，我想允许它的用户提供将在部分过程中作为过滤器运行的代码。基本上，应用程序是这样做的:读入一些数据如果指定了过滤器，则使用它来过滤数据处理数据我希望过滤过程(第2步)尽可能灵活。我的想法是，用户可以提供一个Ruby文件，该文件设置一个已知常量以指向实现我定义的接口(interface)的对象，例如:#user'sfilterclassMyFilterdefdo_filter(array_to_filter)filtered_array=Array.new#domyfilteringonarray_to_filterfiltered_arrayen

  9. ruby - 趋势算法 - 2

    我正在开发一个类似微论坛的项目，其中一个特殊用户发布一条快速(接近推文大小)的主题消息，订阅者可以用他们自己的类似大小的消息来响应。直截了当，没有任何形式的“挖掘”或投票，只是每个主题消息的响应按时间顺序排列。但预计会有很高的流量。我们想根据它们引起的响应嗡嗡声来标记主题消息，使用0到10的等级。在谷歌上搜索了一段时间的趋势算法和开源社区应用示例，到目前为止已经收集到两个有趣的引用资料，但我还没有完全理解它们:Understandingalgorithmsformeasuringtrends，关于使用基线趋势算法比较维基百科页面浏览量的讨论，在SO上。TheBritneySpearsP

  10. Ruby - 不支持的密码算法 (AES-256-GCM) - 2

    我收到错误:unsupportedcipheralgorithm(AES-256-GCM)(RuntimeError)但我似乎具备所有要求:ruby版本:$ruby--versionruby2.1.2p95OpenSSL会列出gcm:$opensslenc-help2>&1|grepgcm-aes-128-ecb-aes-128-gcm-aes-128-ofb-aes-192-ecb-aes-192-gcm-aes-192-ofb-aes-256-ecb-aes-256-gcm-aes-256-ofbRuby解释器:$irb2.1.2:001>require'openssl';puts

随机推荐