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

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

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

• end := 0, jumps := 0, farthest := 0
• i के लिए 0 से nums की लंबाई - 1 तक की रेंज में
  • farthest := farthest और nums[i] + i का अधिकतम
  • यदि i, end है, और i, nums की लंबाई - 1 नहीं है, तो
    • jumps को 1 से बढ़ाएं
    • end := farthest
• jumps वापस करें

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

उदाहरण

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