建外贸网站比较好的公司,建站网站主题设置不能点,wordpress反应慢,湖南seo优化公司贪心算法实际上并没有什么套路可言#xff0c;贪心的关键就在于它的思想#xff1a;
如何求出局部最优解#xff0c;通过局部最优解从而推导出全局最优解
常见的贪心算法题目
455. 分发饼干
这题的解法很符合“贪心”二字
如果使用暴力的解法#xff0c;那么本题是通过…贪心算法实际上并没有什么套路可言贪心的关键就在于它的思想
如何求出局部最优解通过局部最优解从而推导出全局最优解
常见的贪心算法题目
455. 分发饼干
这题的解法很符合“贪心”二字
如果使用暴力的解法那么本题是通过不了的
那怎么使用求得局部最优从而推导出全局最优呢
注意题意中提到了这么一句话 如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足 假如说每次分给孩子的饼干都是刚好满足这个条件也就是说让尽可能大的饼干喂给胃口大的孩子从而喂饱每一个孩子就能达到全局最优尽可能满足越多数量的孩子
所以本题的代码应该这么写
让s和g排好序后都选择从后向前遍历两个数组从而实现尽可能大的饼干喂给胃口大的孩子从而喂饱每一个孩子 public int findContentChildren(int[] g, int[] s) {Arrays.sort(g); Arrays.sort(s);int result 0;int index s.length - 1;for(int i g.length - 1;i 0;i--){if(index 0 s[index] g[i]){//注意要写上index 0防止空指针异常这里是为了避免饼干没了但是还有小孩没遍历到的情况result;index--;}}return result;}
1005. K 次取反后最大化的数组和
这题就很简单了直接上思想使用局部最优推出全局最优
局部最优使用while循环每次循环找出最小的数字并将它的符号进行转换负数变成正数/正数变成负数
全局最优返回数组的最大和
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {while(k-- 0){int min Integer.MAX_VALUE;int index 0;for(int i 0;i nums.length;i){if(nums[i] min){min nums[i];index i;}}nums[index] -nums[index];}int ans 0;for(int i :nums){ans i;}return ans;}
}
860. 柠檬水找零
这题的难度和上一题相同直接上思想使用局部最优推出全局最优
局部最优遇到账单20优先消耗美元10完成本次找零
全局最优完成找零工作 public boolean lemonadeChange(int[] bills) {int five 0;int ten 0;int twenty 0;for(int i 0;i bills.length;i){if(bills[i] 5){five;}if(bills[i] 10){if(five ! 0){--five;ten;}else{return false;}}if(bills[i] 20){if(five 3 ten 0){five - 3;twenty;}else if(five ! 0 ten ! 0){--five;--ten;twenty;}else{return false;}}}return true;}
376. 摆动序列
根据题目的意思
如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
本题我们使用的是贪心算法局部最优寻找局部的差值波动 全局最优的到最长的摆动序列
以题目提供的例子
nums [1,7,4,9,2,5] 各元素之间的差值为 (6, -3, 5, -7, 3)
所以有 6 个摆动序列
nums [1,2,3,4,5,6,7,8,9] 各元素之间的差值为 (1,1,......,1)
所以有2个摆动序列
根据这两个例子我们可以画一个图来进行解释
先来解释第二个例子 这个例子其实就是对应了如何处理数组左边或者右边的情况
题目中给出的结果是如果只有两个元素那么就算2个摆动序列
如果我们直接写死了处理数组左边或者右边的情况直接是2个摆动序列
但我们这里不写死进行判断操作根据题意我们至少需要三个数字才能确定这个数字是不是摆动序列那么我们可以理解成[1,9] [1,1,9]前面的差值为0 后面的差值为9 此时就有了差值波动
而我们初始result 1 那么此时出现了 差值波动 所以 result 后就有了2个摆动序列 然后我们再来解释第一个例子
由于需要判断前后的差值 所以此时我们设置两个变量 prediff 记录前面差值 curdiff 记录当前差值
结合第二个例子
以 1 7 4 为例子 prediff 6 而 curdiff -3
所以 prediff 0 curdiff 0 所以此时算一个摆动序列
以 7 4 9 为例子 prediff -3 而 curdiff 5
所以 prediff 0 curdiff 0 所以此时算一个摆动序列 所以我们写出代码 public int wiggleMaxLength(int[] nums) {int prediff 0;int curdiff 0;int result 1;for(int i 0;i nums.length-1;i){curdiff nums[i1] - nums[i];if(prediff 0 curdiff 0 || prediff 0 curdiff 0){result;}prediff curdiff; }return result;}
但其实这里的代码是有一点问题的我们的 prediff curdiff; 实际上要放到if里面进行判断
为什么我这里再举一个例子
假如说我们的单调递增有平坡由于prediff是实时更新的所以在 1 9 9 这个区间内会被计算成一个摆动序列 但是我们的题目中要求 如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 所以此时不能算一个摆动序列
为了解决这个问题我们直接让curdiff不再实时更新
而是当出现差值波动时 prediff 更新成当前的差值即可
最终代码如下 public int wiggleMaxLength(int[] nums) {int prediff 0;int curdiff 0;int result 1;for(int i 0;i nums.length-1;i){curdiff nums[i1] - nums[i];if(prediff 0 curdiff 0 || prediff 0 curdiff 0){result;prediff curdiff;}}return result;}
738. 单调递增的数字 题目描述
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。
本题的解题思路使用贪心算法
局部最优每当相邻的两个数字 x y 时将y后的所有数字变成9同时让x-1
全局最优返回 小于或等于 n 的最大数字且数字呈 单调递增
以332为例子 首先将数字转换成字符串然后再将字符串转换成数组方便我们进行操作
根据题意我们选择从后向前遍历当我们发现x y时使用一个变量来记录 y的下标 for(int i charNum.length - 1;i 1;i--){if(i 0 charNum[i] charNum[i-1]){start i;//体现贪心charNum[i-1]--;}else{continue;}}
最后我们直接让start后面的所有数字统统变成9 if(start ! 0){for(int i start;i charNum.length;i){charNum[i] 9;}}
然后我们再使用 Intetger.parseInt这个函数能帮助我们让字符串转换成整数
最终代码如下 public int monotoneIncreasingDigits(int n) {String num String.valueOf(n);char[] charNum num.toCharArray();int start 0;for(int i charNum.length - 1;i 1;i--){if(i 0 charNum[i] charNum[i-1]){start i;//体现贪心charNum[i-1]--;}else{continue;}}if(start ! 0){for(int i start;i charNum.length;i){charNum[i] 9;}}//确保转换成的是十进制的数字return Integer.parseInt(String.valueOf(charNum),10);}
53. 最大子数组和 根据题意找出一个具有最大和的连续子数组
那么我们只要保证和是最大的就行了
使用贪心算法 局部最优遍历数组的同时记录和的大小当和小于0时果断让和变成0
全局最优找出一个具有最大和的连续子数组
class Solution {public int maxSubArray(int[] nums) {int sum 0;int max Integer.MIN_VALUE;for(int i 0;i nums.length;i){//统计和的大小sum nums[i];//不断地比较从而得出最大和max Math.max(sum,max);if(sum 0){sum 0;}}return max;}
}
贪心算法解决股票问题
122. 买卖股票的最佳时机 II 根据题意这题使用贪心算法
局部最优利润大于0才买入当利润小于等于0立马卖掉全局最优是得到最大利润
那么根据这个思想来编写代码
for(int i 1;i price.length;i){int sum price[i] - price[i-1];if(sum 0){ans sum;}else{continue;}
} 最后贴出全部的代码
class Solution {public int maxProfit(int[] prices) {int ans 0;if(prices.length 1){return ans;}for(int i 1;i prices.length;i){int sum prices[i] - prices[i-1];if(sum 0){ans sum;}else{continue;}}return ans;}
}
思考如何从两个维度使用贪心算法解决问题
当我们遇到需要从两个维度来解决问题的题目时如果我们同时思考两个维度那么很有可能就会顾此失彼所以我们的策略就是单独来思考两个维度的其中之一最后结合两个解决方案
406. 根据身高重建队列
根据题意 “每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi 前面正好有 ki 个身高大于或等于 hi 的人”我们很容易的能推导出本题需要从两个维度来解决问题一个是身高一个是位置
那么我们就根据策略单独来思考两个维度的其中之一最后结合两个解决方案来解决问题
首先我们根据身高来进行排序
那么我们就写出一个排序算法根据身高从大到小来进行排序 Arrays.sort(people,(a,b) - {if(a[0] b[0]){return a[1] - b[1];}return b[0] - a[0];});
这个时候身高这个维度以及解决了那么就来解决位置这个维度
根据题意“前面正好有 ki 个身高大于或等于 hi 的人”可以推导出我们需要根据数组中下标为1的元素再次进行排序因为数组中下标为1代表着前面还有多少人
我们可以使用链表来进行再次排序根据数组中下标为1的元素插入到链表中对应下标的位置从而实现了两个维度 “每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi 前面正好有 ki 个身高大于或等于 hi 的人”既保证了数组是从高到低来进行排序的又满足了前面正好有 ki 个身高大于或等于 hi 的人
最后贴出完整代码
class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people,(a,b) - {if(a[0] b[0]){return a[1] - b[1];}return b[0] - a[0];});LinkedListint[] list new LinkedList();for(int[] i : people){list.add(i[1],i);}return list.toArray(new int[people.length][]);}
}
135. 分发糖果
这道题目也是经典的从两个维度来思考问题
相邻两个孩子评分更高的孩子会获得更多的糖果
相邻也就代表着有左边相邻也有右边相邻如果我们在遍历数组的过程中同时思考左右两边很容易顾此失彼那么我们还是使用我们的解题策略独来思考两个维度的其中之一最后结合两个解决方案
我这里给出一个例子 我们首先思考比左边孩子评分更高的情况再来思考比右边孩子评分更高的情况
最后得出下面这个分析过程 我们根据分析过程来编写代码最终得到如下结果
class Solution {public int candy(int[] ratings) {int[] ratingsVec new int[ratings.length];Arrays.fill(ratingsVec,1);for(int i 1;i ratings.length;i){if(ratings[i] ratings[i-1]){ratingsVec[i] ratingsVec[i-1] 1;}}for(int i ratings.length - 2;i 0;i--){if(ratings[i] ratings[i1]){ratingsVec[i] Math.max(ratingsVec[i],ratingsVec[i1] 1);}}int sum 0;for(int i : ratingsVec){sum i;}return sum;}
}
使用贪心算法解决区间问题
1.跳跃游戏问题
跳跃问题的解题关键就在于寻找到可以跳跃到达的最远下标位置
55. 跳跃游戏
根据题意数组中的每个元素代表你在该位置可以跳跃的最大长度
换言之数组中的每个元素 都代表着 该下标开始能到达最远区间是多少 那么只要区间包含到最后一个下标那么就一定可以到达最后一个下标
我们使用for循环来模拟跳跃的过程在模拟的过程中不断的更新区间在更新区间的时候我们使用贪心算法局部最优每次更新都更新最大的区间 全局最优到达最后一个下标 public boolean canJump(int[] nums) {if(nums.length 1){return true;}int cover 0;for(int i 0;i cover;i){if(i nums.length - 1){return true;}cover Math.max(cover,i nums[i]);}return false;}
45. 跳跃游戏 II
这题同样也是跳跃问题
这道题目求的是到达最后一个下标所需要的最小次数
大体思路还是一样的都是找到最远下标来解决问题
我们还是不断的寻找最远区间但是区别在于每次到达最远下标的时候都更新次数同时再次走寻找到的最远区间
当我们走到终点前的一步发现此时还是不能走到终点那么此时就应该再将步数加一次同时推出循环避免操作空指针 if(i cur){ cur next;ans;if(next nums.length - 1){break;} }
最后贴出最终代码
class Solution {public int jump(int[] nums) {int ans 0;int cur 0;int next 0;if(nums.length 1){return 0;}for(int i 0;i nums.length;i){next Math.max(next,i nums[i]);if(i cur){ cur next;ans;if(next nums.length - 1){break;} }}return ans;}
}
2.重叠区间问题
重叠区间问题的解题关键就在于找到重叠的区间后 修改区间 然后再次进行寻找
452. 用最少数量的箭引爆气球
我们想要用最少数量的弓箭引爆应可能多的气球那么我们就要尽量让气球重叠在一起
我们可以先让数组从小到大进行排序然后寻找重叠的区间当我们找到了重叠的区间就更新终止下标的位置如果没有找到那么就说明又需要一支弓箭来射爆下一组重叠的气球了 根据我画出来的这副分析图可以发现当我们找到了重叠的区间以后就应该更新原本终止下标的位置改成重叠区间内的终止下标。这样就能保证寻找到的下一个区间也是在重叠区间内否则就要让弓箭数加一
分析完成后代码就好写了 public int findMinArrowShots(int[][] points) {Arrays.sort(points,((a, b) - Integer.compare(a[0], b[0])));int ans 1;for(int i 1;i points.length;i){//没有找到重叠的区间if(points[i][0] points[i-1][1]){ans;}else{//找到了重叠的区间然后修改下标points[i][1] Math.min(points[i][1],points[i-1][1]);}}return ans;}
435. 无重叠区间
根据题意需要移除区间的最小数量使剩余区间互不重叠
翻译过来就是寻找到重叠的区间那么本题代码就和上题差不多了只不过我们要把ans放进寻找重叠区间的逻辑里面
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b) - {if(a[0] b[0]){return a[1] - b[1];}return a[0] - b[0];});int ans 0;for(int i 1;i intervals.length;i){if(intervals[i][0] intervals[i-1][1]){continue;}else{ans;//不能是intervals[i][1] intervals[i-1][1];如果前一个长 现在的短那么也会导致重复intervals[i][1] Math.min(intervals[i][1],intervals[i-1][1]);}}return ans;}
} 56. 合并区间
合并区间说白了也是寻找到重叠的区间然后再进行合并操作
那么大体的逻辑还是和上面的两题一样只不过具体操作有所不同
我们以起始下标为起点不断地寻找最远的终止下标 所以我们就需要两个变量一个起始下标 一个终止下标 当我们找不到重叠区间了说明此时我们就要更新起始下标了寻找下一个重叠区间
当我们找到重叠去建立说明此时就要更新终止下标获取最远的终止下标贪心 public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a,b) - {if(a[0] b[0]){return a[1] - b[1];}return a[0] - b[0];});LinkedListint[] list new LinkedList();//初始化int left intervals[0][0];int right intervals[0][1];for(int i 1;i intervals.length;i){//没有找到重叠区间if(intervals[i][0] right){int[] res new int[2];res[0] left;res[1] right;list.add(res);left intervals[i][0];right intervals[i][1];//找到了重叠的区间}else{right Math.max(intervals[i][1],right);}}//最后一个合并区间添加到链表里面int[] res new int[2];res[0] left;res[1] right;list.add(res);return list.toArray(new int[list.size()][]);}
3.结合跳跃问题和重叠区间问题 763. 划分字母区间
根据题意 我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中
首先我们可以遍历字符串寻找到每个字母最远能够到达的下标的位置并且记录下来 然后我们再次选择遍历字符串同时使用一个变量来记录当前能够到达的最远的位置同时通过比较不断的修改当前能够到达的最远下标的位置 当我们到达了最远下标时说明此时我们找到了区间即同一字母最多出现在一个片段中的区间内 public ListInteger partitionLabels(String s) {int[] edge new int[26];ArrayListInteger list new ArrayList();for(int i 0;i s.length();i){edge[s.charAt(i) - a] i;}int left -1;int right 0;int index 0;for(int i 0;i s.length();i){index Math.max(index,edge[s.charAt(i) - a]);if(i index){right i;list.add(right - left);left i;}}return list;}
两道难题
134. 加油站
这道题目如果我们使用模拟的方式来进行解题也是可以的但是很显然太过于麻烦了
那么我们换一种思路由于每个加油站都有耗油量和加油量那么如果我们将他们进行整合一下
路过每个加油站都会得出一个剩油量加油量 - 耗油量 同时让车辆从起点开始路过每个加油站的时候都统计一下剩下的油量
如果剩下的油量小于0说明不能再往前开了此时就得选择下一个站点作为起始位置重新计算了
由于我们是需要将车辆跑一圈从起始位置出发最终回到起始位置有没有一种可能就是如果我们选择了下一个站点作为起始位置那么由于只能知道以下一个站点为起始位置后面的剩油量不知道前面的剩油量从而导致不能跑完全程
答案是有可能的所以我们要先确定好车辆能不能够跑完全程
方法也很简单只要确定gas之和大于等于cost之和那么就一定是可以跑完全程的 for(int i 0;i rest.length;i){rest[i] gas[i] - cost[i];sum rest[i];}if(sum 0){return -1;}
还有一种常见的疑惑由于我们从起始加油站跑到 i 这个站点的时候剩油量小于0了我们直接让 i 1作为起始位置重新开始跑那么有没有一种可能就是 起始位置到 i 之间再选择一个位置作为起始位置从而使到达 i 这个位置的时候剩油量大于0换言之会不会遗漏掉某一个起始位置
那么我画一幅图来进行解释 那么根据我这副图的分析就能够很好的解释这种现象了所以根本就不会出现这样的问题因为我们的策略就是 剩下的油量小于0说明不能再往前开了此时就得选择下一个站点作为起始位置重新计算了不存在说会遗漏掉某一个起始位置
最后贴上我们的最终代码
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int[] rest new int[gas.length];int sum 0;for(int i 0;i rest.length;i){rest[i] gas[i] - cost[i];sum rest[i];}if(sum 0){return -1;}sum 0;int ans 0;for(int i 0;i rest.length;i){sum rest[i];if(sum 0){sum 0;ans i 1;//下一个加油站开始}}return ans;}
}
968. 监控二叉树
这道题可以说是一道难题了
根据示例 同时结合题目意思每个摄影头都可以监视其父对象、自身及其直接子对象也就是说每个摄像头只能监控他的相连接的节点
这个时候分情况讨论出局部最优
从而达到全局最优计算监控树的所有节点所需的最小摄像头数量
首先我们约定好
为了充分利用上中下三个位置的节点状态我们应该使用后序遍历从下往上的遍历二叉树
同时函数返回值是返回状态我们使用 int 来接收
当返回值为0时为没有被监控的状态
当返回值为1时为放置了摄像头的状态
当返回值为2时为被摄像头监控的状态
情况1当节点是叶子节点的时候
当节点是叶子节点那么此时我们就让他的父节点装一个监控从而达到用最少的摄像头数量监控最多的节点 if(root null){return 2;} 情况2当两个节点都有子节点有监控时此时父节点就不需要安装摄像头了 if(left 1 right 1){return 2;} 情况3当左右孩子有一个有摄像头时
并且另一个节点被监控到了此时父节点就不需要安装摄像头了 if(left 1 || right 1){result;return 2;} 情况4当左右孩子有一个没有被监控到那么此时父节点不过另一个节点是否安装了摄像头它一定要安装摄像头 if(left 0 || right 0){result;return 1;} 情况5当头节点没有被监控那么就给头节点添加一个监控
if(root 0){root.val 1;result;
} 分析完毕现在开始编写代码
class Solution {int result 0;public int minCameraCover(TreeNode root) {if(minCameraCoverHelper(root) 0){result;}return result;}public int minCameraCoverHelper(TreeNode root){if(root null){return 2;}int left minCameraCoverHelper(root.left);int right minCameraCoverHelper(root.right);if(left 0 || right 0){result;return 1;}if(left 2 right 2){return 0;}if(right 1 || left 1){return 2;}return -1;}
}
代码编写完毕
