पायथन में अंतिम स्थिति तक पहुंचने के लिए आवश्यक न्यूनतम संख्या में हॉप्स खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक सरणी संख्या है, जहां सभी तत्व सकारात्मक हैं। हम सूचकांक 0 पर हैं। यहाँ, सरणी में प्रत्येक तत्व उस स्थिति में हमारी अधिकतम छलांग लंबाई का प्रतिनिधित्व करता है। हमारा लक्ष्य कम छलांग के साथ अंतिम सूचकांक (n-1, जहां n अंकों का आकार है) तक पहुंचना है। तो अगर सरणी [2,3,1,1,4] की तरह है, और फिर आउटपुट 2 होगा, क्योंकि हम 0 से इंडेक्स 1 पर जा सकते हैं, फिर इंडेक्स 4 पर जा सकते हैं, यह आखिरी इंडेक्स है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• अंत:=0, कूदता है:=0, सबसे दूर:=0
• मैं के लिए 0 से लेकर अंकों की लंबाई तक - 1
  • सबसे दूर:=सबसे दूर और अंकों की अधिकतम [i] + i
  • यदि मैं अंत है, और मैं संख्या -1 की लंबाई नहीं है, तो
    • कूद में 1 की वृद्धि करें
    • अंत :=सबसे दूर
• वापसी कूदता है

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution(object):
   def jump(self, nums):
      end = 0
      jumps = 0
      farthest = 0
      for i in range(len(nums)):
         farthest = max(farthest,nums[i]+i)
         if i == end and i != len(nums)-1:
            jumps+=1
            end = farthest
      return jumps
ob = Solution()
print(ob.jump([3, 4, 3, 0, 1]))

इनपुट

[3, 4, 3, 0, 1]

आउटपुट

2