力扣100题——贪默算法

概述

   贪默算法（Greedy Algorithm）是一种在办理问题时，按照某种尺度在每一步都选择当前最优解（局部最优解）的算法。它期望通过一系列局部最优解的选择，终极可以或许得到全局最优解。
  贪默算法的核心思想

贪默算法的核心思想是每一步都采取最优选择，即所谓的“贪心选择”。算法会根据某种贪心计谋，渐渐做出局部最优的选择，并渴望通过这些局部最优的选择可以或许得到终极的全局最优解。
贪默算法的一样平常步骤

• 问题分解：将问题分解为多少个子问题。
  
• 选择贪心计谋：为每个子问题选取局部最优解（通常是通过某种评价尺度，选择当前最有利的选择）。
  
• 合并子问题的解：将每次的选择累积起来，直到办理完所有子问题，得到终极的全局解。
  

贪默算法的应用场景

贪默算法实用于那些通过选择局部最优解，终极可以或许得到全局最优解的问题。一样平常来说，贪默算法并不总是能找到全局最优解，但在某些特定问题中，它可以得到最优解。常见的贪默算法应用场景包罗：

• 最小天生树问题：Kruskal 和 Prim 算法都是基于贪心计谋的，可以或许找到加权连通图的最小天生树。
  
• 活动选择问题：用于选择最多的不重叠活动，典型的贪心选择是选择结束时间最早的活动。
  
• 背包问题（贪心版的 0-1 背包问题）：按物品的单位代价从高到低举行选择，直到装满背包。
  

贪默算法的优缺点

优点：

• 简单、高效：由于只关注局部最优，贪默算法通常比较简单，运行速度较快。
  
• 直接、可实现性强：贪默算法容易实现，对于某些问题是最佳办理方案。
  

缺点：

• 不实用于所有问题：贪默算法无法保证在所有问题中都能找到全局最优解，尤其是当局部最优解无法组合玉成局最优解时。
  
• 必要问题具备“贪心选择性质”：即从局部最优可以或许推导出全局最优。
  

刷题

买卖股票的最佳时机

标题

121. 买卖股票的最佳时机 - 力扣（LeetCode）
思路

初始思路：以每一个数组元素为买入点，找出利润的最大值，时间复杂度是O(n)
优化思路：在遍历的过程中，我们始终选择当前最小的买入价格，并盘算卖出的最大大概利润。
代码

初始代码

1. public int maxProfit(int[] prices) {
2.         int n = prices.length;
3.         int max = 0;
4.         for (int i = 0; i < n; i++) {
5.             for(int j=i+1;j<n;j++){
6.                 if(prices[j]>prices[i]){
7.                     max = Math.max(max,prices[j]-prices[i]);
8.                 }
9.             }
10.         }
11.         return max;
12.     }

复制代码

优化后的代码

1. public int maxProfit(int[] prices) {
2.         int n = prices.length;
3.         int max = 0;
4.         int min = prices[0];
5.         for (int i = 0; i < n; i++) {
6.             if(prices[i] < min)
7.                 min = prices[i];
8.             max = Math.max(max, prices[i] - min);
9.         }
10.         return max;
11.     }

复制代码

跳跃游戏

标题

55. 跳跃游戏 - 力扣（LeetCode）
思路

• 初始化一个变量 maxReach，表现当前可以或许到达的最远位置。
  
• 遍历数组的每一个元素，对于每个元素 nums，查抄是否可以从当前位置到达更远的位置，即 maxReach 是否大于或即是当前下标 i。
  
• 在遍历的过程中，不断更新可以或许到达的最远位置 maxReach 为 i + nums。
  
• 假如在遍历过程中，某个位置的 maxReach 大于或即是末了一个下标，则返回 true；否则，假如遍历结束仍未达到末了一个下标，则返回 false。
  

代码

1. public boolean canJump(int[] nums) {
2.         int n = nums.length;
3.         int max = 0;
4.         for(int i = 0; i < n; i++) {
5.             if(i>max){
6.                 return false;
7.             }
8.             max = Math.max(max, nums[i] + i);
9.             if(max>=n-1){
10.                 return true;
11.             }
12.         }
13.         return false;
14.     }

复制代码

跳跃游戏Ⅱ

标题

45. 跳跃游戏 II - 力扣（LeetCode）
思路

1.定义状态：

• 维护两个变量 curEnd 和 curFarthest：
  
• curEnd 表现当前跳跃范围的最远边界。
  
• curFarthest 表现通过当前步可以或许到达的最远位置。
  

2.遍历数组：

• 遍历 nums，在每次遍历时，我们会更新 curMax，表现通过当前跳跃可以到达的最远位置。
  
• 当遍历到 curEnd 时，表现当前跳跃已经完成，必须举行下一次跳跃，并更新 max 为 curMax，跳跃次数加1。
  
• 末了，假如遍历到了数组的末了一个位置，返回跳跃次数即可。
  

贪心计谋：

• 在每一次跳跃中，我们尽大概向前跳得最远，如许才能保证在最少的跳跃次数内到达数组末端。
  

代码

1. public int jump(int[] nums) {
2.         int n = nums.length;
3.         int max = 0;
4.         int curMax = 0;
5.         int sum =0;
6.         for(int i = 0; i < n; i++) {
7.             if(i==n-1){
8.                 break;
9.             }
10.             curMax = Math.max(curMax, nums[i] + i);
11.             if(i==max){
12.                 max = curMax;
13.                 sum++;
14.             }
15.         }
16.         return sum;
17.     }

复制代码

划分字母区间

标题

763. 划分字母区间 - 力扣（LeetCode）
思路

• 用一个last数组，记录每个字母出现的最远位置
  
• 遍历数组，使用start和end记录当前划分字符串的开头和结尾
  
• 每次不断的更新当前字符串的最远位置
  
• 当i和end相称，即代表当前字符串划分结束
  

代码

1. public List<Integer> partitionLabels(String s) {
2.         List<Integer> res = new ArrayList<Integer>();
3.         int[] last = new int[26];
4.         for(int i=0;i<s.length();i++){
5.             last[s.charAt(i)-'a']=i;
6.         }
7.         int end = 0,start = 0;
8.         for(int i=0;i<s.length();i++){
9.             end = Math.max(end, last[s.charAt(i)-'a']);
10.             if(i==end){
11.                 res.add(end-start+1);
12.                 start=i+1;
13.             }
14.         }
15.         return res;
16.     }

复制代码

结语

每次做贪心都以为自己智商低

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。