मान लीजिए हमारे पास पूर्णांकों की एक सरणी है, जहां सभी तत्व धनात्मक हैं। प्रारंभिक प्रारंभिक बिंदु इंडेक्स 1 पर है। सरणी में प्रत्येक तत्व उस स्थिति पर हमारी अधिकतम छलांग लंबाई दर्शाता है। हमारा लक्ष्य अंतिम कोशिका तक कम से कम छलांग के साथ पहुंचना है। इसलिए यदि सरणी [2,3,1,1,4] जैसी है, तो आउटपुट 2 होगा, क्योंकि हम इंडेक्स 0 से 1 पर कूद सकते हैं, फिर इंडेक्स 4 पर कूद सकते हैं, जो अंतिम इंडेक्स है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
end := 0, jumps := 0, farthest := 0
i के लिए range 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([2,3,1,1,4]))
इनपुट
[2,3,1,1,4]
आउटपुट
2