贪默算法一

> 作者：დ旧言~
> 座右铭：松树千年末是朽，槿花一日自为荣。
  > 目标：相识什么是贪默算法，而且把握贪默算法。
  > 毒鸡汤：有些事变，总是不明确，以是我不会对峙。早安!
  > 专栏选自：贪默算法_დ旧言~的博客-CSDN博客
  > 望小搭档们点赞👍收藏✨加关注哟💕💕
  一、算法解说

贪默算法的界说：
贪默算法是指在对题目求解时，总是做出在当前看来是最好的选择。也就是说，不从团体最优上加以思量，只做出在某种意义上的局部最优解。贪默算法不是对全部题目都能得到团体最优解，关键是贪心计谋的选择，选择的贪心计谋必须具备无后效性，即某个状态从前的过程不会影响以后的状态，只与当前状态有关。
解题的一样平常步调是：

• 创建数学模子来形貌题目；
  
• 把求解的题目分成多少个子题目；
  
• 对每一子题目求解，得到子题目的局部最优解；
  
• 把子题目的局部最优解合成原来题目的一个解。
  

假如各人比力相识动态规划，就会发现它们之间的相似之处。最优解题目大部门都可以拆分成一个个的子题目，把解空间的遍历视尴尬刁难子题目树的遍历，则以某种情势对树整个的遍历一遍就可以求出最优解，大部门情况下这是不可行的。贪默算法和动态规划本质上是对子题目树的一种修剪，两种算法要求题目都具有的一个性子就是子题目最优性(构成最优解的每一个子题目的解，对于这个子题目自己肯定也是最优的)。
动态规划方法代表了这一类题目的一样平常解法，我们自底向上构造子题目的解，对每一个子树的根，求出下面每一个叶子的值，而且以此中的最优值作为自身的值，别的的值舍弃。而贪默算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前题目的状态。换句话说，不须要知道一个节点全部子树的情况，就可以求出这个节点的值。由于贪默算法的这个特性，它对解空间树的遍历不须要自底向上，而只须要自根开始，选择最优的路，不停走到底就可以了。
二、算法习题

---

2.1、第一题

   标题链接：860. 柠檬水找零 - 力扣（LeetCode）
  标题形貌：
   

  算法思绪：
a. 遇到 5 元钱，直吸取下；
b. 遇到 10 元钱，找零 5 元钱之后，收下；
c. 遇到 20 元钱：

• 先实验凑 10 + 5 的组合；
  
• 假如凑不出来，拼集 5 + 5 + 5 的组合；
  

代码出现：

1. class Solution {
2. public:
3.     bool lemonadeChange(vector<int>& bills)
4.     {
5.         int five = 0, ten = 0;
6.         for (auto x : bills)
7.         {
8.             if (x == 5)
9.                 five++;       // 5 元：直接收下
10.             else if (x == 10) // 10 元：找零 5 元
11.             {
12.                 if (five == 0)
13.                     return false;
14.                 five--;
15.                 ten++;
16.             } else // 20 元：分情况讨论
17.             {
18.                 if (ten && five) // 贪⼼
19.                 {
20.                     ten--;
21.                     five--;
22.                 } else if (five >= 3) {
23.                     five -= 3;
24.                 } else
25.                     return false;
26.             }
27.         }
28.         return true;
29.     }
30. };

复制代码

2.2、第二题

   标题链接：2208. 将数组和减半的最少操纵次数 - 力扣（LeetCode）
  标题形貌：
   

  算法思绪：

• 每次挑选出「当前」数组中「最⼤」的数，然后「减半」；
  
• 直到数组和镌汰到⾄少⼀半为⽌。
  

为了「快速」挑选出数组中最⼤的数，我们可以利⽤「堆」这个数据布局。
代码出现：

1. class Solution {
2. public:
3.     int halveArray(vector<int>& nums)
4.     {
5.         priority_queue<double> heap; // 创建⼀个⼤根堆
6.         double sum = 0.0;
7.         for (int x : nums) // 把元素都丢进堆中，并求出累加和
8.         {
9.             heap.push(x);
10.             sum += x;
11.         }
12.         sum /= 2.0; // 先算出⽬标和
13.         int count = 0;
14.         while (sum > 0) // 依次取出堆顶元素减半，直到减到之前的⼀半以下
15.         {
16.             double t = heap.top() / 2.0;
17.             heap.pop();
18.             sum -= t;
19.             count++;
20.             heap.push(t);
21.         }
22.         return count;
23.     }
24. };

复制代码

2.3、第三题

   标题链接：179. 最大数 - 力扣（LeetCode）
  标题形貌：
   

  算法思绪：
可以先优化：
将全部的数字当成字符串处理处罚，那么两个数字之间的拼接操纵以及⽐较操纵就会很⽅便。
贪⼼计谋：
按照题⽬的要求，重新界说⼀个新的排序规则，然后排序即可。
排序规则：

• 「A 拼接 B」 ⼤于 「B 拼接 A」，那么 A 在前，B 在后；
  
•  「A 拼接 B」 便是 「B 拼接 A」，那么 A B 的次序⽆所谓；
  
• 「A 拼接 B」 ⼩于 「B 拼接 A」，那么 B 在前，A 在后
  

代码出现：

1. class Solution {
2. public:
3.     string largestNumber(vector<int>& nums)
4.     {
5.         // 优化：把所有的数转化成字符串
6.         vector<string> strs;
7.         for (int x : nums)
8.             strs.push_back(to_string(x));
9.         // 排序
10.         sort(strs.begin(), strs.end(), [](const string& s1, const string& s2) {
11.             return s1 + s2 > s2 + s1;
12.         });
13.         // 提取结果
14.         string ret;
15.         for (auto& s : strs)
16.             ret += s;
17.         if (ret[0] == '0')
18.             return "0";
19.         return ret;
20.     }
21. };

复制代码

2.4、第四题

   标题链接：376. 摆动序列 - 力扣（LeetCode）
  标题形貌：
   

  算法思绪：
对于某⼀个位置来说：

• 假如接下来出现上升趋势的话，我们让其上升到波峰的位置；
  
• 假如接下来出现降落趋势的话，我们让其降落到波⾕的位置。
  
• 因此，假如把整个数组放在「折线图」中，我们统计出全部的波峰以及波⾕的个数即可
  

代码出现：

1. class Solution {
2. public:
3.     int wiggleMaxLength(vector<int>& nums)
4.     {
5.         int n = nums.size();
6.         if (n < 2)
7.             return n;
8.         int ret = 0, left = 0;
9.         for (int i = 0; i < n - 1; i++)
10.         {
11.             int right = nums[i + 1] - nums[i]; // 计算接下来的趋势
12.             if (right == 0)
13.                 continue; // 如果⽔平，直接跳过
14.             if (right * left <= 0)
15.                 ret++; // 累加波峰或者波⾕
16.             left = right;
17.         }
18.         return ret + 1;
19.     }
20. };

复制代码

2.5、第五题

   标题链接：300. 最长递增子序列 - 力扣（LeetCode）
  标题形貌：
   

  算法思绪：

• 我们在思量最⻓递增⼦序列的⻓度的时间，实在并不关⼼这个序列⻓什么样⼦，我们只是关⼼末了⼀个元素是谁。如许新来⼀个元素之后，我们就可以判断是否可以拼接到它的后⾯。
  
• 因此，我们可以创建⼀个数组，统计⻓度为 x 的递增⼦序列中，末了⼀个元素是谁。为了尽大概让这个序列更⻓，我们仅需统计⻓度为 x 的全部递增序列中末了⼀个元素的「最⼩值」。
  
• 统计的过程中发现，数组中的数出现「递增」趋势，因此可以使⽤「⼆分」来查找插⼊位置。
  

代码出现：

1. class Solution {
2. public:
3.     int lengthOfLIS(vector<int>& nums)
4.     {
5.         int n = nums.size();
6.         vector<int> ret;
7.         ret.push_back(nums[0]);
8.         for (int i = 1; i < n; i++)
9.         {
10.             if (nums[i] > ret.back()) // 如果能接在最后⼀个元素后⾯，直接放
11.             {
12.                 ret.push_back(nums[i]);
13.             } else {
14.                 // ⼆分插⼊位置
15.                 int left = 0, right = ret.size() - 1;
16.                 while (left < right) {
17.                     int mid = (left + right) >> 1;
18.                     if (ret[mid] < nums[i])
19.                         left = mid + 1;
20.                     else
21.                         right = mid;
22.                 }
23.                 ret[left] = nums[i]; // 放在 left 位置上
24.             }
25.         }
26.         return ret.size();
27.     }
28. };

复制代码

2.6、第六题

   标题链接：334. 递增的三元子序列 - 力扣（LeetCode）
  标题形貌：
   

  算法思绪：
不⽤⼀个数组存数据，仅需两个变量即可。也不⽤⼆分插⼊位置，仅需两次⽐较就可以找到插⼊位
置。
代码出现：

1. class Solution {
2. public : bool increasingTriplet(vector<int>& nums)
3. {
4.         int a = nums[0], b = INT_MAX;
5.         for (int i = 1; i < nums.size(); i++)
6.         {
7.             if (nums[i] > b)
8.                 return true;
9.             else if (nums[i] > a)
10.                 b = nums[i];
11.             else
12.                 a = nums[i];
13.         }
14.         return false;
15.     }
16. };

复制代码

三、竣事语 

本日内容就到这里啦，时间过得很快，各人沉下心来好勤学习，会有肯定的劳绩的，各人多多对峙，嘻嘻，乐成路上注定孤独，由于对峙的人不多。那请各人举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。

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