LeetCode每日一题——735. 行星碰撞

简介: 给定一个整数数组 asteroids,表示在同一行的行星。

题目

给定一个整数数组 asteroids,表示在同一行的行星。

对于数组中的每一个元素,其绝对值表示行星的大小,正负表示行星的移动方向(正表示向右移动,负表示向左移动)。每一颗行星以相同的速度移动。

找出碰撞后剩下的所有行星。碰撞规则:两个行星相互碰撞,较小的行星会爆炸。如果两颗行星大小相同,则两颗行星都会爆炸。两颗移动方向相同的行星,永远不会发生碰撞

示例

示例 1:

输入:asteroids = [5,10,-5]

输出:[5,10]

解释:10 和 -5 碰撞后只剩下 10 。 5 和 10永远不会发生碰撞。

示例 2:

输入:asteroids = [8,-8]

输出:[]

解释:8 和 -8 碰撞后,两者都发生爆炸。

示例 3:

输入:asteroids = [10,2,-5]

输出:[10]

解释:2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下10 。

提示:

2 <= asteroids.length <= 104

-1000 <= asteroids[i] <= 1000

asteroids[i] != 0

思路

1.扫描一遍给定数组,记录数值为负的值的下标

2.使用队列,按顺序从小到大弹出值为负的下标

3.依次从该下标和前方所有元素相比较

4.若前方元素为负,永远不会相撞,直接跳过该下标

5.若前方元素为正,比较两元素绝对值,若负数绝对值较大,删除前方元素,继续往前比较。若正数绝对值大,删除负数元素,跳到下一个负数开始比较。若两数绝对值相等,删除两元素,跳到下一个负数比较

6.由于边比较边删除比较复杂,这里使用了几个小技巧,下标需要使用相对下标,详细见代码。

题解

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:         
        # 负数元素队列
        temp = deque()
        for i in range(len(asteroids)):
            if asteroids[i] < 0:
                temp.append(i)
        # 负数下标需要减去的相对值
        ans = 0
        # 弹出负数下标比较
        while temp:
            # 变为相对负数下标
            index = temp.popleft() - ans
            # 记录需要删除的下标
            res = []
            for i in range(index - 1, -1, -1):
                if asteroids[i] < 0:
                    break
                else:
                    if abs(asteroids[index]) > abs(asteroids[i]):
                        res.append(i)
                    elif abs(asteroids[index]) < abs(asteroids[i]):
                        res.append(index)
                        break
                    else:
                        res.append(i)
                        res.append(index)
                        break   
            # 按下标由小到大的顺序删除
            res = sorted(res)
            for i in range(len(res)):
                # 每删除一个元素,负数下标需要剪的相对值也要加1
                # 第一个元素直接删除
                if i == 0:
                    asteroids.pop(res[i])
                    ans +=1
                # 其他元素减去相对值i
                else:
                    asteroids.pop(res[i] - i)
                    ans += 1
        return asteroids


目录
相关文章
|
7月前
leetcode-913:猫和老鼠
leetcode-913:猫和老鼠
88 1
|
7月前
leetcode-735:行星碰撞
leetcode-735:行星碰撞
41 0
|
算法 C语言 C++
LeetCode 每日一题2347. 最好的扑克手牌
给你一个整数数组 ranks 和一个字符数组 suit 。你有 5 张扑克牌,第 i 张牌大小
82 0
|
算法 Android开发 容器
LeetCode 周赛上分之旅 #35 两题坐牢,菜鸡现出原形
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
94 0
|
算法 Perl
力扣266场周赛
力扣266场周赛
94 0
|
算法 C++
【每日算法Day 77】LeetCode 第 181 场周赛题解
【每日算法Day 77】LeetCode 第 181 场周赛题解
|
算法 C++ Python
【每日算法Day 63】LeetCode 第 179 场周赛题解
起床打开 leetcode,准备看看今天搞点啥题目水一水的,突然发现周赛还剩 1 小时整。看了眼题目也都挺简单的,就把 4 道题都做掉了。
|
机器学习/深度学习
【蓝桥杯集训·每日一题】 AcWing 3996. 涂色
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 区间DP Unique函数
121 0
|
C++
【力扣·每日一题】913. 猫和老鼠(C++ 记忆化搜索 博弈)
【力扣·每日一题】913. 猫和老鼠(C++ 记忆化搜索 博弈)
228 0
【力扣·每日一题】913. 猫和老鼠(C++ 记忆化搜索 博弈)
LeetCode每日一题——799. 香槟塔
我们把玻璃杯摆成金字塔的形状,其中 第一层 有 1 个玻璃杯, 第二层 有 2 个,依次类推到第 100 层,每个玻璃杯 (250ml) 将盛有香槟。
133 0
LeetCode每日一题——799. 香槟塔