关注网站怎么做,南京 百度 网站建设,淄博网站建设专家,上海十大外贸公司理论基础
#什么是贪心
贪心的本质是选择每一阶段的局部最优#xff0c;从而达到全局最优。
这么说有点抽象#xff0c;来举一个例子#xff1a;
例如#xff0c;有一堆钞票#xff0c;你可以拿走十张#xff0c;如果想达到最大的金额#xff0c;你要怎么拿#xff…理论基础
#什么是贪心
贪心的本质是选择每一阶段的局部最优从而达到全局最优。
这么说有点抽象来举一个例子
例如有一堆钞票你可以拿走十张如果想达到最大的金额你要怎么拿
指定每次拿最大的最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子你有一个背包体积为n如何把背包尽可能装满如果还每次选最大的盒子就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
#贪心的套路什么时候用贪心
很多同学做贪心的题目的时候想不出来是贪心想知道有没有什么套路可以一看就看出来是贪心。
说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优推出整体最优。
那么如何能看出局部最优是否能推出整体最优呢有没有什么固定策略或者套路呢
不好意思也没有 靠自己手动模拟如果模拟可行就可以试一试贪心策略如果不可行可能需要动态规划。
有同学问了如何验证可不可以用贪心算法呢
最好用的策略就是举反例如果想不到反例那么就试一试贪心吧。
可有有同学认为手动模拟举例子得出的结论不靠谱想要严格的数学证明。
一般数学证明有如下两种方法
数学归纳法反证法
看教课书上讲解贪心可以是一堆公式估计大家连看都不想看所以数学证明就不在我要讲解的范围内了大家感兴趣可以自行查找资料。
面试中基本不会让面试者现场证明贪心的合理性代码写出来跑过测试用例即可或者自己能自圆其说理由就行了。
举一个不太恰当的例子我要用一下11 2但我要先证明11 为什么等于2。严谨是严谨了但没必要。
虽然这个例子很极端但可以表达这么个意思刷题或者面试的时候手动模拟一下感觉可以局部最优推出整体最优而且想不到反例那么就试一试贪心。
例如刚刚举的拿钞票的例子就是模拟一下每次拿做大的最后就能拿到最多的钱这还要数学证明的话其实就不在算法面试的范围内了可以看看专业的数学书籍
所以这也是为什么很多同学通过accept了贪心的题目但都不知道自己用了贪心算法因为贪心有时候就是常识性的推导所以会认为本应该就这么做
那么刷题的时候什么时候真的需要数学推导呢
例如这道题目链表环找到了那入口呢 (opens new window)这道题不用数学推导一下就找不出环的起始位置想试一下就不知道怎么试这种题目确实需要数学简单推导一下。
#贪心一般解题步骤
贪心算法一般分为如下四步
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
这个四步其实过于理论化了我们平时在做贪心类的题目 很难去按照这四步去思考真是有点“鸡肋”。
做题的时候只要想清楚 局部最优 是什么如果推导出全局最优其实就够了。
#总结
本篇给出了什么是贪心以及大家关心的贪心算法固定套路。
不好意思了贪心没有套路说白了就是常识性推导加上举反例。
最后给出贪心的一般解题步骤大家可以发现这个解题步骤也是比较抽象的不像是二叉树回溯算法给出了那么具体的解题套路和模板。 53. 最大子数组和 给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 子数组 是数组中的一个连续部分。 示例 1 输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6 。示例 2 输入nums [1]
输出1示例 3 输入nums [5,4,-1,7,8]
输出23提示 1 nums.length 105-104 nums[i] 104 进阶如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的 分治法 求解。 class Solution(object):def maxSubArray(self, nums)::type nums: List[int]:rtype: inttime: O(n)space: O(1)max_current nums[0]max_global nums[0]for i in range(1, len(nums)):max_current max(nums[i], max_current nums[i])if max_current max_global:max_global max_currentreturn max_global
