c++算法贪心系列

本篇文章，同大家一起学习贪心算法！！！

 第一题

题目链接

2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）

题目解析

本题重点：最终的数组和要小于原数组和的一半，且求这一操作的最少操作数

代码原理

代码编写

class Solution {

public:

    int halveArray(vector<int>& nums) {

        double sum = 0.0;

        priority_queue<double> heap;//将数据存放进大根堆中的优势：最大的数会在堆顶

        for(auto cur: nums)

        {

            heap.push(cur);

            sum += cur;

        }

        sum /= 2.0;

        int count = 0;

        while(sum > 0)

        {

            double t = heap.top() / 2.0;

            heap.pop();

            sum -= t;

            count++;

            heap.push(t);

        }

        return count;

    }

};

贪心策略

选择数组中最大的元素

第二题

题目链接

179. 最大数 - 力扣（LeetCode）

题目解析

代码原理

代码编写

class Solution {

public:

    string largestNumber(vector<int>& nums) {

        vector<string> str;

        for(auto cur: nums)

        {

            str.push_back(to_string(cur));

        }

        sort(str.begin(), str.end(), [](const string& a, const string& b)

        {

            return a + b > b + a;

        });

        string ret;

        for(auto& s: str)

        {

            ret += s;

        }

        if(ret[0] == '0') return "0";

        return ret;

    }

};

贪心策略

先看数字的最高位，与其他数字的最高位进行比较，大的在前小的在后

注意：一切都以每个数的最高位为比较对象

第三题

题目链接

376. 摆动序列 - 力扣（LeetCode）

题目解析

相信大家对这道题已经不再陌生，因为我们上一次做这题的时候是用动态规划的方法去做的题，当然这次博主依旧为给大家简单解析一下这题

注意：这里的加号表示递增，减号表示递减！！！大体可以参考高中时学过的单调性

代码原理

将一个波分成两段分析，因此就有了left和right，left的状态（是上升还是下降）由后面的i+1的元素决定，right的状态则需要i + 1元素和i元素决定。

由于起点无法判断它的状态因此要长度减1,也因此最后的子序列长度要加1

代码编写

class Solution {

public:

    int wiggleMaxLength(vector<int>& nums) {

        int n = nums.size();

        if(n < 2) return n;

        int ret = 0, left = 0;

        for(int i = 0; i < n - 1; i++)

        {

             int right = nums[i + 1] - nums[i];

             if(right == 0) continue;

             if(right * left <= 0) ret++;

             left = right;

        }

        return ret + 1;

    }

};

贪心策略

画图 + 状态走向

那么本篇文章的内容就先到这里，我们下期文章再见！！！！

记得一键三联哦！！！