Giả sử chúng ta có một chuỗi s và một số k. Bây giờ mỗi ký tự trong chuỗi là dấu chấm ('.') Hoặc 'x', trong đó dấu chấm biểu thị khoảng trống và 'x' biểu thị một người. Ta phải kiểm tra xem có thể chọn vị trí đứng sao cho khoảng cách giữa ta và người gần ta nhất là k. (Ở đây khoảng cách giữa mỗi chỉ số lân cận là 1).
Vì vậy, nếu đầu vào là s ="x ... x ..", k =2, thì đầu ra sẽ là True, vì chúng ta có thể đứng ở s [2] hoặc s [6].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- pos:=vị trí của x tính bằng s, nếu không có, pos sẽ là -1
- nếu pos giống -1 hoặc pos> =k, thì
- trả về True
- last_x:=pos
- dist_min:=2 * k-1
- Thực hiện vòng lặp vô hạn, thực hiện
- next_x:=vị trí của x trong s từ chỉ mục last_x + 1 đến cuối (nếu không có x, nó sẽ là -1)
- nếu next_x không giống -1, thì
- nếu next_x-last_x-1> =dist_min, thì
- trả về True
- last_x:=next_x
- nếu next_x-last_x-1> =dist_min, thì
- nếu không,
- nếu kích thước của s -last_x-1> =k, thì
- trả về Sai
- nếu kích thước của s -last_x-1> =k, thì
- trả về null
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution:
def solve(self, s, k):
pos = s.find("x")
if pos==-1 or pos>=k: return True last_x = pos
dist_min = 2*k-1
while True:
next_x = s.find("x", last_x+1)
if next_x!=-1:
if next_x-last_x-1 >= dist_min:
return True
last_x = next_x
else:
if len(s)-last_x-1>=k: return True
return False
return None
ob = Solution() print(ob.solve("x...x..", 2)) Đầu vào
"x...x..", 2
Đầu ra
True