贪心算法理论基础和习题【算法学习day.17】
前言
###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！
理论基础
贪心算法（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(l1<clen&&l2<blen){
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(n==2&&nums[0]-nums[1]==0)return 1;
int[] flag = new int[n];
int count = n;
for(int i = 1;i<n-1;i++){
int l = i-1;
int r = i+1;
while(l-1>=0&&flag[l]==1)l--;
while(r+1<n&&flag[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(r<n){
if(nums[r]>=nums[r]+sum){
sum = nums[r];
l=r;
}else {
sum+=nums[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;i<=n-1;i++){
int k = prices[i]-prices[i-1];
if(k>0)sum+=k;
}
return sum;
// int l = 1;
// int pre = prices[0];
// while(l<n){
// if(prices[l]>pre){
// sum+=(prices[l]-pre);
// if(l+2<n){
// pre = prices[l+1];
// 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(n==1)return true;
arr = nums;
len = n;
int flag1 = 0;
int flag2 = 0;
for(int i = 0;i<=n-1;i++){
if(nums[i]==0){
flag1=1;
if(canTrap(i)==false){
flag2 = 1;
break;
}
}
}
if(flag1==0)return true;
if(flag2==0)return true;
return false;
}
public boolean canTrap(int flag){
for(int i = flag-1;i>=0;i--){
if(arr[i]>(flag-i))return true;
if(flag==len-1&&arr[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(l<len-1){
count++;
l = jumpWhere(l);
}
return count;
}
public int jumpWhere(int flag){
int n = arr[flag];
if(flag+n>=len-1)return len-1;
int ans = flag+1;
int max = arr[flag+1];
for(int i = flag+2;i<=flag+n;i++){
if(arr[i]+i-(flag+1)>=max){
max = arr[i]+i-(flag+1);
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(count<n&&count<k&&nums[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;i<n;i++){
sum+=nums[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;i<=n-1;i++){
gas[i] = gas[i]-cost[i];
sum+=gas[i];
if(gas[i]>=0&&flag!=-1){
l = i;
flag = 0;
}
}
if(sum<0)return -1;
ans = l;
sum = 0;
while(l<n){
if(sum+gas[l]<0){
l=l+1;
sum = 0;
ans = l;
}else{
sum+=gas[l];
l++;
}
}
return ans;
}
}后言
上面是贪心算法基本概念和部分习题，下一篇会讲解贪心算法的其他相关力扣习题，希望有所帮助，一同进步，共勉！ 