贪心算法 遵循某种规律,不断贪心的选取当前最优策略的算法设计方法考虑条件,只有证明当前最优解是全局最优解时,贪心成立高频面试问题考察思维方式, 数据结构简单即可解决找不到反例的情况 55. 跳越游戏 I (Medium) 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。示例 1： 输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳...
贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。 比如说一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的。 什么是贪心选择性质呢，简单说就是：每一步都做出一个局部最优的选择，最终的结果就是全局最优。注意...
一.贪心算法 对于一些最优解问题，每一步都做当前的最优选择，最后得到的选择结果就是最终问题的最优解，这样的问题就适用贪心算法。贪心算法在每一步做出局部的最优选择，最后得到整个问题的最优解。显然，实际问题中存在大量问题并不是每一步最优就能最终最优的，如01背包问题，因此贪心算法解决问题简化了解决方案，但是得到的最终结果的可信度不如动态规划算法或者分治算法高，往往考虑不够全面。问题能否使用贪心算法解决要根...
leetcode03_贪心算法 在贪婪算法(greedy method) 中，我们要逐步构造一个最优解。每一步，我们都在一定的标准下，做出一个最优决策。做出决策所依据的标准称为贪心准则(greedy criterion)。贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解例1.钞票支付问题 假设1元、2元、5元、10元、20元、50元、100元的纸币。现在要用这些钱来找给顾...
贪心算法 如果问题的最优解包含两个（或更多）子问题的最优解，且子问题多有重叠，我们考虑使用动态规划算法。 而如果问题经过贪心选择后，只剩下一个子问题，且具有优化子结构，那么可以使用贪心算法。 贪心选择性：每一步贪心选出来的一定是原问题的最优解的一部分（即每次求的最优解一定会被更大的父问题选择，即被父节点选择） 关键点就在于这个性质，就是说怎么证明父状态转移到的这唯一一个子状态就是父状态要使用的最优解 最...
背包问题： 背包问题就是在背包载荷已经给定的情况下，每次把单位价值最高的物品放入背包中知道所有物品放完或者背包中物品的重量达到给定载荷。 一般是用结构体来做； for(int i=0;i<n;i++){v[i]=p[i]/w[i]; //p是每个物品的价值，w是每个物品的重量 } //然后对物品的单位价值由高到低排序 W=0,P=0; //设定背包一开始的包内物品重量和价值 while(W<M){if(M-W-w[i]>=0){ //如果这个物品可以完全放进背包里且不超载W+=w[i];P+=p[i];...
题目描述（传送门） 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1： 输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2： 输入：nums = [3,2,1,0,4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是...
贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本...
/*疯狂的牛牛n个隔间 c头牛使每两头牛之间的最小距离最大化 思路：转化为判定性问题判断间距d是否可行；对间距d采取二分策略 */ #include<stdio.h> #include<algorithm> using namespace std;const int MAXN = 1e5 + 10; int arr[MAXN];bool judge(int n, int m, int distance){int current = arr[0];//第一头牛放在第一个位置 int number = 1;//记录放的牛的数量for(int i = 1;i < n; ++i){if(arr[i] - current >= distance){n...
前言 ??顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。 leetcode 455??因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。...
教室调度问题 假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。 你没法让这些课都在这间教室上，因为有些课的上课时间有冲突。 你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢? 这个问题好像很难，不是吗?实际上，算法可能简单得让你大吃-一惊。具体做法如下。 选出结束最早的课，它就是要在这间教室上的第一-堂课。接下来，必须选择第一-堂 课结束后才开始的课。同样，你选择结束最早的课，...
455.分发饼干 // 时间复杂度：O(N*logN) 因为谷歌排序为快排，火狐为归并，都是O(N*logN) var findContentChildren = function(g, s) {const sortFunc = function(a,b){return a-b}g.sort(sortFunc)s.sort(sortFunc)let i = 0s.forEach(n=>{if(n>=g[i]){i+=1}})return i };122. 买卖股票的最佳时机 II /** 时间复杂度：O(n) for循环* 空间复杂度：O(1) 没有线性增长，是常量*/ var maxProfit = function(prices) {let profit = 0f...
题目 有一个二维矩阵 A 其中每个元素的值为 0 或 1 。 移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。 在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。 返回尽可能高的分数。题解 这个题是使用贪心算法的思想做解的 由于题目最后要的结果是二进制转换为十进制之后的结果，所以我们为了让结果最大化 在行的开头必须为1，之后多多...
问题描述： 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应 在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置，编程计算最少加油次数。并证明算法能产生一个最优解。 在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置，编程计算最少加油次数。并证明算法能产生一个最优解。 要求： 输入：第一行有2个正整...
思路 这道题其实主要的难点是如何排序。 排序之后贪心就非常简单了。 考虑贪心邻项交换 设 si=∏j=0iajs_i=\prod\limits_{j=0}^{i}a_jsi?=j=0∏i?aj?。 首先考虑交换前，第 iii 个上的值是 si?1bi\frac {s_{i-1}}{b_i}bi?si?1??，第 i+1i+1i+1个 是 si?1aibi+1\frac {s_{i-1}\times a_i}{b_{i+1}}bi+1?si?1?ai?? ans1=max?(si?1bi,si?1aibi+1)ans_1=\max(\frac {s_{i-1}}{b_i},\frac {s_{i-1}\times a_i}{b_{i+1}})ans1?=max(bi?si...