贪心算法（三） ---cmp_to_key, 力扣452，力扣179

目录

cmp_to_key

比较函数

键函数

cmp_to_key 的作用

使用 cmp_to_key

代码解释

力扣452 ---射气球

题目 

分析 

 代码

力扣179 ---最大数

题目

分析

代码 

---

 

cmp_to_key

在Python中，cmp_to_key 是一个函数，它将一个比较函数转换成一个键函数，使得比较函数可以用作排序算法的键。这个函数在Python 3中通过functools模块提供。

比较函数

在Python中，比较函数是一个接受两个参数并返回以下三种值之一的函数：

• 负数：表示第一个参数小于第二个参数。
• 零：表示两个参数相等。
• 正数：表示第一个参数大于第二个参数。

键函数

键函数是一个接受一个元素并返回一个值的函数，这个返回的值将被用作排序的依据。在Python的sort()方法或sorted()函数中，可以提供一个键函数来决定排序的方式。

cmp_to_key 的作用

由于Python的sort()方法和sorted()函数需要键函数返回的是具体的比较结果（-1、0、1），而不是比较函数的返回值（负数、零、正数），因此cmp_to_key的作用就是将比较函数转换成一个符合要求的键函数。

使用 cmp_to_key

以下是如何使用cmp_to_key的一个例子：

python
from functools import cmp_to_keydef compare_strings(a, b):# 比较两个字符串return (a > b) - (a < b)# 使用cmp_to_key将比较函数转换成键函数
sorted_strings = sorted(["banana", "apple", "cherry"], key=cmp_to_key(compare_strings))
print(sorted_strings)

在这个例子中：

• compare_strings 是一个比较函数，它比较两个字符串a和b。
• cmp_to_key(compare_strings) 将compare_strings转换成一个键函数，这个键函数可以用作sorted()函数的键。

代码解释

1. compare_strings 函数返回1、0或-1，这与Python比较操作符的返回值一致。
2. cmp_to_key(compare_strings) 将compare_strings转换为一个键函数。
3. sorted() 函数使用这个键函数对字符串列表进行排序。

力扣452 ---射气球

 

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

• 1 <= points.length <= 105
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

题目 

分析 

 代码

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if not points:return 0points.sort(key=lambda x: x[0])arrow = 1right = points[0][1]for i in range(0, len(points)):  # 修正了循环语法if right >= points[i][0]:  # 气球的开始时间小于等于当前箭的结束时间if right > points[i][1]:  # 更新箭的结束时间为当前气球的结束时间，如果它更小的话right = points[i][1]else:arrow += 1right = points[i][1]  # 新箭的结束时间是当前气球的结束时间return arrow

力扣179 ---最大数

题目

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

分析

代码 

 

class Solution:def largestNumber(self, nums: List[int]) -> str:def sort_rule(x, y):a, b = x + y, y + xif a < b: return 1elif a > b: return -1else: return 0strs = [str(num) for num in nums]strs.sort(key = cmp_to_key(sort_rule))if strs[0] == "0":return "0"return ''.join(strs)