记录一些自己学到的知识，同时希望能帮到各位小伙伴们学习一些东西，如果有什么写的不好的地方或者需要更改的，还请大佬指正
贪心算法(又称贪婪算法)是指：在每一步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。
贪心算法每一步必须满足一下条件：
1、可行的：即它必须满足问题的约束。
2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。
3、不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。
因此，贪心算法说白了就是在子问题的每一步中取最优解，然后把每一步的最优解合成原来问题的解，虽然最终答案可能不是最优的，但与最中答案很接近。
以下是关于贪心算法的几道题，可以参考着学习一下
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例1
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例2
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
思路:
对于这种题型，就用到了贪心的思想。比如在示例1中，刚开始nums[0]的值为2，可以跳两步，可以调到nums[1]值为3的位置，也可以跳到nums[2]值1的地方，我们会选择让其跳到下标为1的地方，因为跳到此处下标值更大，跳的更远，我们只需考虑每次能跳到的最远下标即可，因此最后所需的步也可能就最少。那么怎么判定达到终点呢?
最初位置下标为0，而此时nums[0]为2，也就是说能跳到下标为2的位置结束，当跳到下标为1时，可以跳三步到达终点，所以我们是通过数组下标i+nums[i]来计算其能跳到的位置的。
因此我们的代码如下:
|
1 |
<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">canJump</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">if</span><span class="token punctuation">(</span>nums<span class="token punctuation">.</span>length<span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span> <span class="token keyword">int</span> coverage<span class="token operator">=</span>nums<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator"><=</span>coverage<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{<!-- --></span> coverage<span class="token operator">=</span><span class="token class-name">Math</span><span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>coverage<span class="token punctuation">,</span>i<span class="token operator">+</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>coverage<span class="token operator">>=</span>nums<span class="token punctuation">.</span>length<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> |
因此本题就解决了。
来让我们看下一道题。
问题
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例1
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例2
输入: nums = [2,3,0,1,4]
输出: 2
分析:
首先这道题是对跳跃游戏 | 的延伸，只不过|是让我们求能不能到跳到最后，而这个是让我们求最少需要几步到达最后一个位置，同样也用到了贪心的思想。
|
1 |
<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">jump</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">if</span><span class="token punctuation">(</span>nums<span class="token punctuation">.</span>length<span class="token operator">==</span><span class="token number">1</span><span class="token operator">||</span>nums<span class="token punctuation">.</span>length<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">int</span> count<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">int</span> temp<span class="token operator">=</span>nums<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> cur<span class="token operator">=</span>temp<span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator"><=</span>temp<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{<!-- --></span> <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token operator">>=</span>nums<span class="token punctuation">.</span>length<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> count<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span> cur<span class="token operator">=</span>cur<span class="token operator"><=</span>i<span class="token operator">+</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">?</span>i<span class="token operator">+</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">:</span>cur<span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span>temp<span class="token punctuation">)</span><span class="token punctuation">{<!-- --></span> temp<span class="token operator">=</span>cur<span class="token punctuation">;</span> count<span class="token operator">++</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> count<span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> |
这道题到这里也就结束了，||和|的区别在于第二题是当
i到达第一个区间再更新区间，因为如果nums[0]=2,而nums[1]=4,nums[2]=6时，显然要到下标为2再跳，因此用cur保存最大值，将nums[2]+2赋值给temp。
本文到这里就先结束了，还会记录其他的题以及题型，如果有什么写的不对的地方，还希望各位大佬看到后指正。
微信扫一扫打赏
支付宝扫一扫打赏
