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

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

ตัวอย่าง

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

ขั้นตอนการแก้ปัญหา

1. pos := ตำแหน่งของ 'x' ใน s, หากไม่มีจะเป็น -1
2. ถ้า pos เป็น -1 หรือ pos >= k ให้คืนค่า True
3. last_x := pos
4. dist_min := 2*k - 1
5. ลูปไม่รู้จบ:
   • next_x := ตำแหน่งของ 'x' ใน s จากดัชนี last_x + 1 ถึงสุดท้าย (หากไม่มีจะเป็น -1)
   • ถ้า next_x ไม่ใช่ -1:
     • ถ้า next_x - last_x - 1 >= dist_min ให้คืนค่า True
     • last_x := next_x
   • อื่นๆ:
     • ถ้า len(s) - last_x - 1 >= k ให้คืนค่า True
     • คืนค่า False
6. คืนค่า None

การใช้งาน

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