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 次浏览

启动您的 职业生涯

通过完成课程获得认证

开始