โปรแกรมตรวจสอบว่าเราสามารถยืนห่างจากผู้ติดต่อที่ใกล้ที่สุดใน Python ได้อย่างน้อย k หรือไม่

สมมติว่าเรามีสตริง s และตัวเลข k ตอนนี้อักขระแต่ละตัวในสตริงคือจุด ('.') หรือ 'x' โดยที่จุดระบุพื้นที่ว่างและ 'x' หมายถึงบุคคล เราต้องตรวจสอบว่าสามารถเลือกตำแหน่งที่จะยืนได้หรือไม่ โดยให้ระยะห่างระหว่างเรากับคนที่อยู่ใกล้ที่สุดเราอย่างน้อย k (ในที่นี้ระยะห่างระหว่างดัชนีข้างเคียงแต่ละอันคือ 1)

ดังนั้น หากอินพุตเป็น s ="x...x..", k =2 เอาต์พุตจะเป็น True เนื่องจากเราสามารถยืนที่ s[2] หรือ s[6]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• pos :=ตำแหน่งของ x ใน s หากไม่มี pos จะเป็น -1
• ถ้า pos เหมือนกับ -1 หรือ pos>=k แล้ว
  • คืนค่า True
• last_x :=ตำแหน่ง
• dist_min :=2*k-1
• ทำวนไม่สิ้นสุด ทำ
  • next_x :=ตำแหน่งของ x ใน s จากดัชนี last_x+1 ถึงจุดสิ้นสุด (หากไม่มี x จะเป็น -1)
  • ถ้า next_x ไม่เหมือนกับ -1 แล้ว
    • ถ้า next_x-last_x-1>=dist_min แล้ว
      • คืนค่า True
    • last_x :=next_x
  • มิฉะนั้น
    • ถ้าขนาดของ s -last_x-1>=k แล้ว
      • คืนค่าเท็จ
• คืนค่า null

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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))

อินพุต

"x...x..", 2

ผลลัพธ์

True