735. Asteroid Collision

leetcode medium

#array#csharp#leetcode#medium#stack

Task

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]

Output: true

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int[] AsteroidCollision(int[] asteroids) {
        Stack<int> stack = new Stack<int>();
        
        foreach (int asteroid in asteroids) {
            bool alive = true;
            while (alive && asteroid < 0 && stack.Count > 0 && stack.Peek() > 0) {
                int last = stack.Pop();
                if (last == -asteroid) {
                    alive = false;
                } else if (last > -asteroid) {
                    stack.Push(last);
                    alive = false;
                }
            }
            if (alive) {
                stack.Push(asteroid);
            }
        }
        
        int[] result = new int[stack.Count];
        for (int i = result.Length - 1; i >= 0; i--) {
            result[i] = stack.Pop();
        }
        
        return result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& AsteroidCollision(vector<int>& asteroids) {
        stack<int> stack = new stack<int>();
        
        foreach (int asteroid in asteroids) {
            bool alive = true;
            while (alive && asteroid < 0 && stack.size() > 0 && stack.Peek() > 0) {
                int last = stack.pop();
                if (last == -asteroid) {
                    alive = false;
                } else if (last > -asteroid) {
                    stack.push(last);
                    alive = false;
                }
            }
            if (alive) {
                stack.push(asteroid);
            }
        }
        
        vector<int>& result = new int[stack.size()];
        for (int i = result.size() - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        
        return result;
    }
}

Java solution

matched/original

import java.util.*;

public class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        
        for (int asteroid : asteroids) {
            boolean alive = true;
            while (alive && asteroid < 0 && !stack.isEmpty() && stack.peek() > 0) {
                int last = stack.pop();
                if (last == -asteroid) {
                    alive = false;
                } else if (last > -asteroid) {
                    stack.push(last);
                    alive = false;
                }
            }
            if (alive) {
                stack.push(asteroid);
            }
        }
        
        int[] result = new int[stack.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        
        return result;
    }
}

JavaScript solution

matched/original

var asteroidCollision = function(asteroids) {
    const stack = [];
    
    for (let asteroid of asteroids) {
        let alive = true;
        while (alive && asteroid < 0 && stack.length && stack[stack.length - 1] > 0) {
            const last = stack.pop();
            if (last === -asteroid) {
                alive = false;
            } else if (last > -asteroid) {
                stack.push(last);
                alive = false;
            }
        }
        if (alive) {
            stack.push(asteroid);
        }
    }
    
    return stack;
};

Python solution

matched/original

def asteroidCollision(asteroids):
    stack = []
    
    for asteroid in asteroids:
        while stack and asteroid < 0 < stack[-1]:
            if stack[-1] < -asteroid:
                stack.pop()
                continue
            elif stack[-1] == -asteroid:
                stack.pop()
            break
        else:
            stack.append(asteroid)
    
    return stack

Go solution

matched/original

package main

func asteroidCollision(asteroids []int) []int {
    stack := []int{}
    
    for _, asteroid := range asteroids {
        alive := true
        for alive && asteroid < 0 && len(stack) > 0 && stack[len(stack)-1] > 0 {
            last := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if last == -asteroid {
                alive = false
            } else if last > -asteroid {
                stack = append(stack, last)
                alive = false
            }
        }
        if alive {
            stack = append(stack, asteroid)
        }
    }
    
    return stack
}

Explanation

Algorithm

Используйте стек для отслеживания движущихся вправо астероидов.

Пройдите по массиву астероидов: Если астероид движется вправо, добавьте его в стек. Если астероид движется влево, сравните его с последним астероидом в стеке (если он есть и движется вправо): Если движущийся вправо астероид больше, текущий взорвется. Если движущийся влево астероид больше, последний астероид в стеке взорвется, и продолжите сравнение. Если они одинакового размера, оба взорвутся.

Добавьте оставшиеся астероиды из стека и текущий астероид в результат.

😎