[LeetCode] 457.循環配列ループ問題解決レポート(C ++)



457 Circular Array Loop Problem Solving Report



著者:Xue MingZhuネガティブ
id:fuxuemingzhu
個人ブログ: http://fuxuemingzhu.cn/


目次

タイトルアドレス: https://leetcode.com/problems/circular-array-loop/



トピックの説明

あなたは与えられます 円形 正と負の整数の配列nums。インデックスの数値kが正の場合、kステップ進みます。逆に、負の値(-k)の場合は、kステップ後方に移動します。配列は円形であるため、最後の要素の次の要素が最初の要素であり、最初の要素の前の要素が最後の要素であると想定できます。

numsにループ(またはサイクル)があるかどうかを判別します。サイクルは、同じインデックスで開始および終了し、サイクルの長さが1より大きい必要があります。さらに、サイクル内の動きはすべて単一の方向に従う必要があります。言い換えれば、サイクルは前進と後退の両方の動きで構成されてはなりません。



例1:

Input: [2,-1,1,2,2] Output: true Explanation: There is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.

例2:

Input: [-1,2] Output: false Explanation: The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1. By definition the cycle's length must be greater than 1.

例3:



Input: [-2,1,-1,-2,-2] Output: false Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.

注意:

  1. -1000≤nums[i]≤1000
  2. nums [i]≠0
  3. 1≤nums.length≤5000

ファローアップ:

O(n)時間計算量とO(1)余分な空間計算量でそれを解決できますか?

局所

エンドツーエンドで接続された円形アレイがあります。任意の位置から開始するように依頼しますi。ステップサイズはnums [i]で、移動するたびに、左から後ろに移動することも、後ろに移動することもできます。要するに、一方向にのみ、あなたはリングを形成することができます。リクエストリングサイズ> 1。

問題解決方法

高速および低速ポインタ

質問を読むときは、リンクリストと非常によく似た画像があることを理解する必要があります。そのため、遭遇のリングがある場合は、高速ポインタと低速ポインタを2ステップに1つずつ、1ステップに1つ使用できます。

この問題の難しさは、一方向にしか進まないことです。したがって、各サイクルの過程で、経験したすべての数字が同じ数字であることを確認する必要があります。次に、速い位置で各位置を判断する必要があります。ポインタが経験しました。開始点の番号は、whileループの判断部分である同じ記号ではありません。

スピードポインターとスローポインターが出会う場合は、リングのサイズも1ではないと判断する必要があるため、合流点の位置が1ステップの場合は十分ではありません。リングのサイズが1でない場合は、Trueを返すことができます。

移動するたびに、低速ポインタは1ステップ進み、高速ポインタは2ステップ戻ります。

Pythonコードは次のとおりです。

class Solution(object): def circularArrayLoop(self, nums): ''' :type nums: List[int] :rtype: bool ''' N, self.nums = len(nums), nums for i in range(N): slow = i fast = self.nextpos(slow) while nums[fast] * nums[i] > 0 and nums[self.nextpos(fast)] * nums[i] > 0: if fast == slow: if slow == self.nextpos(slow): break return True slow = self.nextpos(slow) fast = self.nextpos(self.nextpos(fast)) return False def nextpos(self, index): N = len(self.nums) return (index + self.nums[index] + N) % N

日付

2019年2月27日-2月が来ています