Asteroid Collision
Một hàng tiểu hành tinh bay dọc theo một đường thẳng, tất cả đều có cùng tốc độ. Mỗi giá trị trong asteroids mô tả một tiểu hành tinh: giá trị tuyệt đối là kích thước, còn dấu cho biết hướng di chuyển, số dương là sang phải và số âm là sang trái.
Khi một tiểu hành tinh di chuyển sang phải gặp một tiểu hành tinh di chuyển sang trái, chúng va chạm. Tiểu hành tinh nhỏ hơn sẽ nổ tung; nếu chúng có cùng kích thước, cả hai đều nổ tung. Các tiểu hành tinh di chuyển cùng hướng sẽ không bao giờ gặp nhau. Trả về các tiểu hành tinh còn lại sau mọi vụ va chạm, theo thứ tự ban đầu. Kết quả có thể là một danh sách rỗng.
Hàm
- asteroidsinteger-array
- các tiểu hành tinh từ trái sang phải, dấu chỉ hướng, giá trị tuyệt đối chỉ kích thước
- Trả vềinteger-array
- các tiểu hành tinh còn sót lại theo thứ tự từ trái sang phải, có thể không còn tiểu hành tinh nào
Ràng buộc
1 ≤ asteroids.length ≤ 104-1000 ≤ asteroids[i] ≤ 1000asteroids[i] ≠ 0
Ví dụ
- Đầu vào
- asteroids = [4, 9, -6, 2, -3]
- Đầu ra
- [4, 9]
- Giải thích
- 9 gặp -6 và thắng. 2 gặp -3 rồi phát nổ, sau đó -3 bay tiếp đến 9 và cũng phát nổ. Không có gì khác di chuyển về phía bất cứ thứ gì, nên 4 và 9 còn lại.
- Đầu vào
- asteroids = [6, -6]
- Đầu ra
- []
- Giải thích
- 6 và -6 va chạm với cùng kích thước, nên cả hai đều nổ tung và kết quả là rỗng.
- Đầu vào
- asteroids = [-2, -7, 3, 8]
- Đầu ra
- [-2, -7, 3, 8]
- Giải thích
- -2 và -7 bay sang trái, còn 3 và 8 bay sang phải, vì vậy hai nhóm di chuyển ra xa nhau. Chúng không bao giờ va chạm và cả bốn tiểu hành tinh đều sống sót.
Câu hỏi mở rộng
Ngăn xếp cho biết những tiểu hành tinh nào sống sót. Làm thế nào để bạn cũng báo cáo chỉ số của tiểu hành tinh đã phá hủy nó, với mỗi tiểu hành tinh phát nổ?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Một vụ va chạm cần có thiên thạch di chuyển sang phải ở bên trái và thiên thạch di chuyển sang trái ở bên phải. Thiên thạch di chuyển sang trái mà không có thiên thạch nào di chuyển sang phải ở phía trước sẽ an toàn mãi mãi. Duyệt hàng thiên thạch từ trái sang phải: những thiên thạch nào ở phía trước mà một thiên thạch mới di chuyển sang trái vẫn có thể va chạm?
Một vật thể di chuyển sang trái mới sẽ va vào vật thể di chuyển sang phải còn sống sót gần nhất trước, rồi đến vật thể tiếp theo, cứ thế cho đến khi nó phát nổ hoặc không còn vật thể di chuyển sang phải nào. Những vật thể còn sống sót cho đến lúc đó hoạt động như một ngăn xếp: chỉ vật thể mới nhất mới có thể bị va vào tiếp theo.
Giữ những đối tượng sống sót trong một ngăn xếp (stack). Đẩy mọi đối tượng di chuyển sang phải vào ngăn xếp. Với một đối tượng di chuyển sang trái, hãy lấy đối tượng ở đỉnh ra khi nó nhỏ hơn đối tượng di chuyển sang phải đó. Nếu đối tượng ở đỉnh di chuyển sang phải và có cùng kích thước, hãy lấy nó ra rồi loại bỏ đối tượng mới. Nếu đối tượng ở đỉnh lớn hơn, hãy loại bỏ đối tượng mới. Nếu không, hãy đẩy đối tượng mới vào ngăn xếp.
Lời giải
Một tiểu hành tinh di chuyển sang trái có thể phá hủy một chuỗi dài các tiểu hành tinh di chuyển sang phải, và mỗi vụ va chạm có thể làm lộ ra một cặp mới sẽ va chạm tiếp theo. Một tiểu hành tinh mới luôn gặp tiểu hành tinh sống sót gần nhất trước, nên dùng ngăn xếp để lưu các tiểu hành tinh sống sót sẽ xử lý được mọi vụ va chạm chỉ trong một lượt.
Khắc phục từng lỗi khiến chương trình bị dừng
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Hai tiểu hành tinh va chạm đúng lúc một tiểu hành tinh di chuyển sang phải nằm ngay bên trái một tiểu hành tinh di chuyển sang trái. Tìm cặp đầu tiên như vậy, giải quyết va chạm rồi quét lại từ bên trái. Khi không còn cặp nào, sẽ không có vụ va chạm nào nữa và hàng đó chính là đáp án.
Thứ tự giải quyết không quan trọng: hai tiểu hành tinh liền kề hướng vào nhau sẽ va chạm với nhau trước khi một trong hai có thể va chạm với bất kỳ tiểu hành tinh nào khác.
Mỗi vụ va chạm cần quét lại và xóa một tiểu hành tinh ở giữa hàng. Với 9,999 tiểu hành tinh nhỏ di chuyển sang phải, theo sau là -1000, mỗi lần quét sẽ đi qua hàng để phá hủy một tiểu hành tinh di chuyển sang phải: khoảng 5 × 10^7 bước.
Thuật toán
- Sao chép hàng để bạn có thể loại bỏ các tiểu hành tinh khỏi hàng đó.
- Duyệt từ trái sang phải để tìm chỉ số đầu tiên
isao chorow[i] > 0vàrow[i+1] < 0. - Nếu không có chỉ số nào như vậy, hãy trả về hàng.
- Nếu có, hãy loại bỏ tiểu hành tinh nhỏ hơn trong hai tiểu hành tinh, hoặc loại bỏ cả hai nếu chúng có kích thước bằng nhau, rồi duyệt lại.
def asteroidCollision(asteroids):
row = list(asteroids)
while True:
# A crash happens where a right-mover is directly followed by a left-mover.
hit = -1
for i in range(len(row) - 1):
if row[i] > 0 and row[i + 1] < 0:
hit = i
break
if hit == -1:
return row
right, left = row[hit], -row[hit + 1]
if right > left:
del row[hit + 1]
elif right < left:
del row[hit]
else:
del row[hit:hit + 2]Chồng những người sống sót
Ý tưởng
Giữ những tiểu hành tinh sống sót đến lúc này trên một ngăn xếp. Ngăn xếp không bao giờ chứa một tiểu hành tinh đi sang phải rồi đến một tiểu hành tinh đi sang trái, vì cặp đó đã va chạm trước đó. Vì vậy, ngăn xếp gồm một số tiểu hành tinh đi sang trái đã thoát nạn, theo sau là các tiểu hành tinh đi sang phải.
Một tiểu hành tinh mới đi sang phải sẽ bay khỏi mọi thứ trên ngăn xếp, nên bạn đẩy nó vào ngăn xếp. Một tiểu hành tinh mới đi sang trái bay về phía các tiểu hành tinh đi sang phải ở trên cùng và gặp tiểu hành tinh mới nhất trước, nên phần tử trên cùng là tiểu hành tinh duy nhất mà nó có thể va chạm tiếp theo. Trong ví dụ đầu tiên, -3 lấy 2 ra khỏi ngăn xếp, rồi phát nổ khi va chạm với 9, và ngăn xếp [4, 9] là đáp án theo thứ tự ban đầu.
Mỗi tiểu hành tinh được đẩy vào nhiều nhất một lần và lấy ra nhiều nhất một lần, nên lượt duyệt có độ phức tạp O(n) ngay cả khi một tiểu hành tinh đi sang trái dọn sạch một dãy dài.
Thuật toán
- Bắt đầu với một ngăn xếp người sống sót trống.
- Với mỗi tiểu hành tinh, nếu nó di chuyển sang phải, hãy đẩy nó vào ngăn xếp rồi tiếp tục.
- Nếu nó di chuyển sang trái, hãy lấy các tiểu hành tinh di chuyển sang phải ra khỏi đỉnh ngăn xếp khi chúng nhỏ hơn nó.
- Nếu lúc này đỉnh ngăn xếp là một tiểu hành tinh di chuyển sang phải có cùng kích thước, hãy lấy nó ra và loại bỏ tiểu hành tinh mới. Nếu đỉnh ngăn xếp là một tiểu hành tinh di chuyển sang phải lớn hơn, hãy loại bỏ tiểu hành tinh mới. Nếu không, hãy đẩy tiểu hành tinh mới vào ngăn xếp.
- Trả về ngăn xếp theo thứ tự từ dưới lên trên.
def asteroidCollision(asteroids):
survivors = [] # the row so far, after every crash it caused
for rock in asteroids:
alive = True
# Only a left-mover can hit something: a right-mover on top of the stack.
while alive and rock < 0 and survivors and survivors[-1] > 0:
top = survivors[-1]
if top < -rock:
survivors.pop() # the right-mover is smaller and explodes
elif top == -rock:
survivors.pop() # same size: both explode
alive = False
else:
alive = False # the right-mover is bigger: the new one explodes
if alive:
survivors.append(rock)
return survivors
Lỗi thường gặp và trường hợp biên
- Coi một vật thể di chuyển sang trái theo sau là một vật thể di chuyển sang phải là va chạm. Trong
[-2, -7, 3, 8], các nhóm bay ra xa nhau và cả bốn đều sống sót. - Dùng
ifthay vìwhileđể lấy các phần tử ra. Trong[1, 2, 3, 4, 5, -15], vật thể di chuyển sang trái phá hủy cả năm vật thể di chuyển sang phải và sống sót. - Bỏ sót trường hợp bằng nhau.
[6, -6]phải lấy 6 ra và bỏ -6, để lại kết quả rỗng. - Đưa vật thể di chuyển sang trái đã thua vào ngăn xếp. Trong
[9, -6], -6 phát nổ và không được đưa vào ngăn xếp; hãy dùng một cờ để xác định liệu nó còn sống hay không.
Câu hỏi thường gặp3
Độ phức tạp thời gian của Asteroid Collision là bao nhiêu?
Tốn thời gian O(n) và không gian O(n) với một ngăn xếp lưu các thiên thạch còn lại, vì mỗi thiên thạch được đưa vào và lấy ra khỏi ngăn xếp nhiều nhất một lần. Quét lại hàng sau mỗi vụ va chạm sẽ tốn O(n²).
Vì sao ngăn xếp là cấu trúc dữ liệu phù hợp cho bài toán va chạm tiểu hành tinh?
Một tiểu hành tinh mới chỉ có thể chạm đến những người sống sót gần nó nhất, và nó gặp họ theo thứ tự từ người mới nhất đến người cũ nhất. Đó là vào sau, ra trước. Những người còn lại trên ngăn xếp vào cuối cùng sẽ không thể bị va chạm nữa, nên họ là hàng cuối cùng.
Có thể giải bài toán Asteroid Collision với không gian bổ sung O(1) không?
Có, nếu bạn có thể ghi đè lên đầu vào. Dùng đầu mảng làm ngăn xếp: giữ một chỉ số ghi top, so sánh với asteroids[top-1] và trả về top phần tử đầu tiên.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def asteroidCollision(asteroids):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
asteroids = [4, 9, -6, 2, -3]
Đầu ra mong đợi
[4, 9]