[LeetCode] 457. Circular Array Loop

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

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云服務器云服務器 circular LeetCode Loop Event Loop

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

轉載請注明本文地址：http://systransis.cn/yun/72240.html

[Leetcode 622]設計循環(huán)隊列

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

canopus4u 2019-08-23 18:02 評論0 收藏0
LeetCode 622：設計循環(huán)隊列 Design Circular Queue

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

Joyven 2019-08-19 10:15 評論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 評論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 評論0 收藏0
LeetCode 之 JavaScript 解答第641題 —— 設計雙端隊列（Design Cir

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

Freeman 2019-08-23 16:58 評論0 收藏0