मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है और एक अन्य संख्या k है। यदि हम सूचकांक k से शुरू करते हैं और किसी भी सूचकांक i पर, हम ठीक nums[i] संख्या में चरणों से बाएं या दाएं जा सकते हैं। हमें जांचना है कि क्या हम सूची के अंत तक पहुंच सकते हैं या नहीं।
उदाहरण के लिए, यदि इनपुट है nums = [0, 0, 2, 1, 3, 3, 1, 1] k = 2, तो आउटपुट होगा True, क्योंकि यदि हम सूचकांक 2 से शुरू करते हैं, तो सूचकांक 4 पर कूदते हैं और फिर अंतिम सूचकांक 7 पर कूदते हैं।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- n := nums का आकार
- visited := आकार n की एक सूची और 0 से भरें
- tovisit := आकार 1 की एक सूची, और इसमें k डालें
- जब तक tovisit का आकार 0 से कम है, करें
- i := tovisit से अंतिम तत्व और इसे tovisit से हटाएं
- यदि i, n-1 के समान है, तो
- True वापस करें
- यदि visited[i], 1 के समान नहीं है, तो
- visited[i] := 1
- up := i + nums[i]
- down := i - nums[i]
- यदि up < n, तो
- up को tovisit के अंत में डालें
- यदि down >= 0, तो
- down को tovisit के अंत में डालें
- False वापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
class Solution: def solve(self, nums, k): n=len(nums) visited = [0]*n tovisit = [k] while len(tovisit)>0: i=tovisit.pop() if i==n-1: return True if visited[i]!=1: visited[i]=1 up=i+nums[i] dn=i-nums[i] if up=0: tovisit.append(dn) return False ob = Solution() nums = [0, 0, 2, 1, 3, 3, 1, 1] k = 2 print(ob.solve(nums, k))
इनपुट
[0, 0, 2, 1, 3, 3, 1, 1], 2
आउटपुट
True
