wordpress全站背景,字体模板素材免费下载网站,淘宝关键词优化怎么弄,网页游戏人生重开模拟器前言
###我做这类文档一个重要的目的还是给正在学习的大家提供方向#xff08;例如想要掌握基础用法#xff0c;该刷哪些题#xff1f;#xff09;我的解析也不会做的非常详细#xff0c;只会提供思路和一些关键点#xff0c;力扣上的大佬们的题解质量是非常非常高滴例如想要掌握基础用法该刷哪些题我的解析也不会做的非常详细只会提供思路和一些关键点力扣上的大佬们的题解质量是非常非常高滴 理论基础
贪心算法Greedy Algorithm是一种在每一步选择中都采取当前状态下的最优决策的算法策略简而言之就是通过局部最优达到全局最优
如何解决这类问题就在习题中体会~ 习题
ps:部分题我不分析贪心多少带点赌的思想
1.分发饼干
题目链接:455. 分发饼干 - 力扣LeetCode
题面:
基本分析尽可能花最小的代价满足孩子所以排序然后采用双指针
代码:
class Solution {public int findContentChildren(int[] g, int[] s) {int clen g.length;int blen s.length;int count 0;Arrays.sort(g);Arrays.sort(s);int l1 0;int l2 0;while(l1clenl2blen){if(g[l1]s[l2]){count;l1;l2;}else{l2;}}return count;}
} 2.摆动序列
题目链接:376. 摆动序列 - 力扣LeetCode
题面:
代码:
class Solution {public int wiggleMaxLength(int[] nums) {int n nums.length;// if(n2nums[0]-nums[1]0)return 1;int[] flag new int[n];int count n;for(int i 1;in-1;i){int l i-1;int r i1;while(l-10flag[l]1)l--;while(r1nflag[r]1)r;if((nums[i]nums[l]nums[i]nums[r])||(nums[i]nums[l]nums[i]nums[r])){flag[i] 1 ;count--;}}Arrays.sort(nums);if(nums[0]nums[n-1])return 1;return count;}
}
3.最大子数组和
题目链接:53. 最大子数组和 - 力扣LeetCode
题面:
代码:
class Solution {public int maxSubArray(int[] nums) {int n nums.length;int l 0;int r 1;int sum nums[0];int max nums[0];while(rn){if(nums[r]nums[r]sum){sum nums[r];lr;}else {sumnums[r];}max Math.max(max,sum);r;}return max;}
}
4.买卖股票的最佳时机II
题目链接:122. 买卖股票的最佳时机 II - 力扣LeetCode
题面:
代码:
class Solution {public int maxProfit(int[] prices) {int n prices.length;int sum 0;for(int i 1;in-1;i){int k prices[i]-prices[i-1];if(k0)sumk;}return sum;// int l 1;// int pre prices[0];// while(ln){// if(prices[l]pre){// sum(prices[l]-pre);// if(l2n){// pre prices[l1];// l;// }else{// break;// }// }// else if(prices[l]pre){// pre prices[l];// }// l;// }// return sum;}
} 5.跳跃游戏
题目链接:55. 跳跃游戏 - 力扣LeetCode
题面:
代码:
class Solution {int[] arr;int len;public boolean canJump(int[] nums) {int n nums.length;if(n1)return true;arr nums;len n;int flag1 0;int flag2 0;for(int i 0;in-1;i){if(nums[i]0){flag11;if(canTrap(i)false){flag2 1;break;}}}if(flag10)return true;if(flag20)return true;return false;}public boolean canTrap(int flag){for(int i flag-1;i0;i--){if(arr[i](flag-i))return true;if(flaglen-1arr[i](flag-i))return true;}return false;}
} 6.跳跃游戏II
题目链接:45. 跳跃游戏 II - 力扣LeetCode
题面:
代码:
class Solution {int len;int[] arr;public int jump(int[] nums) {arr nums;len nums.length;int count 0;int l 0;while(llen-1){count;l jumpWhere(l);}return count;}public int jumpWhere(int flag){int n arr[flag];if(flagnlen-1)return len-1;int ans flag1;int max arr[flag1];for(int i flag2;iflagn;i){if(arr[i]i-(flag1)max){max arr[i]i-(flag1);ans i;}}return ans;}
} 7.K次取反后最大化的数组和
题目链接:1005. K 次取反后最大化的数组和 - 力扣LeetCode
题面:
代码:
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);int count 0;int n nums.length;while(countncountknums[count]0){nums[count]-nums[count];count;}Arrays.sort(nums);if((k-count)%2!0)nums[0]-nums[0];int sum 0;for(int i 0;in;i){sumnums[i];}return sum;}
} 8.加油站
题目链接:134. 加油站 - 力扣LeetCode
题面:
代码:
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int n gas.length;int ans 0;int l 0;int flag -1;int sum 0;for(int i 0;in-1;i){gas[i] gas[i]-cost[i];sumgas[i];if(gas[i]0flag!-1){l i;flag 0;}}if(sum0)return -1;ans l;sum 0;while(ln){if(sumgas[l]0){ll1;sum 0;ans l;}else{sumgas[l];l;}}return ans;}
} 后言
上面是贪心算法基本概念和部分习题下一篇会讲解贪心算法的其他相关力扣习题希望有所帮助一同进步共勉
