[算法课]全面翻新计划！第十一周全解

文章目录

• ​​上课内容​​

• ​​贪心法​​
• ​​例1 兑换货币​​

• ​​颜老板代码​​
• ​​更新版​​

• ​​测试数据​​
• ​​博主提示：​​
• ​​注意：​​

• ​​贪心算法的思路：​​
• ​​请考虑此题用贪心的算法来书写试试看​​

• ​​博主注释​​
• ​​思路​​
• ​​更新版 贪心版本​​
• ​​答案​​

• ​​思考：【LeetCode】柠檬水找零​​

• ​​分析​​
• ​​颜老板版本​​
• ​​更新版​​
• ​​博主思路​​
• ​​提醒：​​

• ​​例如 单调递增的数字【选自LeetCode】​​

• ​​分析​​
• ​​更新版​​
• ​​更新版 贪心​​

• ​​1029. 两地调度【来自LeetCode里面】​​

• ​​思路​​
• ​​AC代码​​
• ​​注明：​​

上课内容

贪心法

第11次 贪心法
问题
1 1吨100元的钞票
2 100吨1元的钞票
如果是你，你选哪个？【送给你的】

某人说都要！ 太无耻了！

有人说1，有人说2，有同学说都要！

【只能证明你们的心中有一个住着许久小恶魔：人的本性：贪！！！】

如果是我你们猜我怎么回答？
【你随便给哪个都可以，我不贪的！】

其实 贪 这个词语 这个是贬义词，其实要看使用的语境

举例

例如 小朋友，手里有个吃的，你问他，你给我分享一点儿好吗？
【现象：】

举例
篮球比赛选出5个选手的问题？
【如果让你在现实中，从全世界所有的现役篮球选手中，组成一个你觉得最强大的球队，你会挑选哪些人？】

控卫：库里？欧文？
分卫：杜兰特
小前：詹姆斯
大前：字母哥
中锋：浓眉哥

思考一个问题 ：这些人在一起真的能组成这个地球上最牛的吗？
【在选他们的时候，大家有2种心态】
1 真的在某个位置上最强，
2 我最喜欢的

NBA马刺。
前后夺得几次总冠军
回过头来看，按照马刺当年的阵容，一一单拿出来，在联盟不见得是最强。

靠团队的力量！

如果使用贪心方式去选择球员，基本原则大家都心知肚明

但是如何做到保持贪心的方法，到最后看起来最佳的选择也是最初的贪心呢？
【白话：你贪的没毛病！】

在我心中，这种算法，更多强调的是一种思维方式。

例1 兑换货币

在2006年开始工作的时候，那个时候我们的工资不是打到卡上。
而是到财务处领现金。
假设我某个月的收入是1289，请问财务处给我如何发工资，使得我们拿到手的纸币最少呢？
【最终实现：任意输入某个月的收入，求得答案】

分析：
1）准备若干张100 50 20 10 5 2 1元的人民币
2）如果取纸币，一般正常的一个财务会如何选择呢？
一般人的处理方式：
计算100元的张数【此刻一般人不会去算1元的张数】
接下来再分别考虑
50的张数
20的张数
10的张数
5的张数
2的张数
1的张数
整个这个过程秉承方法就是贪心的原则
3）实践一下
有gz变量如何求得100元的张数
z[1]=gz/m[1];
gz=gz-z[1]*m[1];//计算剩余的工资
替换上一行
gz=gz%100;
4）代码如下

颜老板代码

#include<stdio.h>

int main()
{
  int m[8]={0,100,50,20,10,5,2,1};//编号从1开始用
  int z[8]={0};//纸币对应的张数
  int gz;
  int i;
  
  printf("请任意输入你的工资:");
  scanf("%d",&gz);
  
  for(i=1;i<=7;i++)
  {
    z[i]=gz/m[i];
    gz=gz-z[i]*m[i];//计算剩余的工资
    printf("面值是%d的人民币有%d张\n",m[i],z[i]);
  }
 
  return 0;
}

更新版

我把它更新为了所有数据都是自己输入的版本，变量名很明显了就不注释了

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool cmp(int a,int b){return a>b;}
int main()
{
    vector<int>a;
    int sumPrice,n;
    cin>>sumPrice>>n;
    for(int i=0;i<n;i++){int t;cin>>t;a.push_back(t);}
    
    sort(a.begin(),a.end(),cmp);
    
    int res=0;
    for(int i=0;i<n;i++)
        res+=(sumPrice/a[i]),sumPrice%=a[i];
    
    cout<<res;
    
    return 0;
}

测试数据

431 7 100 1 2 5 10 20 50

博主提示：

这里的货币系统非常依赖货币面额，如果不成为倍数关系等情况下就可能出现错误

注意：

1 贪心的体现地方在哪里？纸币面值从大到小！

2 贪心算法的使用很可能会和前面所讲过排序算法结合使用！

贪心算法的思路：

对问题求解时，总是做出在当前看来是最好的选择，也就是说贪心法开始时是不从整体考虑的。所以处的情况，只是一个局部的最优解！
【上述做法会带来一个可能出现的情况之一：如果一直保持局部最优解的过程，很有可能出现最终得到的不是一定是整体的最优解】
【虽然贪心法的算法思维、思路看起来都是比较容易的，甚至书写代码也可能比较简单，但是学习贪心算法的最终的目的：使用局部最优解的思路，但是最终必须完成它要成为整体的最优解！】
【贪心算法最困难的部分就是要证明所涉及的算法确实最终能解决整体最优解！】
【贪心算法第一个基本要素：在当前状态下做出做好的选择：局部最优】

继续对上述代码进行优化或者改写

优化或者改写1

#include<stdio.h>

int main()
{
  int m[8]={0,100,50,20,10,5,2,1};//编号从1开始用
  int gz;
  int i;
  
  printf("请任意输入你的工资:");
  scanf("%d",&gz);
  
  for(i=1;i<=7;i++)
  { 
    printf("面值是%d的人民币有%d张\n",m[i],gz/m[i]);
    gz=gz%m[i];//计算剩余的工资
  }
 
  return 0;
}
优化或者改写2 递归书写
#include<stdio.h>

void f(int gz)
{
  if(gz>=100)
  {
    printf("100元的张数是%d\n",gz/100);
    f(gz%100);//继续递归调用 
  }
  else if(gz>=50)
  {
    printf("50元的张数是%d\n",gz/50);
    f(gz%50);//继续递归调用 
  }
  else if(gz>=20)
  {
    printf("20元的张数是%d\n",gz/20);
    f(gz%20);//继续递归调用 
  }
  else if(gz>=10)
  {
    printf("10元的张数是%d\n",gz/10);
    f(gz%10);//继续递归调用 
  }
  else if(gz>=5)
  {
    printf("5元的张数是%d\n",gz/5);
    f(gz%5);//继续递归调用 
  }
  else if(gz>=2)
  {
    printf("2元的张数是%d\n",gz/2);
    f(gz%2);//继续递归调用 
  }
  else if(gz>=1)
  {
    printf("1元的张数是%d\n",gz/1);
    f(gz%1);//继续递归调用 
  }
  else
    return ;
}

int main()
{
  int gz;
  
  printf("请任意输入你的工资:");
  scanf("%d",&gz);
  
  f(gz);
 
  return 0;
}

优化或者改写3 还是想用递归，但是希望代码短一点

#include<stdio.h>

int m[8]={0,100,50,20,10,5,2,1}; 

void f(int gz,int i)
{
  if(gz>0 && i<8)
    f(gz%m[i],i+1);//调用递归函数,除开第i种纸币后剩余的工资
    
  printf("%d面值的人民币的张数是%d\n",m[i],gz/m[i]);  
} 

int main()
{
  int gz;
  
  printf("请任意输入你的工资:");
  scanf("%d",&gz);
  
  f(gz,1);//从数组 m中编号为1也就是100元开始讨论 
 
  return 0;
}

#include<stdio.h>
int a[21][6]={
0,0,0,0,0,0,
1,97,90,0,0,0,
2,92,85,96,0,0,
3,0,0,0,0,93,
4,0,0,0,80,86,
5,89,83,97,0,0,
6,82,86,0,0,0,
7,0,0,0,87,90,
8,0,97,96,0,0,
9,0,0,89,0,0,
10,95,99,0,0,0,
11,0,0,96,97,0,
12,0,0,0,93,98,
13,94,91,0,0,0,
14,0,83,87,0,0,
15,0,0,98,97,98,
16,0,0,0,93,86,
17,98,83,99,98,81,
18,93,87,92,96,98,
19,0,0,0,89,92,
20,0,99,96,95,81
};

请考虑此题用贪心的算法来书写试试看

博主注释

这道题明显是蓝桥杯第十届的组队
贪心也可以，但是你不知道自己一定对，所以推荐用DFS

思路

这里的贪心思路很明显是直接取掉最大值，但我们仍然需要注意判重，即选取一个人之后就无法再次选取这个人

注意：
这里答案虽然对了，但是这样的做法并不正确，只是在这个数据上正确而已
因为我们a[][0]优先选择最大，并且给了判重，而你无法判定这个选择是否只有当前这个位子上最大
我们也可以理解为局部最优并非全局最优？

更新版 贪心版本

#include<iostream>
#include<algorithm>

using namespace std;

const int row = 20,col=5;
int fen[row+5][col+5];
bool st[row];//判重数组
int res;
int jIdx;//用来记录需要判重的位子，即当前选择的人是第几个人

int max(int a,int b,int idx)//自定义max函数，方便判断b>a时进行操作
{
    if(a>b){return a;}
    jIdx=idx;//记录当前位子
    return b;
}

void func()
{
    for(int i=0;i<col;i++)//当col过完之后，表示五个人都被选择完毕
    {
        jIdx=0;
        int tmp=-0x3f3f3f;
        for(int j=0;j<row;j++)
            if(!st[j])tmp = max(tmp,fen[j][i],j);//如果没选择当前这个人，更新最大值，记录这个人的位置
        
        st[jIdx]=true;//选择
        res+=tmp;//求和
        //cout<<jIdx<<" "<<i<<" "<<fen[jIdx][i]<<endl;//输出当前被选择的人员
    }
}

int main()
{
    for(int i=0;i<row;i++)for(int j=0;j<col;j++)cin>>fen[i][j];
    
    func();
    
    cout<<res;//输出答案
    return 0;
}

答案

490

思考：【LeetCode】柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。
你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：[5,5,10]
输出：true
示例 3：
输入：[10,10]
输出：false
示例 4：
输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

0 <= bills.length <= 10000
bills[i] 不是 5 就是 10 或是 20

【我的要求是：输入的多个客户的支付的钱数，任意输入！！！】

分析

1）如果要使用贪心算法的思想来解决此问题，在输入所有用户的支付的钱数后，第1步应该完成：排序操作！【从小到大】
2）注意，一开始你手头没有任何零钱。
很明显应该先把所有的5元先收完。再去考虑10元和20元的情况。
3） 5元是不需要找零
10元只需要找零1张5元【情况只有一种】
20元找零有【1张10元和1张5元】【3张5元】【2种情况】
请问： 20元的找零过程是否需要讨论先后顺序？
要考虑
【我是一个老板，我一定要手里多留点儿小面值的零钞！！！】
需要3个自变量
int sum5=0;//5元的张数
int sum10=0;//10元的张数
int sum20=0;//20元的张数
4）具体分析代码的书写
#include<stdio.h>
int bills[100];

//先书写一个排序函数 冒泡法 从小到大

颜老板版本

void sort(int n)
{
  int i,j;
  for(j=n-2;j>=0;j--)
  for(i=0;i<=j;i++)
  {
    if(bills[i]>bills[i+1])
    {
      int t;
      t=bills[i];
      bills[i]=bills[i+1];
      bills[i+1]=t;
    }
  } 
} 

int changemoney(int n)//返回值为1表示true【能找开】，0表示false【找不开】 
 {
  int sum5=0;//5元的张数
  int sum10=0;//10元的张数
  int sum20=0;//20元的张数
  int i;
  //return 出了返回以外，还有一个作用是让循环提前结束，如果这里循环提前结束一定是return 0; 干的
  //如果下面循环全部做完，那就说明一定能把钱找开！！ 
  for(i=0;i<n;i++) 
  {
    if(bills[i]==5)
      sum5++;
    else if(bills[i]==10)//如果是10元，收10元，找5元 
    {
      if(sum5==0)//这里说明没有5元，则找不开 
        return 0; 
      sum10++;
      sum5--; 
    }
    else if(bills[i]==20) 
    {
      if(sum10>=1 && sum5>=1)//找1张10元和1张5元的情况 
      {
        sum20++;
        sum10--;
        sum5--;
      }
      else if(sum10==0 && sum5>=3)//找3张5元的
      {
        sum20++;
        sum5-=3;//减去3张5元 
      }
      else
        return 0;//找不开 
    }
  }
  return 1; 
 }

int main()
{
  int i,n;
  
  printf("输入顾客数量:");
  scanf("%d",&n);
  
  printf("输入%d个顾客的支付【只能输入5，10,20】:",n);
  for(i=0;i<n;i++)
    scanf("%d",&bills[i]);
  //准备调用函数 
  if(changemoney(n)==1)
    printf("true");
  else
    printf("false");
  return 0;
}

更新版

class Solution {
public:
    int cnt5,cnt10,cnt20;
    bool lemonadeChange(vector<int>& bills) {
        int f=true;
        for(int x:bills)
            if(x==5)cnt5++;
            else if(x==10&&cnt5)cnt10++,cnt5--;
            else if(x==20&&cnt10&&cnt5)cnt20++,cnt10--,cnt5--;
            else if(x==20&&cnt5>=3)cnt20++,cnt5-=3;
            else {f=false;break;}
        return f;
    }
};

博主思路

老师代码太长了，我们直接看原题做就是了

读题可知是单纯的模拟题，一堆if else 解决

提醒：

1 贪心算法 从名称上会让误解为一定要贪多，贪大的，贪价值高的

2 此题很好的论证贪心法的另外一面：贪小，少贪……

3 曾经父母正面告诫我们：生活中吃点亏不是坏事情！

4 有钱不一定是好事儿！

例如 单调递增的数字【选自LeetCode】

给定一个非负整数 N，找出小于或等于 N 的最大的整数，
同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，
我们称这个整数是单调递增的。）

示例 1:
输入: N = 10
输出: 9

示例 2:
输入: N = 1234
输出: 1234

示例 3:
输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

分析

1 得到一个数值的结果，该数值中的每位上的数值是从小到大！

2 立刻，想到，这个程序我要用蛮力法【枚举】
因为题目中例子332，因为答案是299
意味着我的第一反应是 332,331 330…… 300 299
这里明显是枚举的思路
3 对于每个需要判断的数值来说，要使用贪心算法
x=299为例
题目要求为单调递增
做数据分解
【之前的题目贪大，价值大的，贪小的，面值小的情况】
而这道题：贪什么呢？【1 贪大 2 贪尾部】
原因：任意一个正整数求个位上的数值最好求！
x%10的结果是 ，无论x多大多小，得到永远是该x数值中的个位上的数值！

但此题存在要求【单调递增】，去证明x是否是【单调递增】
意味着，我比较x中每次取出来的相邻的2个数值【比较大小】
准备2个变量 qian 和 hou 
以299为例
2就是qian
第一个9就是hou

3）具体讨论 判断某个数值x是否是【单调递增】书写为自定义函数
int qian,hou;
//先去求解x数值的个位上的的数值，注意1234求4,299求9
hou=x%10;
//再求新的x 1234->123 299->29
x=x/10;

qian=x%10;//123求3，如果是29求9

if(qian<hou)//如果这里条件为真，则就是我们所要的局部【单调递增】，这里体现的就是贪心算法
{
  //上述条件为真则继续，此刻的qian就成立接下来的hou
  hou=qian;
  x=x/10; 
}

上述if应该做循环
4）准备代码

#include<stdio.h>

int fen(int x)//对x进行判断其是否是单调递增的数值，如果是返回1，如果不是返回0
{
  
  int qian,hou;
  //先去求解x数值的个位上的的数值，注意1234求4,299求9
  hou=x%10;
  //再求新的x 1234->123 299->29
  x=x/10;
  //因为x大小不定，分解次数也不定，所以用while 
  while(x>0)
  {
    qian=x%10;//123求3，如果是29求9
    if(qian<=hou)//如果这里条件为真，则就是我们所要的局部【单调递增】，这里体现的就是贪心算法
    {
      //上述条件为真则继续，此刻的qian就成立接下来的hou
      hou=qian;
      x=x/10; 
    } 
    else//说明此刻的2个数值之间不满足 【单调递增】
      break;    
  }
  
  //判断上述循环是否做完 
  if(x==0)
    return 1;//是单调递增
  else
    return 0;//不是单调递增 

} 

int main()
{
  int x;
  
  scanf("%d",&x);
  
  //用枚举
  while(x>0)//枚举要从x本身开始递减，枚举的次数不定，所以我用while枚举
  {
    if(fen(x)==1)
    {
      printf("%d\n",x);
      break;  
    }
    
    x--;  
  } 
  return 0;
}

更新版

暴力 过不了所有数据

但是和颜老板的思路是相同的

class Solution {
public:
    bool check(int n)
    {
        int pre =n%10;
        int next = 0;
        n/=10;
        while(n)
        {
            next = n%10;
            n/=10;
            if(pre<next)return false;
            pre = next;
        }

        return true;
    }
    int monotoneIncreasingDigits(int N) {
        for(int i=N;i>=0;i--)
            if(check(i))return i;
        return 0;
    }
};

更新版 贪心

我们拿 321 来举例

这个时候 a1>a2>a3

我们可以直观察觉，直到299为止都不会有正确数据

于是我们粗略的得到 ai>ai+1时，a[0]-=1,a[i]->a[asize]=9

但是此时显然不符合231 这样的数据，因为显然只需要 229即可，所以现在的设想是 a[i]-=1,a[i+1]->a[a.size]=9

以 332来举例 我们简化为 329时，又发现不满足ai>ai+1的情况
于是我们需要把i从头再排查一遍，直接i=-1

class Solution {
public:
    vector<int>a;
    
    int monotoneIncreasingDigits(int N) {
        if(N<10)return N;

        while(N)
        {
            a.push_back(N%10);
            N/=10;
        }

        reverse(a.begin(),a.end());

        for(int i=0;i<a.size()-1;i++)
            {
                if(a[i]>a[i+1])
                    {
                        a[i]--;
                        for(int j=i+1;j<a.size();j++)a[j]=9;
                        i=-1;//感觉简直神来之笔，本来我用递归，差点没自闭
                    }
            }

        for(int i=0;i<a.size();i++)cout<<a[i]<<endl;

        int res=0;
        for(int i=0;i<a.size();i++)res=res*10+a[i];
        return res;
    }
};

最后说明：
1 关于最后这个程序，发现我最后几组乱输入的数值结果其末尾部分带连续的9.
【下来考虑此题的另外一种解法】
2 贪心算法：我个人还是觉得其实并没太多实际的框架等东西【其实有】
我个人理解，贪心算法更多体现一种编程中某个问题局部的思考方式
3 提醒：今天我讲的是最简单的贪心。

1029. 两地调度【来自LeetCode里面】

公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。
返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。

示例：

输入：[[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 A 市，费用为 10。
第二个人去 A 市，费用为 30。
第三个人去 B 市，费用为 50。
第四个人去 B 市，费用为 20。

最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

提示：
1 <= costs.length <= 100
costs.length 为偶数
1 <= costs[i][0], costs[i][1] <= 1000

思路

贪心

题目的意思就是两个城市都有一半人
要最优惠的价格

则 我们假设所有人去A，我们则肯定需要一半人去B
怎么选择着一半人，则是查找B-A正数差值最大的一半人

减去差值之后我们就相当于一半人去了A，一半人去了B，且是最优惠价格

AC代码

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
    int sum = 0;
    for(int i=0;i<costs.size();i++)sum+=costs[i][0];

    vector<int> arr;
    for(int i=0;i<costs.size();i++)arr.push_back(costs[i][0]-costs[i][1]);

    sort(arr.begin(), arr.end());

    for(int i=arr.size()-1;i>=arr.size()>>1;i--)sum-=arr[i];

    return sum;
    }
};

注明：

1.这道题没讲过
2.这道题不是作业
3.这道题没要求自学
所以应该不考