leetCode初级算法---买卖股票的最佳时机 II(Js版/两种思路)

逆熵元组
• 阅读 1726

最近在家待业,无聊的时候刷刷LeetCode,看到一道超级熟悉算法题。因为之前参加秋招,春招都遇到过,而且遇到过几次。反正无聊也是无聊,那就再写写吧,顺便开始写写博客(好久没写了),算这道题来写博客的原因除了这题经常看见外,另外一个重要的原因是这题够简单,能够写写玩玩。重新开始写博客要从一篇简单易懂的文章开始。一个还没毕业的大学生要开始写博客了!!!(好了,废话完毕)。
先把题目粘上吧,我懒得写(懒惰是工程师的第一生产力)

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释:
在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 
 示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
 注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
 因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。 
 示例 3: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

说说这题目,首先他要有收益的,而且要保证收益的最大化,那么如果一整个星期的价格都在下降,那么无论什么时候买都是亏损的,所以交易没有完成。
好了,开始讲讲解题思路,先讲一种简单理解一点的,如果通过画图,其实可以很容易得到答案,不信的话可以看下图(以示例一为例)
leetCode初级算法---买卖股票的最佳时机 II(Js版/两种思路)
虽然说懒惰是工程师的第一生产力,但我现在还是个学生,兴趣是学生的驱动力,所以我还是画了出来,虽然是丑了点吧,将就吧。
从画图可以发现,其实大的收益就是上升区间的总和,所以第一个上升的区间是5-1 = 4,第二个上升区间是6-3 = 3,即最大利益是4+3=7.。用js代码来计算的话,代码如下:

let arr1  = [7,1,5,3,6,4]
let arr2 = [1,2,3,4,5]
let arr3 = [7,6,4,3,1]
let arr4 = [1,7,3,4,5,2]
// arr 就是传入的数组
function maxBenefit(arr){
    let max = 0 // 最大利益
    let count = 0 // 标识符,表示有一个未计算的递增的区间
    let index = 0 // 表示上升区间的第一个元素在数组中的索引
    let length = arr.length // 这个不用解释
    for(let i = 0;i<length-1;i++ ){
         // 如果当前元素比后一个元素大,且有一个递增区间的话
         // 算这个递增区间的增值,然后与前一个递增区间相加,然后把count归0,表示区间已计算
        if(arr[i] > arr[i+1]){  
            if(count){
                max = max + arr[i] - arr[index]
                count = 0
            }  
               index = i+1    
        } if(arr[i] < arr[i+1] && !count){
            count = 1
        }
    }
    if(count){ // 如果遍历完成后,还有一个未计算的区间就计算该区间,这种情况一般是示例2的这种
       max = max + arr[length-1] -arr[index]
    }
    return max
}
console.log('测试1输出:',maxBenefit(arr1))  // 7
console.log('测试2输出:',maxBenefit(arr2))  // 4
console.log('测试3输出:',maxBenefit(arr3))  // 0
console.log('测试4输出:',maxBenefit(arr4))  // 8

第一种思路讲完了,就来讲讲第二种思路。题目说尽可能多地买卖股票,也就是说可以当天卖出并当天买进。这样就更好操作了。只要对比两天价格有赚我就卖了,例如1,2,3,对比1跟2,有赚,那么久1的时候买,2的时候卖,再对比2跟3,也是同样的道理,因为可以当天卖然后再当天买嘛。这也叫贪心策略。代码实现如下:

function maxBenefit1(arr){
  let max = 0
  let length = arr.length;
  for(let i = 0; i<length-1; i++){
    if(arr[i]<arr[i+1]){
        max = max + arr[i+1] - arr[i]
    }
  }
console.log('测试1输出:',maxBenefit1(arr1)) // 7
console.log('测试2输出:',maxBenefit1(arr2)) // 4
console.log('测试3输出:',maxBenefit1(arr3)) // 0
console.log('测试4输出:',maxBenefit1(arr4)) // 8

好了,两种接替思路都讲完了,别人能不能看懂我也不知道,反正我是能看懂。
可能会有看到这篇博客的有缘人会讲,这么简单的东西也好意思做为一篇博客。有咩所谓,我就好久没写博客,写一写玩一玩。有位不知名的网友说过,开始写博客要从一篇简单易懂的博客开始。
学生党,有其他想法或者有写错的欢迎指正~

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
11个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
4年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Leetcode Index
序:  用于记录刷题过程中难度较大或思路怪异的题目,对于常规难度一般的题就不写入我的博客了,关于效率仅是提交时击败的百分比,可能会随时间波动,仅供参考,算法优劣以时间复杂度和空间复杂度为基准。欢迎留言讨论。题目序号难度效率Leetcode42.TrappingRainWater(https://www.oschina.
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
1年前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这
美凌格栋栋酱 美凌格栋栋酱
5个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(