पायथन में जांचें कि क्या हम शब्दों की सूची द्वारा लक्ष्य को लिख सकते हैं या नहीं

मान लीजिए हमारे पास 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]
    • dn := i - nums[i]
    • यदि up < n, तो up को tovisit के अंत में डालें।
    • यदि dn >= 0, तो dn को 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