贪心算法【1】

文章目录

860. 柠檬水找零
题目解析
算法原理
代码实现
交换论证法

2208. 将数组和减半的最少操作次数
题目解析
算法原理
代码实现
交换论证法

179. 最大数
题目解析
算法原理
代码实现

860. 柠檬水找零

题目链接：860. 柠檬水找零

题目解析

一杯柠檬水5块钱，每个顾客每次只能买一杯，支付的现金的面额有5块、10块、20块。

我们需要能够正确的找零，而且最开始我们手里没有钱。

如果遇上不能找零的，则返回false；如果从始至终能够正确找零，返回true。

bills：顾客支付的钱的面额

算法原理

分情况讨论：

顾客给5块，收下
顾客给10块，手上有5块，给5块，然后收下10块；没有返回false
顾客给20块
1. 给三张5块
2. 给一张5块，一张10块
此时这里就能体现贪心，5块钱可以在10块那里用，也可以在20块这里用，所以要尽可能保留5块钱。

所以优先选择给一张5块和一张10块。

代码实现

class Solution {
public:
    bool lemonadeChange(vector<int>& bills)
    {
        if(bills[0] != 5)   return false;
        //unordered_map<int, int> hash;
        int five = 0;
        int ten = 0;
        for(auto e : bills)
        {
            if(e == 5)  five++;
            else if(e == 10)
            {
                if(five == 0)   return false;
                
                five--;
                ten++;
            }
            else
            {
                if(five != 0 && ten != 0)
                {
                    five--;
                    ten--;
                }
                else if(five >= 3)
                {
                    five -= 3;
                }
                else
                {
                    return false;
                }
            }
        }
        return true;
    }
};

交换论证法

证明策略：交换论证法

假设贪心策略的结果是：a b c d e f；最优解是e b c d a f，需要证明在不破坏最优解最优性质的前提下，能够将最优解调整成贪心解。

这里唯一要考虑的就是顾客给20块钱，该如何找零：

贪心策略，有10块和5块，肯定先将10块给出去
最优解，可能是三个5块，也能是5块、10块各一张
这里需要考虑不一样的情况，即最优解给的三张5块

此时就要看能不能将这种情况替换成贪心策略一模一样的，这里2种情况：

10块钱后面没用上：此时可以直接将最优解的三张5块，换成一张10块和一张5块（因为这个10块钱不影响后续操作）
10块钱有用上：依旧可以替换两张5块钱，两张5块钱后面也能抵一张10块钱

所以，不管是用或者不用，都能将最优解替换成贪心解。

2208. 将数组和减半的最少操作次数

题目链接：2208. 将数组和减半的最少操作次数

题目解析

给我们一个正整数数组nums，每次操作都能够从数组选一个数字，对其减半（后续还能继续操作这个数）

最后返回，将nums数组和至少减小一半的最小次数。

算法原理

最少操作次数，每次就挑选最大的，这就是我们的贪心策略。

由于要选择每次最大的元素，这需要用堆来辅助。

最大元素，大根堆。

代码实现

class Solution {
public:
    int halveArray(vector<int>& nums)
    {
        double sum = 0;
        priority_queue<double> heap;
        for(auto e : nums)
        {
            sum += e;
            heap.push(e);
        }
        double targer = sum / 2.0;
        int ret = 0;
        while(sum > targer)
        {
            double n = heap.top();
            heap.pop();
            sum -= n;
            n /= 2.0;
            sum += n;
            ret++;
            heap.push(n);
        }
        return ret;
    }
};

交换论证法

这次还是一样，如果能将最优解不失最优性质的前提下将最优转换为贪心解，就能证明贪心策略是正确的。

由于是贪心策略，到此处的时候x >= y，这里分2种情况：

x在最优解当中没有用过，此时x可以直接替换y，y比x小，x减半，效果更足
x在最优解后续操作使用过，此时也能替换，因为都是要使用的，先后顺序并没有关系，不会影响操作次数

此时不管怎样，都能进行替换。

179. 最大数

题目链接：179. 最大数

题目解析

给我们一个非负整数数组，让我们排列组合，找出最大的组合。

返回的是字符串，因为这个数字可能非常大。

算法原理

这个排列组合，差不多像排序：

正常排序（升序）：
它的本质就是确定元素的先后顺序，谁在前谁在后
规则：

a > b a前 b后
a = b 都行
a < b b前 a后
本题也是确定元素的先后顺序，即找出排序规则即可

ab > ba a前 b后
ab = ba 都行
ab < ba b前 a后

这里的贪心就体现在每次比较都确定最好的排序序列

a > b	a前 b后
a = b	都行
a < b	b前 a后

ab > ba	a前 b后
ab = ba	都行
ab < ba	b前 a后

代码实现

class Solution {
public:
    string largestNumber(vector<int>& nums)
    {
        vector<string> str_nums;
        for(auto e : nums)
        {
            str_nums.push_back(to_string(e));
        }

        sort(str_nums.begin(), str_nums.end(), [](const string &s1, const string &s2)
        {
            return s1 + s2 > s2 + s1;
        });

        string ret;
        for(auto e : str_nums)
        {
            ret += e;
        }
        if(ret[0] == '0') return "0";
        return ret;
    }
};