Cho danh sách nums: dương (bay phải), âm (bay trái), giá trị tuyệt đối là kích thước. Va chạm: tên lửa nhỏ hơn bị hủy, lớn hơn tiếp tục; bằng nhau thì cả hai hủy. Cùng hướng không va chạm. Trả về trạng thái cuối cùng.
Ví dụ: [3,8,5,-5] → [3,8] (5 và -5 hủy nhau).
Giải thuật
- Duyệt
nums, dùng danh sáchlslàm stack. - Nếu tên lửa bay phải (≥0): push vào
ls. - Nếu bay trái (<0): push, sau đó kiểm tra ngược từ trước nó trong
ls(các tên lửa bay phải) để xử lý va chạm:- Nếu |trái| > phải: xóa phải.
- Nếu bằng nhau: xóa cả hai, dừng.
- Nếu |trái| < phải: xóa trái, dừng.
- Trả về
ls.
Ví dụ minh họa
class Solution:
def solve(self, nums):
ls = [nums[0]]
for i in range(1, len(nums)):
if nums[i] >= 0:
ls.append(nums[i])
else:
ls.append(nums[i])
j = len(ls) - 2
while j >= 0 and ls[j] >= 0:
if abs(ls[-1]) > ls[j]:
ls.pop(j)
elif abs(ls[-1]) == ls[j]:
ls.pop(j)
ls.pop(-1)
break
else:
ls.pop(-1)
break
j -= 1
return ls
ob = Solution()
nums = [3, 8, 5, -5]
print(ob.solve(nums))
Đầu vào
[3, 8, 5, -5]
Đầu ra
[3, 8]