[LeetCode] 457. Circular Array Loop

snowell 發(fā)布于2019-08-16 13:44 / 1974人閱讀

Problem

You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it"s negative (-n), move backward n steps. Assume the first element of the array is forward next to the last element, and the last element is backward next to the first element. Determine if there is a loop in this array. A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be "forward" or "backward".

Example 1: Given the array [2, -1, 1, 2, 2], there is a loop, from index 0 -> 2 -> 3 -> 0.

Example 2: Given the array [-1, 2], there is no loop.

Note: The given array is guaranteed to contain no element "0".

Can you do it in O(n) time complexity and O(1) space complexity?

Solution

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        if (nums == null || nums.length <= 2) return false;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) return false;
            int slow = i, fast = getIndex(nums, i);
            while (nums[fast] * nums[i] > 0 && nums[getIndex(nums, fast)] * nums[i] > 0) {
                if (slow == fast) {
                    if (slow == getIndex(nums, slow)) break;
                    return true;
                }
                slow = getIndex(nums, slow);
                fast = getIndex(nums, getIndex(nums, fast));
            }
            slow = i;
            int pre = nums[i];
            while (nums[slow] * pre > 0) {
                int next = getIndex(nums, slow);
                nums[slow] = 0;
                slow = next;
            }
        }
        return false;
    }
    private int getIndex(int[] nums, int i) {
        int len = nums.length;
        int next = i+nums[i];
        return next >= 0 ? next%len : next%len+len;
    }
}

GPU云服務(wù)器云服務(wù)器 circular LeetCode Loop Event Loop

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/72240.html

相關(guān)文章

[Leetcode 622]設(shè)計(jì)循環(huán)隊(duì)列

摘要：循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于先進(jìn)先出原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。它也被稱為環(huán)形緩沖器。但是使用循環(huán)隊(duì)列，我們能使用這些空間去存儲(chǔ)新的值。檢查循環(huán)隊(duì)列是否已滿。設(shè)計(jì)你的循環(huán)隊(duì)列實(shí)現(xiàn)。循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。它也被稱為環(huán)形緩沖器。循環(huán)隊(duì)列的一個(gè)好處是我們可以利用這個(gè)隊(duì)列之前...

canopus4u 2019-08-23 18:02 評(píng)論0 收藏0
LeetCode 622：設(shè)計(jì)循環(huán)隊(duì)列 Design Circular Queue

摘要：刪除操作也被稱為出隊(duì)。如上所述，隊(duì)列應(yīng)支持兩種操作入隊(duì)和出隊(duì)。循環(huán)隊(duì)列此前，我們提供了一種簡(jiǎn)單但低效的隊(duì)列實(shí)現(xiàn)。更有效的方法是使用循環(huán)隊(duì)列。它也被稱為環(huán)形緩沖器。檢查循環(huán)隊(duì)列是否已滿。表示隊(duì)列的起始位置，表示隊(duì)列的結(jié)束位置。 LeetCode 622：設(shè)計(jì)循環(huán)隊(duì)列 Design Circular Queue 首先來(lái)看看隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)：隊(duì)列：先入先出的數(shù)據(jù)結(jié)構(gòu) showImg(ht...

Joyven 2019-08-19 10:15 評(píng)論0 收藏0
[LeetCode] 426. Convert BST to Sorted Doubly Linke

Problem Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list. Lets take the foll...

MartinDai 2019-08-16 13:28 評(píng)論0 收藏0
[LeetCode] 398. Random Pick Index (Reservoir Sampl

Problem Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array. Note:The array siz...

edagarli 2019-08-16 13:46 評(píng)論0 收藏0
LeetCode 之 JavaScript 解答第641題 —— 設(shè)計(jì)雙端隊(duì)列（Design Cir

摘要：小鹿題目設(shè)計(jì)實(shí)現(xiàn)雙端隊(duì)列。你的實(shí)現(xiàn)需要支持以下操作構(gòu)造函數(shù)雙端隊(duì)列的大小為。獲得雙端隊(duì)列的最后一個(gè)元素。檢查雙端隊(duì)列是否為空。數(shù)組頭部刪除第一個(gè)數(shù)據(jù)。以上數(shù)組提供的使得更方便的對(duì)數(shù)組進(jìn)行操作和模擬其他數(shù)據(jù)結(jié)構(gòu)的操作，棧隊(duì)列等。 Time：2019/4/15Title: Design Circular DequeDifficulty: MediumAuthor: 小鹿題目：Desi...

Freeman 2019-08-23 16:58 評(píng)論0 收藏0