Python 程式：檢查是否可以在至少距離最近的人 k 的距離處站立

假設我們有一個字串 s 和一個數字 k。現在字串中的每個字元要麼是點 ('.') 要麼是 'x'，其中點表示空位，'x' 表示一個人。我們必須檢查是否可以選擇一個站立的位置，使得我們與最近的人之間的距離至少為 k。（這裡每個相鄰索引之間的距離為 1）。

因此，如果輸入類似於 s = "x...x.."，k = 2，則輸出將為 True，因為我們可以在 s[2] 或 s[6] 處站立。

要解決此問題，我們將遵循以下步驟 -

• pos := s 中 x 的位置，如果不存在，則 pos 將為 -1
• 如果 pos 與 -1 相同或 pos>=k，則
  • 返回 True
• last_x := pos
• dist_min := 2*k-1
• 執行無限迴圈，執行
  • next_x := s 中從索引 last_x+1 到結尾的 x 的位置（如果 x 不存在，它將為 -1）
  • 如果 next_x 與 -1 不相同，則
    • 如果 next_x-last_x-1 >= dist_min，則
      • 返回 True
    • last_x := next_x
  • 否則，
    • 如果 s 的大小 -last_x-1 >= k，則
      • 返回 False
• 返回 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

Arnab Chakraborty

更新於: 2020-10-05

48 次瀏覽

啟動您的 職業生涯

透過完成課程獲得認證

開始