专栏首页用户6811391的专栏Python 刷题笔记:贪心算法专题二

Python 刷题笔记:贪心算法专题二

最近我们开始练习贪心算法的题目,昨天因为卡在其中一道简单级别的题目上没能更新,今天补更,正好也借着卡的点分享下经验。关于贪心算法的介绍,如果想回顾,可以点上篇来看。

当时的介绍基本引用自诸多官方描述,这两天的相关题目做下来,对贪心算法的感觉却是这更归为一种设计解法的思想,有点拆分步骤或子问题,然后逐个击破的意思。而且这贪心算法的应用,跨度比较大的题目应用起来关联性又不大,还挺麻烦的。

刷这几道题目时,有些刻意练习贪心解法,比较耗时,之后还是要提高效率,先解题,再学习掌握更优算法。来看今儿的题目吧~

题目一

「第 1029 题:两地调度」

难度:简单

公司计划面试 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,每个城市都有一半的人在面试。
#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/two-city-scheduling

题目分析

昨天我就是卡在了这道题,先说下我最初分析:既然要用贪心算法,这里有 2N 个人即 N 对人,那么我们一对对来分析,只要保证每新增一对,花费是最低的,那么最终也将是最低费用。

我们用一张图来展示题目中示例分析过程:

思路尝试

按照刚的设想,每增加一对人,我们先对他们俩的费用分析,其中一个分配去 A、另一个去 B。

但这时,要去 A 的人还要和已经被安排去 B 的所有人来进行比较,看有没有更便宜的组合来对调;同理,要去 B 的这位也要在被安排去 A 的人里进行比较一番,若有更便宜组合则对调,没有的话就按此分配。

这样,每一对人,我们都拿到了最低的分配费用,那么累计 N 对后的 2N 个人,其价格也是最低的。

代码实现

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		# 分配去 A 的名单
        list_A=[]
        # 分配去 B 的名单
        list_B=[]
        # 总人数
        length = len(costs)
		# 人数分成 n 对
        n = length//2
        # 是否要与分配好的人对调
        swap = False
		# 定义一个判断目前去AB的组合是否价格最优
        def check_AB(p,q):
        	# 若 p 去 A、q 去 B 的价格 低于 q 去 A、p 去 B 的价格
            if costs[p][0]+costs[q][1]<=costs[q][0]+costs[p][1]:
            	# 返回 (p,q)
                return (p,q)
            # 否则返回 (q,p)
            else:
                return (q,p)
		# for 循环遍历 n 对人
        for i in range(n):
        	# n 对人中第一人索引值
            first = i*2
            # 第二人索引值
            second = i*2+1
            # 获取二人去 A、B 的最优分配
            a,b = check_AB(first,second)
			# 复制下去 B 的列表
            copy_B = list_B[:]
            # 遍历去 B 的人
            for x in copy_B:
            	# 如果去 B 的人现在和要去 A 的 a 有更优的价格组合
                if check_AB(a,x)!=(a,x):
                	# 将这个原本去 B 的 x 和 a 对调
                    list_B.remove(x)
                    list_B.append(a)
                    a = x
			# 同理,遍历去 A 的人来和要去 B 的 b 来比较分析
            copy_A = list_A[:]
            for y in copy_A:
                if check_AB(y,b)!=(y,b):
                    list_A.remove(y)
                    list_A.append(b)
                    b = y
			# 将对调后的或没有对调过的 a b 分配
            list_A.append(a)
            list_B.append(b)            
		# 计算去 A 地人总费用        
        cost_a = sum([costs[i][0] for i in list_A])
        # 计算去 B 地人总费用
        cost_b = sum([costs[j][1] for j in list_B])
		# 返回二者之和
        return cost_a+cost_b

提交代码测试:

执行用时 : 64 ms, 在所有 Python3 提交中击败了 26.97% 的用户
内存消耗 : 13.8 MB, 在所有 Python3 提交中击败了 25.00% 的用户

过程比较繁琐,但是本着贪心算法来设计的,我昨天卡在了对去 A、B 两地的人遍历上,当时我没有复制列表,直接在列表上来遍历的,导致如果有人对调,那么 list_A 和 list_B 就变化影响遍历循环,导致数据差异。

同时,自定义判断去 A、B 的函数,也略显复杂,但若变下形,便能打开新思路:

costs[p][0]+costs[q][1]<=costs[q][0]+costs[p][1]
# 等效于
# p 去 A 的费用减去 B 的费用
costs[p][0]-costs[p][1]<=costs[q][0]-costs[q][1]

谁去 A 的费用减去 B 的费用更低,谁就更应该被安排去 A。掌握到这点,便能很容易理解题解里其它更直接了当的解法了。

观摩题解

题解虽然简单,但是比较坑,虽然打着贪心算法的标签,但没几个真用这算法来设计的答案。一般都是假设所有人都去 A,那么得到总费用,这时候要选 N 个人去 B,无论谁去 B 都可能会产生差价,计算每个人 B-A 的价格,价格有正负大小,当然是越小越好,挑出 N 个 B-A 最小的值,与之前总费用求和,即最终答案。

根据这思路,我的代码如下:

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        n = len(costs)//2
        # 全部人去 A 市,总费用
        all_a_cost = sum([item[0] for item in costs])
        # 每个人去 B 的话,差价
        b_a_diff = [item[1]-item[0] for item in costs]
        b_a_diff.sort()
        return all_a_cost+sum(b_a_diff[:n])

这里提到的挑出 B-A 值最小的人去 B,和我们之前代码里分析的 A-B 的值最小的人去 A 是一个道理,掌握了这点就能抓住计算的关键。

这样纯列表计算,就规避了繁杂的比较过程,提交测试表现:

执行用时 : 48 ms, 在所有 Python3 提交中击败了 72.29% 的用户
内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 25.00% 的用户

题目二

「第 135 题:分发糖果」

难度:困难

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。

你需要按照以下要求,帮助老师给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。
  • 相邻的孩子中,评分高的孩子必须获得更多的糖果。

那么这样下来,老师至少需要准备多少颗糖果呢?

示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果,这已满足上述两个条件。
#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/candy

题目分析

题做多了,会先被难度级别唬住,看到困难题就会有即使做不出、看题解也理所当然的想法。这里摘录这道题的原因是,它这个解法的思路不再是针对 N 个孩子每人如何如何逐步分,而是按照规则来整体正反两个方向来做处理。

这里我是参考的题解中一份阐述非常明确解法:按照规则每人先分一个糖,从左向右遍历孩子们的分数,若右侧孩子分高于左侧,那么高分的孩子是低分孩子糖数 + 1,这里只处理右侧高于左侧的情况。这么过一遍后,正向来看,规则满足了。

如图,假设孩子们分数 [5,7,8,3,4,2,1],正向分糖:

图片、解法链接:
https://leetcode-cn.com/problems/candy/solution/candy-cong-zuo-zhi-you-cong-you-zhi-zuo-qu-zui-da-/

还有可能,左侧分数高于右侧,这个如果从左向右正向看的话,不好为它们设置分数,因为右侧还有更多孩子没有分配,所以这种情况就从右往左看,就转化成了刚刚问题、只不过调换了方向而已。

但要注意的是,若左侧分数高于右边、且糖数已经多于右边时,不要减少左侧糖数,因为它的数目是由从左到右正向累计上去的。

代码实现

class Solution:
    def candy(self, ratings: List[int]) -> int:
    	# 获取人数长度
        length = len(ratings)        
        if length<2:
            return 1
        # 每人分一个糖
        candy_list = [1]*length
        # 正向遍历
        for i in range(1,length):
        	# 若右侧比左侧分数高
            if ratings[i]>ratings[i-1]:
            	# 右侧分糖比左侧多 1 个
                candy_list[i] = candy_list[i-1]+1
		# 逆向遍历,还是用的原索引,但倒序
        for j in range(length-2,-1,-1):
        	# 如果左侧比右侧分数高
            if ratings[j]>ratings[j+1]:
            	# 如果左侧糖不比右侧高的话
                if candy_list[j]<=candy_list[j+1]:
                	# 左侧糖提高到右侧 +1
                    candy_list[j] = candy_list[j+1]+1
        # 返回糖数列表求和
        return sum(candy_list)

提交测试表现:

执行用时 : 80 ms, 在所有 Python3 提交中击败了 85.68% 的用户
内存消耗 : 15.7 MB, 在所有 Python3 提交中击败了 25.00% 的用户

看,困难级别的题目,代码却很简单,关键就是算法思路的设计。

结论

当然,还有几道题目,时间关系来不及记录了,选这两个题目的原因:贪心算法并不局限于分步骤优化解决问题,像第二题中正反两个方向能涵盖所有问题要求、那么再逐个击破就可以了;第一题贪心算法设计起来很麻烦,但却能挖掘出简单算法里核心点,有了这种铺垫,设计简单算法会更容易些。

很多标着贪心算法标签的题目题解却是其它众多精巧解法,可能第一时间觉得挺坑,但分析下来也是有些关联的。可能我们初次接触掌握不来,但多练练也就把它们拿下了。

本文分享自微信公众号 - TTTEED(TEDxPY),作者:TED

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 链表合并与节点交换——LeetCode 第 23&24 题

    今天的两道题目全都围绕链表,第一个是困难级别的、要合并多个排序的链表;第二题是中等难度,需要两两交换链表中的节点,昨天没能用递归法写出代码,今天就尝试用递归实现...

    TTTEED
  • 2019了,一起来学Python?

    我很惭愧,给了自己诸多借口,将Python学习给搁置了,一直拖到了2019年。时不我待,趁着有精力有兴趣,我要重启学习计划了。

    TTTEED
  • Python 刷题笔记:贪心算法专题一

    LeetCode 每月都会搞每日一题活动,昨天的题目是贪心算法类型,折腾好久才做出来,索性今天就围绕贪心算法多看几道。

    TTTEED
  • Java源码系列(2):Iterable接口

    对于以数组形式存储的多条数据,我们通常是用下表index来遍历数组,或进行相关操作,结构如下:

    陈琛
  • 9.python while循环

    经过昨天的学习,相信大家已经对python的条件判断表达式if/else有一定的了解了,那么我们今天配合昨天的课程讲解一个新概念 – while循环 。

    猿说编程[Python和C]
  • python while循环

    经过昨天的学习,相信大家已经对python的条件判断表达式if/else有一定的了解了,那么我们今天配合昨天的课程讲解一个新概念 – while循环 。

    猿说编程[Python和C]
  • Vue3 深度解析

    距离尤雨溪首次公开 Vue3 (vue-next)源码有一个多月了。青笔观察到,刚发布国庆期间,出现不少解读 Vue3 源码的文章。当然不少有追风蹭热之嫌,文章...

    我是一条小青蛇
  • 如何使用chrome浏览器调试?

    在chrome浏览器中打开http://localhost:3000,按F12,或者右击->单击【检查】.

    贺贺V5
  • Flask 模板 - 变量、过滤器

    在大型应用中,把业务逻辑和表现内容放在一起,会增加代码的复杂度和维护成本。这次的模板内容主要的作用即是承担视图函数的另一个作用,即返回响应内容。

    Devops海洋的渔夫
  • JAVA设计模式之工厂模式(简单工厂模式+工厂方法模式)

    在面向对象编程中, 最通常的方法是一个new操作符产生一个对象实例,new操作符就是用来构造对象实例的。但是在一些情况下, new操作符直接生成对象会带来一些问...

    秃头哥编程

扫码关注云+社区

领取腾讯云代金券