पायथन में जांचें कि क्या हम सूची के अंत तक k से शुरू करके पहुंच सकते हैं

मान लीजिए हमारे पास 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 < n:
                    tovisit.append(up)
                if dn >= 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