Kiểm tra xem các di chuyển trong một ngăn xếp hoặc hàng đợi có khả thi hay không trong Python

Giả sử chúng ta có một danh sách nhị phân, trong đó 1 biểu thị hoạt động đẩy và 0 biểu thị hoạt động bật trên ngăn xếp hoặc hàng đợi. Chúng tôi phải kiểm tra xem tập hợp các hoạt động có thể có hợp lệ hay không.

Vì vậy, nếu đầu vào giống như nums =[1,0,1,1,0,1], thì đầu ra sẽ là Đúng vì chuỗi là [Đẩy, Pop, Đẩy, Đẩy, Pop, Đẩy] như chúng ta không phần tử bật ra từ danh sách trống để các hoạt động này hợp lệ.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• push_count:=0
• đối với tôi trong phạm vi từ 0 đến kích thước là nums - 1, thực hiện
  • nếu nums [i] là 1, thì
    • push_count:=push_count + 1
  • nếu không,
    • push_count:=push_count - 1
  • nếu push_count <0, thì
    • trả về Sai
• trả về True

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(nums):
   push_count = 0
   for i in range (len(nums)):
      if nums[i]:
         push_count += 1
      else:
         push_count -= 1
      if push_count < 0:
         return False
   return True
nums = [1,0,1,1,0,1]
print(solve(nums))

Đầu vào

[1,0,1,1,0,1]

Đầu ra

True