mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-11-04 03:33:12 +08:00
60 lines
3.3 KiB
HTML
60 lines
3.3 KiB
HTML
<p>You are playing a game involving a <strong>circular</strong> array of non-zero integers <code>nums</code>. Each <code>nums[i]</code> denotes the number of indices forward/backward you must move if you are located at index <code>i</code>:</p>
|
|
|
|
<ul>
|
|
<li>If <code>nums[i]</code> is positive, move <code>nums[i]</code> steps <strong>forward</strong>, and</li>
|
|
<li>If <code>nums[i]</code> is negative, move <code>nums[i]</code> steps <strong>backward</strong>.</li>
|
|
</ul>
|
|
|
|
<p>Since the array is <strong>circular</strong>, you may assume that moving forward from the last element puts you on the first element, and moving backwards from the first element puts you on the last element.</p>
|
|
|
|
<p>A <strong>cycle</strong> in the array consists of a sequence of indices <code>seq</code> of length <code>k</code> where:</p>
|
|
|
|
<ul>
|
|
<li>Following the movement rules above results in the repeating index sequence <code>seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...</code></li>
|
|
<li>Every <code>nums[seq[j]]</code> is either <strong>all positive</strong> or <strong>all negative</strong>.</li>
|
|
<li><code>k > 1</code></li>
|
|
</ul>
|
|
|
|
<p>Return <code>true</code><em> if there is a <strong>cycle</strong> in </em><code>nums</code><em>, or </em><code>false</code><em> otherwise</em>.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/01/img1.jpg" style="width: 402px; height: 289px;" />
|
|
<pre>
|
|
<strong>Input:</strong> nums = [2,-1,1,2,2]
|
|
<strong>Output:</strong> true
|
|
<strong>Explanation:</strong> The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
|
|
We can see the cycle 0 --> 2 --> 3 --> 0 --> ..., and all of its nodes are white (jumping in the same direction).
|
|
</pre>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/01/img2.jpg" style="width: 402px; height: 390px;" />
|
|
<pre>
|
|
<strong>Input:</strong> nums = [-1,-2,-3,-4,-5,6]
|
|
<strong>Output:</strong> false
|
|
<strong>Explanation:</strong> The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
|
|
The only cycle is of size 1, so we return false.
|
|
</pre>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/01/img3.jpg" style="width: 497px; height: 242px;" />
|
|
<pre>
|
|
<strong>Input:</strong> nums = [1,-1,5,1,4]
|
|
<strong>Output:</strong> true
|
|
<strong>Explanation:</strong> The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
|
|
We can see the cycle 0 --> 1 --> 0 --> ..., and while it is of size > 1, it has a node jumping forward and a node jumping backward, so <strong>it is not a cycle</strong>.
|
|
We can see the cycle 3 --> 4 --> 3 --> ..., and all of its nodes are white (jumping in the same direction).
|
|
</pre>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= nums.length <= 5000</code></li>
|
|
<li><code>-1000 <= nums[i] <= 1000</code></li>
|
|
<li><code>nums[i] != 0</code></li>
|
|
</ul>
|
|
|
|
<p> </p>
|
|
<p><strong>Follow up:</strong> Could you solve it in <code>O(n)</code> time complexity and <code>O(1)</code> extra space complexity?</p>
|