यह जांचने के लिए कार्यक्रम कि वृत्ताकार चक्रीय सूची में कोई आगे का रास्ता है या नहीं, पायथन में नहीं है

मान लीजिए हमारे पास एक वृत्ताकार सूची है जिसे अंक कहते हैं। तो पहला और आखिरी तत्व पड़ोसी हैं। तो किसी भी सूचकांक से शुरू करते हुए कहते हैं कि, हम अंक [i] कदमों की संख्या आगे बढ़ा सकते हैं यदि अंक [i] एक सकारात्मक मान है, अन्यथा पीछे की तरफ अगर यह नकारात्मक मान है। हमें यह जांचना होगा कि क्या कोई चक्र है जिसकी लंबाई एक से अधिक है कि पथ केवल आगे की ओर जाता है या केवल पीछे की ओर जाता है।

इसलिए, यदि इनपुट nums =[-1, 2, -1, 1, 2] जैसा है, तो आउटपुट ट्रू होगा, क्योंकि आगे का रास्ता है [1 -> 3 -> 4 -> 1]

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

• n :=अंकों का आकार
• यदि n, 0 के समान है, तो
  • झूठी वापसी
• देखा:=आकार n की एक सरणी और 0 से भरें
• अंकों में प्रत्येक तत्व x के लिए x mod n प्राप्त करके अंक अपडेट करें
• इटर:=0
• मैं के लिए 0 से n -1 की सीमा में, करो
  • यदि अंक [i] 0 के समान है, तो
    • अगले पुनरावृत्ति के लिए जाएं
  • iter :=iter + 1
  • स्थिति:=सत्य
  • नकारात्मक:=सच
  • करी:=मैं
  • निम्नलिखित को बार-बार करें
    • यदि nums[curr] और देखा [curr] iter के समान है, तो
      • सही लौटें
    • यदि देखा जाए[curr] गैर-शून्य है, तो
      • लूप से बाहर आएं
    • यदि अंक [कर्र]> 0, तो
      • नकारात्मक:=गलत
    • अन्यथा,
      • स्थिति :=असत्य
    • अगर नकारात्मक और पॉज़ दोनों झूठे हैं, तो
      • लूप से बाहर आएं
    • देखा[कर्र] :=iter
    • curr:=(curr + nums[curr] + n) mod n
    • यदि nums[curr] 0 के समान है, तो
      • लूप से बाहर आएं
• झूठी वापसी

उदाहरण

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

def solve(nums):
   n = len(nums)
   if n == 0:
      return False
   seen = [0]*n
   nums = [x % n for x in nums]
   iter = 0
   for i in range(n):
      if nums[i] == 0:
         continue
      iter += 1
      pos = True
      neg = True
      curr = i
      while True:
         if nums[curr] and seen[curr] == iter:
            return True
         if seen[curr] :
            break
         if nums[curr] > 0:
            neg = False
         else:
            pos = False
         if not neg and not pos:
            break
         seen[curr] = iter
         curr = (curr + nums[curr] + n) % n
         if nums[curr] == 0:
            break
   return False

nums = [-1, 2, -1, 1, 2]
print(solve(nums))

इनपुट

[-1, 2, -1, 1, 2]

आउटपुट

True