前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 5969. 摧毁小行星(贪心)

LeetCode 5969. 摧毁小行星(贪心)

作者头像
Michael阿明
发布2022-01-07 10:40:44
2440
发布2022-01-07 10:40:44
举报
文章被收录于专栏:Michael阿明学习之路

文章目录

1. 题目

给你一个整数 mass ,它表示一颗行星的初始质量。 再给你一个整数数组 asteroids ,其中 asteroids[i] 是第 i 颗小行星的质量。

你可以按 任意顺序 重新安排小行星的顺序,然后让行星跟它们发生碰撞。如果行星碰撞时的质量 大于等于 小行星的质量,那么小行星被 摧毁 ,并且行星会 获得 这颗小行星的质量。否则,行星将被摧毁。

如果所有小行星 都 能被摧毁,请返回 true ,否则返回 false 。

代码语言:javascript
复制
示例 1:
输入:mass = 10, asteroids = [3,9,19,5,21]
输出:true
解释:一种安排小行星的方式为 [9,19,5,3,21] :
- 行星与质量为 9 的小行星碰撞。新的行星质量为:10 + 9 = 19
- 行星与质量为 19 的小行星碰撞。新的行星质量为:19 + 19 = 38
- 行星与质量为 5 的小行星碰撞。新的行星质量为:38 + 5 = 43
- 行星与质量为 3 的小行星碰撞。新的行星质量为:43 + 3 = 46
- 行星与质量为 21 的小行星碰撞。新的行星质量为:46 + 21 = 67
所有小行星都被摧毁。

示例 2:
输入:mass = 5, asteroids = [4,9,23,4]
输出:false
解释:
行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后,质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小,所以无法摧毁最后一颗小行星。
 
提示:
1 <= mass <= 10^5
1 <= asteroids.length <= 10^5
1 <= asteroids[i] <= 10^5

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/destroying-asteroids 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 贪心,先吸收最小的行星的质量,确保质量能 >= 小行星
代码语言:javascript
复制
class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        asteroids.sort()
        for m in asteroids:
            if mass >= m:
                mass += m
            else:
                return False
        return True

144 ms 24.4 MB Python3

题解区有一种 O(n) 的解法,将小行星质量按照 [ 2n, 2n+1] 分桶,如果 mass >= 桶内最小的 m0,那么 mass + m0 >= 2*m0 >= 桶内最大的


我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022/01/02 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档