广州网站建设seo,建站优化,ps做网站首页设计教程,网络游戏的特点文章目录1. 题目2. 解题1. 题目
给你一个整数 mass #xff0c;它表示一颗行星的初始质量。 再给你一个整数数组 asteroids #xff0c;其中 asteroids[i] 是第 i 颗小行星的质量。
你可以按 任意顺序 重新安排小行星的顺序#xff0c;然后让行星跟它们发生碰撞。如果行星…
文章目录1. 题目2. 解题1. 题目
给你一个整数 mass 它表示一颗行星的初始质量。 再给你一个整数数组 asteroids 其中 asteroids[i] 是第 i 颗小行星的质量。
你可以按 任意顺序 重新安排小行星的顺序然后让行星跟它们发生碰撞。如果行星碰撞时的质量 大于等于 小行星的质量那么小行星被 摧毁 并且行星会 获得 这颗小行星的质量。否则行星将被摧毁。
如果所有小行星 都 能被摧毁请返回 true 否则返回 false 。
示例 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. 解题
贪心先吸收最小的行星的质量确保质量能 小行星
class Solution:def asteroidsDestroyed(self, mass: int, asteroids: List[int]) - bool:asteroids.sort()for m in asteroids:if mass m:mass melse:return Falsereturn True144 ms 24.4 MB Python3
题解区有一种 O(n) 的解法将小行星质量按照 [ 2n, 2n1] 分桶如果 mass 桶内最小的 m0那么 mass m0 2*m0 桶内最大的 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步