贪心算法理论基础和习题【算法学习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;}
}