735. Asteroid Collision

Problem

Bài toán yêu cầu mô phỏng các vụ va chạm giữa các thiên thạch trong một hàng, dựa trên kích thước và hướng di chuyển của chúng. Các thiên thạch di chuyển sang phải (giá trị dương) và sang trái (giá trị âm). Khi hai thiên thạch gặp nhau, kết quả phụ thuộc vào kích thước của chúng:

Nếu kích thước của thiên thạch lớn hơn, thiên thạc nhỏ hơn sẽ bị phá hủy

Nếu hai thiên thạch có cùng kích thước, cả 2 sẽ bị phá hủy.

Thiên thạch di chuyển cùng hướng sẽ không va chạm

Approach

Sử dụng stack để mô phỏng các vụ va chạm → Xử lý các vụ va chạm theo thứ tự ngược lại

Init stack

Stack sẽ lưu các thiên thạch còn tồn tại sau khi xử lý va chạm

Duyệt qua từng thiên thạch trong mảng:

Nếu thiên thạch đang xét di chuyển sang phải (+), thêm nó vào stack vì nó không thể va chạm với các thiên thạch trước đó

Nếu thiên thạc đang xét di chuyển sang trái (-), kiểm tra điều kiện sau:

Va chạm xảy ra: Nếu stack không rỗng và đỉnh của stack là một thiên thạc đang di chuyển sang phải

So sánh kích thước:

Nếu thiên thạch ở đỉnh stack nhỏ hơn (abs), loại bỏ nó khỏi stack

Nếu bằng nhau, cả 2 sẽ bị phá hủy (pop đỉnh stack mà không thêm thiên thạch hiện tại)

Nếu đỉnh stack lớn hơn, thiên thạch hiện tại bị phá hủy (bỏ qua)

Không va chạm: Nếu stack rỗng hoặc đỉnh stack là một thiên thạch đang di chuyển sang trái, thêm thiên thạch hiện tại vào stack

Kết quả

Sau khi duyệt hết mảng, các thiên thạch còn lại trong stack là trạng thái cuối cùng

Solution

typescripttypescript

1function asteroidCollision(asteroids: number[]): number[] {
2    const stack: number[] = [];
3
4    for (const a of asteroids) {
5        let destroy = false;
6
7        while (stack.length > 0 && a < 0 && stack.at(-1) > 0) {
8            const top = stack.at(-1);
9
10            if (top < Math.abs(a)) {
11                stack.pop()
12            } else if (top === Math.abs(a)) {
13                stack.pop()
14                destroy = true;
15                break;
16            } else {
17                destroy = true;
18                break;
19            }
20        }
21
22        if (!destroy) {
23            stack.push(a);
24        }
25    }
26
27    return stack
28}

Loading content...

1function asteroidCollision(asteroids: number[]): number[] { 2 const stack: number[] = []; 3 4 for (const a of asteroids) { 5 let destroy = false; 6 7 while (stack.length > 0 && a < 0 && stack.at(-1) > 0) { 8 const top = stack.at(-1); 9 10 if (top < Math.abs(a)) { 11 stack.pop() 12 } else if (top === Math.abs(a)) { 13 stack.pop() 14 destroy = true; 15 break; 16 } else { 17 destroy = true; 18 break; 19 } 20 } 21 22 if (!destroy) { 23 stack.push(a); 24 } 25 } 26 27 return stack 28}