文档章节

457. Circular Array Loop

52iSilence7
 52iSilence7
发布于 10/19 20:42
字数 407
阅读 11
收藏 0

Description

Difficulty : Medium

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

Points to be cared

  1. A loop starts and ends at a particular index with more than 1 element along the loop. It means a satisfied loop contains more than 1 element
  2. That the loop must be "forward" or "backward' means in a satisfied loop elements must be all postive or all negative

Mindpath:
Since the give array is guaranteed to contain no 0, we start from a index which is not zero then loop through the array.

Calculate next index and do next steps

  1. check next index is zero or not, if it is, break
  2. set next index element to zero. It means that we visited that element
  3. check the direction, if changed, break
  4. check whether next index is equal the initial index, if so, we find a loop

Code blow:

func circularArrayLoop(nums []int) bool {
    size := len(nums)
    if size <= 1 {
        return false
    }

    for i:=0;i<size;i++{
        if nums[i] == 0{
            continue
        }
        direction := nums[i] > 0
        curIndex := i
        curVal := nums[i]
        counter := 1
        for true{
            curIndex = curIndex + curVal
            if curIndex >= size {
                curIndex = curIndex - size
            } else if curIndex < 0 {
                curIndex = curIndex + size
            }
            curVal = nums[curIndex]
            //traveled
            if nums[curIndex] == 0 {
                break
            }
            nums[curIndex] = 0
            //loop detected
            if curIndex == i &&  counter > 1{
                return true
            }
            // direction changed
            if !((direction && curVal >0) || (!direction && curVal < 0)){
                break
            }
            counter++
        }
    }
    
    return false
} 

© 著作权归作者所有

共有 人打赏支持
上一篇: 284. Peeking Iterator
下一篇: 403. Frog Jump
52iSilence7
粉丝 3
博文 69
码字总数 50566
作品 0
海淀
高级程序员
私信 提问
在数组中查找一个环 Circular Array Loop

问题: 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 backwa......

叶枫啦啦
01/05
0
0
jMyCarousel

JMyCarousel is a free, highly customizable, non obstrusive image carousel. It has been created to suit a maximum of needs. It enables to display a list or gallery of images in a......

匿名
2008/09/19
3.4K
0
Apache NiFi 1.7.1 发布,数据处理和分发系统

Apache NiFi 1.7.1 已发布,Apache NiFi 是一个易于使用、功能强大而且可靠的数据处理和分发系统。它为数据流设计,支持高度可配置的指示图的数据路由、转换和系统中介逻辑。 该版本有以下值...

王练
07/19
0
0
《基于MFC的OpenGL编程》Part 13 Creating 2D and 3D Text

wglUseFontBitmaps函数 The wglUseFontBitmaps() function creates a set of bitmap display lists based on the glyphs in the currently selected font in the current DC for use in the......

嗯哼9925
2017/12/22
0
0
FindBugs 3.0.1 RC1 发布,Java 代码 Bug 分析插件

FindBugs 3.0.1 RC1 发布,此版本更新内容如下: 新的 Bug 模式:CAACOVARIANTARRAYFIELD, CAACOVARIANTARRAYRETURN, CAACOVARIANTARRAYLOCAL, CAACOVARIANTARRAYELEMENTSTORE, COCOMPARETO......

oschina
2015/02/23
3.1K
1

没有更多内容

加载失败,请刷新页面

加载更多

CentOS 安装PHP5和PHP7

安装PHP5 下载解压二进制包 [root@test-a src]# cd /usr/local/src/[root@test-a src]# wget http://cn2.php.net/distributions/php-5.6.32.tar.bz2[root@test-a src]# tar jxvf php-5.6......

野雪球
今天
4
0
windows上类似dnsmasq的软件Dual DHCP DNS Server

官网地址:http://dhcp-dns-server.sourceforge.net/官网定向的下载地址:https://sourceforge.net/projects/dhcp-dns-server/files/ 设置参考地址:http://blog.51cto.com/zhukeqiang/18264......

xueyuse0012
今天
3
0
LinkedHashMap源码解析

前言 HashMap中的元素时无序的,也就是说遍历HashMap的时候,顺序和放入的顺序是不一样的。 如果需要有序的Map,就可以采用LinkedHashMap. LinkedHashMap通过维护一个包含所有元素的双向链表,...

grace_233
今天
4
0
初识flask

文档 0.10.1版本 http://www.pythondoc.com/flask/index.html 1.0.2版本 https://dormousehole.readthedocs.io/en/latest/ 安装flask $ pip3 install flaskCollecting flask Downloading......

yimingkeji
昨天
6
0
Akka系统《sixteen》译

Actor是一个封装状态(state)和行为(behavior)的对象,它们只通过交换消息通信(放入收件人邮箱的邮件)。从某种意义上说,Actor是最严格的面向对象编程形式,但它更适合将他们视为人:在与Act...

woshixin
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部