পাইথনের নিকটতম পরিচিতিগুলি থেকে আমরা কমপক্ষে 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 হয়, তাহলে
  • সত্য ফেরান
• last_x :=pos
• dist_min :=2*k-1
• অসীম লুপ করুন, করুন
  • next_x :=সূচী শেষ_x+1 থেকে শেষ পর্যন্ত x-এর অবস্থান (যদি x উপস্থিত না থাকে, তাহলে -1 হবে)
  • যদি next_x -1 এর মত না হয়, তাহলে
    • যদি next_x-last_x-1>=dist_min, তারপর
      • সত্য ফেরান
    • last_x :=next_x
  • অন্যথায়,
    • যদি s -last_x-1>=k হয়, তাহলে
      • মিথ্যে ফেরত দিন
• শূন্য রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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