【数据结构和算法】小行星碰撞

发布时间:2024年01月04日

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集


文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1?什么情况会用到栈

2.2 方法一:模拟 + 栈

三、代码

3.1 方法一:模拟 + 栈

四、复杂度分析

4.1 方法一:模拟 + 栈


前言

这是力扣的 735 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。

慢慢开始栈的模块了,这道题是一道非常好的栈的例题,很有代表性。


一、题目描述

给定一个整数数组?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

二、题解

2.1?什么情况会用到栈

栈是一种数据结构,其特点是后进先出(Last In First Out,LIFO)。在算法中,栈在很多情况下是非常有用的,下面是一些常见的情况:

  1. 括号匹配:当你有一个包含括号的字符串,并且你想要检查这个字符串中的括号是否匹配,你可以使用栈。从左到右扫描字符串,如果遇到左括号(如“(”,“{”或“[”),则将其压入栈。如果遇到右括号,则从栈顶弹出一个元素并检查它们是否匹配。如果它们不匹配,那么这个字符串就不是有效的。
  2. 深度优先搜索(DFS):在图的遍历中,栈经常被用于实现深度优先搜索。首先,将起始节点压入栈。然后,当栈不为空时,弹出栈顶元素并访问它。对于每个刚刚访问过的节点,将其未被访问过的邻居节点压入栈。
  3. 函数调用:在计算机程序的执行中,函数调用通常使用栈来管理。当一个函数被调用时,它的参数和局部变量被压入栈。当函数执行结束时,这些数据从栈中弹出。
  4. 文本编辑器中的撤销/重做功能:许多文本编辑器使用撤销/重做功能来允许用户撤销他们最近所做的更改。这些功能通常使用一个操作栈,每个操作(例如插入或删除文本)都被压入栈。用户可以多次撤销,每次撤销都从栈中弹出并反转一个操作。
  5. 解析语法:在编译原理中,栈被广泛用于解析语法。例如,在解析一个算术表达式时,你可以使用栈来保持追踪括号和操作符的优先级。

这只是栈在算法中的一些应用,实际上还有很多其他的应用场景。

2.2 方法一:模拟 + 栈

思路与算法:

由于碰撞抵消总是从相邻行星之间发生,我们可以使用「栈」来模拟该过程。

从前往后处理所有的 asteroids[i] ,使用栈存储当前未被抵消的行星,当栈顶元素方向往右,当前 asteroids[i] 方向往左时,会发生抵消操作,抵消过程根据规则进行即可。

用到变量 ok 的 true 和 false 来表示待插入栈的元素是否还大于栈顶元素。

最后把栈内元素再放入 int[] 中。


三、代码

3.1 方法一:模拟 + 栈

Java版本:

class Solution {
    public static int[] asteroidCollision(int[] asteroids) {
       ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int i : asteroids) {
            boolean ok = true;
            while (ok && !deque.isEmpty() && deque.peekLast() > 0 && i < 0) {
                int a = deque.peekLast(), b = -i;
                if (a <= b) deque.pollLast();
                if (a >= b) ok = false;
            }
            if (ok) deque.addLast(i);
        }
        int n = deque.size();
        int[] res = new int[n];
        while(!deque.isEmpty()) res[--n]=deque.pollLast();
        return res;
    }
}

C++版本:

class Solution {
public:
    static vector<int> asteroidCollision(vector<int>& asteroids) {
        deque<int> deque;
        for (int i : asteroids) {
            bool ok = true;
            while (ok && !deque.empty() && deque.back() > 0 && i < 0) {
                int a = deque.back(), b = -i;
                if (a <= b) deque.pop_back();
                if (a >= b) ok = false;
            }
            if (ok) deque.push_back(i);
        }
        vector<int> res(deque.begin(), deque.end());
        return res;
    }
};

Python版本:

from collections import deque

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        deque = deque()
        for i in asteroids:
            ok = True
            while ok and deque and deque[-1] > 0 and i < 0:
                a, b = deque[-1], -i
                if a <= b: 
                    deque.pop()
                if a >= b: 
                    ok = False
            if ok: 
                deque.append(i)
        return list(deque)

Go版本:

package main

import "fmt"

func asteroidCollision(asteroids []int) []int {
    var stack []int
    for _, i := range asteroids {
        ok := true
        for ok && len(stack) > 0 && stack[len(stack)-1] > 0 && i < 0 {
            a, b := stack[len(stack)-1], -i
            if a <= b {
                stack = stack[:len(stack)-1]
            }
            if a >= b {
                ok = false
            }
        }
        if ok {
            stack = append(stack, i)
        }
    }
    return stack
}

func main() {
    asteroids := []int{5, 10, -5}
    fmt.Println(asteroidCollision(asteroids))
}

四、复杂度分析

4.1 方法一:模拟 + 栈

  • 时间复杂度:O(n)。
  • 空间复杂度:O(n)。

文章来源:https://blog.csdn.net/kologin/article/details/135382076
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。