[LeetCode] 457. Circular Array Loop

snowell 发布于2019-08-16 13:44 / 1973人阅读

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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