[LeetCode] 457. Circular Array Loop

snowell 發布于2019-08-16 13:44 / 1981人閱讀

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

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/72240.html

[Leetcode 622]設計循環隊列

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

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

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

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

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