摧毁小行星

2126. 摧毁小行星

给你一个整数 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⁵
1 <= asteroids.length <= 10⁵
1 <= asteroids[i] <= 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool asteroidsDestroyed(int mass, vector<int>& asteroids) { } };

golang 解法, 执行用时: 136 ms, 内存消耗: 8.5 MB, 提交时间: 2023-06-08 10:41:05

func asteroidsDestroyed(mass int, asteroids []int) bool {
	var min, sum [17]int
	for _, v := range asteroids {
		l := bits.Len(uint(v)) - 1
		if min[l] == 0 || v < min[l] {
			min[l] = v
		}
		sum[l] += v
	}
	for i := range min {
		if mass < min[i] {
			return false
		}
		mass += sum[i]
	}
	return true
}

golang 解法, 执行用时: 196 ms, 内存消耗: 8.4 MB, 提交时间: 2023-06-08 10:40:53

func asteroidsDestroyed(mass int, asteroids []int) bool {
	sort.Ints(asteroids)
	for _, v := range asteroids {
		if mass < v {
			return false
		}
		mass += v
	}
	return true
}

java 解法, 执行用时: 11 ms, 内存消耗: 55.7 MB, 提交时间: 2023-06-08 10:40:17

class Solution {
    //获得二进制有几位，从0开始
    public int getH(int x){
        int cnt = 0;
        while(x != 1){
            x >>= 1;
            cnt++;
        }
        return cnt;
    }
    public boolean asteroidsDestroyed(int mass, int[] asteroids) {
        //根据数据范围，最多不超过17位
        long[] sum = new long[17];
        int[] min = new int[17];
        for(int i = 0; i < asteroids.length; i++){
            int h = getH(asteroids[i]);
            if(asteroids[i] < min[h] || min[h] == 0){
                min[h] = asteroids[i];
            }
            sum[h] += asteroids[i];
        }
        long cur = mass;
        for(int i = 0; i < 17; i++){
            if(cur >= min[i]){
                cur += sum[i];
            }else{
                return false;
            }
        }
        return true;
    }
}

cpp 解法, 执行用时: 180 ms, 内存消耗: 100.6 MB, 提交时间: 2023-06-08 10:39:32

/**
 * 不排序的做法
 * 考虑将所有值按[1, 2), [2, 4), [4, 8), [2^n, 2^n+1)...分组,按顺序考虑所有非空的组,
 * 如果当前mass小于组内最小值,那么答案是false;
 * 如果当前mass大于等于组内最小值,那么加上最小值之后必然大于组内所有值,所以可以直接加上组内所有值.
 **/ 
class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
        vector<int> min(17, -1);
        vector<long long> sum(17);
        for (int i = 0; i < asteroids.size(); i += 1) {
            int h = 31 - __builtin_clz(asteroids[i]);
            if (min[h] == -1 or asteroids[i] < min[h]) min[h] = asteroids[i];
            sum[h] += asteroids[i];
        }
        long long cur = mass;
        for (int i = 0; i < 17; i += 1) {
            if (cur < min[i]) return false;
            cur += sum[i];
        }
        return true;
    }
};

python3 解法, 执行用时: 168 ms, 内存消耗: 30.1 MB, 提交时间: 2023-06-08 10:36:04

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        asteroids.sort()
        for a in asteroids:
            if a > mass:
                return False
            mass += a
        return True

上一题

下一题

详情