Chương trình kiểm tra sắp xếp chỗ ngồi lập trình viên tại hội nghị trong Python

Cho số lập trình viên n và mảng convention (1: đã có người, 0: trống). Không được hai lập trình viên ngồi cạnh nhau. Kiểm tra xem có thể cho tất cả n người vào không.

Ví dụ

Đầu vào: n = 2, convention = [0,0,1,0,0,0,1].
Đầu ra: True.

Thuật toán

1. Duyệt qua từng vị trí i của convention:
   • Xác định hàng xóm trái a và phải b (xử lý biên).
   • Nếu convention[i]==0 và cả hai hàng xóm đều 0: đặt convention[i]=1, giảm n.
2. Trả về n <= 0.

Mã nguồn Python

class Solution:
    def solve(self, n, conv):
        for i in range(len(conv)):
            a = 0 if i-1 < 0 else i-1
            b = len(conv)-1 if i+1 >= len(conv) else i+1
            if conv[i]==0 and conv[a]==0 and conv[b]==0:
                conv[i] = 1
                n -= 1
        return n <= 0

ob = Solution()
n = 2
convention = [0, 0, 1, 0, 0, 0, 1]
print(ob.solve(n, convention))

Đầu vào / Đầu ra

Input: 2, [0, 0, 1, 0, 0, 0, 1]
Output: True