Giả sử chúng ta có một số n, có n số người đang tìm kiếm một chỗ ngồi, chúng ta cũng có một danh sách các bit trong đó 1 đại diện cho một chỗ đã có người ngồi và 0 đại diện cho một chỗ trống. Không có hai người nào có thể ngồi cạnh nhau, vì vậy chúng tôi phải kiểm tra xem tất cả n người có thể tìm thấy một chỗ ngồi hay không.
Vì vậy, nếu đầu vào giống như n =2 ghế =[1, 0, 0, 0, 1, 0, 0], thì đầu ra sẽ là Đúng, vì chúng có thể đặt ở chỉ mục 2 và 6.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- chèn 0 ở đầu chỗ ngồi và chèn [0, 1] vào cuối chỗ ngồi
- res:=0, gap:=0
- đối với mỗi tôi trên ghế, hãy thực hiện
- nếu tôi giống 0, thì
- gap:=gap + 1
- ngược lại khi khoảng cách> 0, thì
- res:=res + tầng của (khoảng cách - 1) / 2
- khoảng cách:=0
- nếu tôi giống 0, thì
- trả về true khi res> =n, ngược lại là false
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(n, seats): seats = [0] + seats + [0, 1] res = 0 gap = 0 for i in seats: if i == 0: gap += 1 elif gap > 0: res += (gap - 1) // 2 gap = 0 return res >= n n = 2 seats = [1, 0, 0, 0, 1, 0, 0] print(solve(n, seats))
Đầu vào
2, [1, 0, 0, 0, 1, 0, 0]
Đầu ra
True