首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

「经典题目回顾」贪心算法:买卖股票最佳时机II

春节前最后一个周末,明天还是工作日,哈哈,我们来复习一下贪心算法吧! 贪心经常被大多数同学忽略算法,都感觉贪心嘛,不就是常识,有啥可学贪心其实是很难,难就难在没有套路,是的,贪心无套路!...动态规划我能总结出动规五部曲,二叉树我们总结出递归三部曲,回溯算法我也能总结出回溯三部曲。 但贪心真的总结不出来什么规律,题目往往巧出其不意。...来回顾一下这道题贪心算法:买卖股票最佳时机II 如果想到其实最终利润是可以分解,那么本题就很容易了! 局部最优:收集每天正利润,全局最优:求得最大利润。...= max(prices[i] - prices[i - 1], 0); } return result; } }; 时间复杂度O(n) 空间复杂度O(1) 贪心代码很简单...,而且比动规解法更优!

33210

贪心算法如何贪心

在前面学习最短路径和最小生成树时候,我们发现Dijkstra算法,Prim算法,Kruskal算法都是属于典型贪心算法应用。...这篇文章就是对于贪心算法入门介绍 贪心算法 贪心算法(又称贪婪算法)是指在对问题求解时,总是做出在当前看来是最好选择。也就是说,不从整体最优上加以考虑,他所做出是在某种意义上局部最优解。...我们通过下面两个例题来看下什么时候选用贪心算法求解。 例题一 题目:给出0-9数字任意个,比如数字0两个,数字1两个,数字5三个。让你用所给数据组成一个最小值,0不能放在首位。...例题二 题目:假如现在仓库囤有一批同款产品不同规格货物,货A是30吨,货B是50吨,货C是30吨,总价值分别是,30万,50万,30万,货物A,B,C不可分解。现在有人 准备收购60吨。...只要能满足贪心算法两个性质: 贪心选择性质和最优子结构性质,贪心算法就可以出色地求出问题整体最优解。即使某些问题,贪心算法不能求得整体最优解,贪心算法 也能求出大概整体最优解。

1.1K10
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    算法贪心算法

    贪心算法 概念解释 贪婪算法(贪心算法)是指在对问题求解时候,每一步选择都采用最好或者最优(即最有利)选择,从而希望能够导致结果是最好或者最优算法。...贪心算法所得到结果往往不是最优结果(有时候会是最优解),但是都是相对近似(接近)最优解结果。 贪心算法并没有固定解发框架,算法关键是贪心策略选择,根据不用问题选择不同策略。...解题思路: 用贪心算法思想,每一步都用能用最大纸币即可。...会提示找不开,这种情况下我们使用贪心算法得到答案就不是最优解,因为我们一直在尝试用最大纸币来尽可能使用最少张数来解决问题。这就不是最优贪心算法没有固定框架,关键是看你怎么选择。...这种情况就需要调整策略,甚至,就不适用贪心算法贪心算法是尽力找到近似的最优解,注重是速度,不是精准度,并不是说一定能找到合适解,或是一定能找到解 。 对应问题根据情况不同选择合适算法解决。

    25530

    贪心算法

    贪心算法:分阶段工作,在每个阶段做出当前最好选择,从而希望得到结果是最好或最优算法贪心算法与动态规划不同在于它对每个子问题解决方案都做出选择,不能回退。...动态规划则会保存以前运算结果,并根据以前结果对当前进行选择,有回退功能。 任务调度问题(简单) 这是一个经典简单贪心问题,只是题目有点长需要认真读。...解决这个问题,重点要想好贪心策略: 阶段性:每个时间表选择哪一个任务。 贪心策略:根据“误时惩罚”对任务进行排序,优先排惩罚大任务,如果这个时间点已经被占了,依次向前找,判断任务是否能安排?...; 54 bubble(); 55 range(); 56 printf("%d",totle); 57 return 0; 58 } 区间覆盖(开始没思路) 感觉这个贪心策略比较难想...56 */ 最近做了一些贪心算法题,感觉贪心算法主要是根据问题要求想出贪心策略,上面提到了没有涉及到什么数据结构和高精度问题。所以用到最多就是排序。

    53630

    算法基础-贪心

    区间问题 01.区间选点 题目描述 给定 N 个闭区间 [a_i,b_i],请你在数轴上选择尽量少点,使得每个区间内至少包含一个选出点。 输出选择最小数量。...位于区间端点上点也算作区间内。 输入格式 第一行包含整数 N,表示区间数。 接下来 N 行,每行包含两个整数 a_i,b_i,表示一个区间两个端点。...输出格式 输出一个整数,表示所需最小数量。...b_i\le 10^9 输入样例: 3 -1 1 2 4 3 5 输出样例: 2 题解 时间复杂度 O(nlogn) 证明: 证明ans$$\le$$cnt :cnt 是一种可行方案, ans是可行方案最优解...核心思想 将每个区间按照右端点从小到大进行排序 从前往后枚举区间,end值初始化为无穷小 如果本次区间不能覆盖掉上次区间右端点, ed < range[i].l 说明需要选择一个新点, res ++

    47620

    贪心算法

    http://blog.csdn.net/xywlpo/article/details/6439048 贪心算法设计思想          贪心算法在解决问题策略上目光短浅,只根据当前已有的信息就做出选择...换言之,贪心法并不是从整体最优考虑,它所做出选择只是在某种意义上局部最优。贪心算法对于大部分优化问题都能产生最优解,但不能总获得整体最优解,通常可以获得近似最优解。...=S+{x};           C=C-{x};     }    return S; 贪心基本要素       对于一个具体问题,怎么知道是否可用贪心算法解此问题,以及能否得到问题最优解呢...这个问题很难给予肯定回答。       但是,从许多可以用贪心算法求解问题中看到这类问题一般具有2个重要性质:贪心选择性质和最优子结构性质。...这是贪心算法可行第一个基本要素。 贪心算法以迭代方式作出相继贪心选择,每作一次贪心选择就将所求问题简化为规模更小子问题。

    1.5K20

    算法专题】贪心算法

    贪心算法 贪心算法介绍 什么是贪心算法呢?...首先,我们需要知道贪心策略,即解决问题策略,将局部最优转变为全局最优; 把解决问题过程分为若干步; 解决每一步时候,都选择当前看起来"最优"解法; "希望"得到全局最优解 贪心算法特点: 提出贪心策略...贪心策略:按照题目的要求,重新定义一个新排序规则,然后排序即可。...最长递增子序列(贪心算法) 题目链接 -> Leetcode -300.最长递增子序列 Leetcode -300.最长递增子序列 题目:给你一个整数数组 nums ,找到其中最长严格递增子序列长度。...买卖股票最佳时机Ⅱ(贪心算法) 题目链接 -> Leetcode -122.买卖股票最佳时机Ⅱ Leetcode -122.买卖股票最佳时机Ⅱ 题目:给你一个整数数组 prices ,其中 prices

    10410

    【基础算法贪心算法

    贪心算法又称贪婪算法,是一种常见算法思想。贪心算法优点是效率高,实现较为简单,缺点是可能得不到最优解。 贪心算法基本思想 贪心算法就是在求解问题时,总是做出当前看来最好选择。...贪心算法每一步只考虑局部最优解,所以在处理问题时候可能得不到整体最优解。要使贪心算法得到最优解,问题应具备以下性质: 贪心选择性质 所求问题整体最优解可以通过一系列局部最优解得到。...实际应用中许多问题都可以使用贪心算法得到最优解,即使得不到最优解,也能得到最优解近似解。所以在解决一般性问题时,我们可以大胆尝试使用贪心算法。...哈夫曼编码算法、图算法最小生成树Prim算法和Kruskal算法,以及计算图单源最短路径Dijkstra算法等都是基于贪心算法思想设计。...但是随着广播台增多,消耗时间将呈指数级增长,穷举法将不是可行方案。 使用贪心算法进行解决。 我们通过一个简单例子来理解贪心算法精髓。

    31340

    贪心算法

    贪心算法基本思想: ------求解最优化问题算法包含一系列步骤 ------每一部都有一组选择 ------做出当前看来最好选择 ------希望通过做出局部优化选择达到全局优化选择 -...-----贪心算法不一定总产生优化解 ------贪心算法是否产生优化解,需要严格证明 贪心算法产生优化解条件 ------贪心选择性:若一个优化问题全局优化解可以通过局部优化选择得到,则该问题成为具有贪心选择性...------优化子结构 与动态规划方法比较 ------动态规划方法可用条件:(1)优化子结构(2)子问题重叠性(3)子问题空间小 ------贪心法可用条件:(1)优化子结构(2)贪心选择性...这是一种典型贪心算法,它只顾眼前,但能得到最优解。 (2)部分背包问题。有n个物体,第i个物体重量为wi,价值为vi,在总重量不超过C情况下让总价值尽量高。...一种直观贪心策略是:优先拿“价值除以重量值”最大,直到重量和正好为C。

    94720

    贪心算法

    贪婪算法 贪心算法(Greedy Algorithm) 简介贪心算法,又名贪婪法,是寻找最优解问题常用方法,这种方法模式一般将求解过程分成若干个步骤,但每个步骤都应用贪心原则,选取当前状态下最好/最优选择...{看着这个名字,贪心,贪婪这两字内在含义最为关键。...index = i; } } } return index; } 有了物品,有了方法,下面就是将两者结合起来贪心算法...按照贪心算法三个步骤:1.41分,局部最优化原则,先找给顾客25分;2.此时,41-25=16分,还需要找给顾客10分,然后5分,然后1分;3.最终,找给顾客一个25分,一个10分,一个5分,一个1分...^_^;总结:贪心算法优缺点优点:简单,高效,省去了为了找最优解可能需要穷举操作,通常作为其它算法辅助算法来使用;缺点:不从总体上考虑其它可能情况,每次选取局部最优解,不再进行回溯处理,所以很少情况下得到最优解

    97911

    算法】之贪心算法

    欢迎记录下你那些努力时刻(算法学习知识点/算法题解/遇到算法bug/等等),在分享同时加深对于算法理解,同时吸收他人奇思妙想,一起见证技术er成长~ 目录 贪心算法 算法知识点 解题步骤...算法题目来源 算法题目描述 做题思路 代码 运行结果 读书笔记 ---- 贪心算法 算法知识点 贪心算法(又称贪婪算法)是指在对问题求解时,总是做出在当前看来是最好选择。...解题步骤 1.分解:将原问题分解为若干个相互独立阶段 2.解决:在每个相互独立阶段进行贪心选择,求出局部最优解 3.合并:将各个阶段解合并为原问题算法题目来源 860....柠檬水找零 - 力扣(LeetCode) 算法题目描述 在柠檬水摊上,每一杯柠檬水售价为 5 美元。顾客排队购买你产品,(按账单 bills 支付顺序)一次购买一杯。...贪心算法采用自顶向下,以迭代方法做出相继贪心选择,每做一次贪心选择,就将所求问题简化为一个规模更小子问题,通过每一步贪心选择,可得到问题一个最优解。

    57330

    贪心算法+回溯算法

    贪心算法 先来比较一下贪心算法和动态规划 贪心算法是指在对问题求解时,总是做出在当前看来是最好选择,不考虑整体,只考虑局部最优,所以它不一定能得到最优解; 动态规划则是每个步骤都要进行一次选择,但选择通常要依赖子问题解...,是通过求解小问题取解决 如果理解了最优子结构,则会发现贪心算法和动态规划都利用了最优子结构性质 实现该算法过程 从问题某一初始解出发 while 能朝给定总目标前进一步 do 求出可行解一个解元素...由所有解元素组合成问题一个可行解 典型可用贪心来解问题有 最小生成树、分数背包问题(类似0-1背包问题,只不过可以取物体一部分) 用分数背包问题举个例子 W=30(所选物体不能超过30)...物品:A B C 重量:20 5  20 价值:40 20 20 这个时候贪心选择肯定是选择单位价值量最高 所以先选择B,再选择A  再从C中选择5   这时价值肯定最大 但贪心算法一开始就说了...,并不保证最优解,所以有时会配合随机算法算法导论第三版第五章有讲)使用  一般来说贪心算法代码比动态规划简单多 ---- 回溯算法 回溯法概念 通常采取深度遍历形式,按照某种规则能够避免某些不必要搜索穷举式搜索

    1.4K91

    贪心算法(Java)

    贪心算法(Java) 0、写在前面 1、贪心算法基本要素 1.1 贪心选择性质 1.2 最优子结构性质 1.3 贪心算法与动态规划算法差异 2、贪心算法特点 3、贪心正确性证明 4、活动安排问题...也就是说贪心算法并不从整体最优考虑,它所作出选择只是在某种意义上局部最优选择。当然,希望贪心算法得到最终结果也是整体最优。...1.1 贪心选择性质 所谓贪心选择性质是指所求问题整体最优解可以通过一系列局部最优选择,即贪心选择来达到。这是贪心算法可行第一个基本要素,也是贪心算法与动态规划算法主要区别。...动态规划算法通常以自底向上方式解各子问题,而贪心算法则通常以自顶向下方式进行,以迭代方式作出相继贪心选择,每作一次贪心选择就将所求问题简化为规模更小子问题。...问题最优子结构性质是该问题可用动态规划算法贪心算法求解关键特征。 1.3 贪心算法与动态规划算法差异 贪心算法和动态规划算法都要求问题具有最优子结构性质,这是2类算法一个共同点。

    53710

    经典算法贪心算法

    什么是贪心算法?   贪心算法,又称贪婪算法(Greedy Algorithm),是指在对问题求解时,总是做出在当前看来是最好选择。...这种“眼下能够拿到就拿”策略是这类算法名称来源。   贪心算法没有固定算法框架,算法设计关键是贪心策略选择。...把子问题解局部最优解合成原来解问题一个解。 贪心算法适用问题   贪心策略适用前提是:局部最优策略能导致产生全局最优解。也就是当算法终止时候,局部最优等于全局最优。...贪心算法实现框架 从问题某一初始解出发; while (能朝给定总目标前进一步) { 利用可行决策,求出可行解一个解元素; } 由所有解元素组合成问题一个可行解; 贪心策略选择   因为用贪心算法只能通过解局部最优解策略来达到全局最优解...如果确定可以使用贪心算法,那一定要选择合适贪心策略; 贪心算法几个例子 1.

    1.7K30

    疯子算法总结(四)贪心算法

    一、贪心算法 解决最优化问题算法一般包含一系列步骤,每一步都有若干选择。对于很多最优化问题,只需要采用简单贪心算法就可以解决,而不需要采用动态规划方法。...贪心算法使所做局部选择看起来都是当前最佳,通过局部最优化选择来产生全局最优解。本文将介绍贪心算法理论基础和一些简单应用。...在求最优解问题过程中,依据某种贪心标准,从问题初始状态出发,直接去求每一步最优解,通过若干次贪心选择,最终得出整个问题最优解,这种求解方法就是贪心算法。...贪心算法理论基础 关于贪心算法有一种理论可用于确定在何时使用贪心算法能给出最优解,虽然这种理论并没有包含贪心算法所适用所有情况,但确实描述了许多非常有意义情况。...7.区间覆盖问题 POJ1328是一道经典贪心算法例题。题目大意是假设海岸线是一条无限延伸直线。陆地在海岸线一侧,而海洋在另一侧。每一个小岛屿是海洋上一个点。

    72720

    常用算法贪心算法

    思路:求解问题时,总是选当前最好选择,不从整体上考虑。因而选用贪心算法必须保证当前选最好必定是整体最好。 示例 分发饼干 假设你是一位很棒家长,想要给你孩子们一些小饼干。...换句话说就是贪心选择执行n个不一样任务,使得CPU能够充分利用 要选择先执行任务,得考虑如何使得当前选择整体是最优,加入随便选择一个任务A执行,当存在一个任务B它任务数比选择任务数要多时,这意味着...list.add(top); for (int i=0;i<maxLength;i++) { //贪心选择没有执行过...maxNumsTaskIndex]--; } return maxNumsTaskIndex; } } 复制代码 当然如果只要解决问题,可以直接计算出结果 还是使用贪心策略来作为逻辑考虑...}else{ break; } } return Math.max(tasks.length,(taskArr[25]-1)*(n+1)+m); } 复制代码 附录 贪心算法思路

    62020

    贪心算法问题-LeetCode 55、45(贪心算法,跳跃问题)

    贪心算法问题:LeetCode #55 #45 1 编程题 【LeetCode #55】跳跃游戏 给定一个非负整数数组,你最初位于数组第一个位置。...算法原理: 遍历整个nums数组,每次计算从i位置最大可能到达距离,然后依次更新这个最大值,如果最大值大于nums大小nums.size(),那么就返回true, 否则返回false....数组中每个元素代表你在该位置可以跳跃最大长度。 你目标是使用最少跳跃次数到达数组最后一个位置。...说明: 假设你总是可以到达数组最后一个位置 算法原理: 由于题目中规定总能到达数组最后一个位置,因此我们在遍历数组时每次都要去找最大跳跃位置,只有到达了这个最远边界end,我们才让step进行自加...如下图,开始位置是 2,可跳范围是橙色。然后因为 3 可以跳更远,所以跳到 3 位置。 ?

    1.3K60
    领券