贪心算法【1】

时间：2024-12-21 11:36:47

文章目录

    • 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;
    }
};

交换论证法

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

image-20240927163356570

由于是贪心策略，到此处的时候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后

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

代码实现

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;
    }
};

相关文章