文档章节

457. Circular Array Loop

52iSilence7
 52iSilence7
发布于 2018/10/19 20:42
字数 407
阅读 42
收藏 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
粉丝 4
博文 77
码字总数 56798
作品 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......

叶枫啦啦
2018/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 是一个易于使用、功能强大而且可靠的数据处理和分发系统。它为数据流设计,支持高度可配置的指示图的数据路由、转换和系统中介逻辑。 该版本有以下值...

王练
2018/07/19
619
1
关于smarty二维数组循环显示,如何写section语句。

关于smarty二维数组循环显示,如何写section语句。附上二维数组。

eeeneo
2012/07/23
0
0
FindBugs 3.0.1 RC1 发布,Java 代码 Bug 分析插件

FindBugs 3.0.1 RC1 发布,此版本更新内容如下: 新的 Bug 模式:CAA_COVARIANT_ARRAY_FIELD, CAA_COVARIANT_ARRAY_RETURN, CAA_COVARIANT_ARRAY_LOCAL, CAA_COVARIANT_ARRAY_ELEMENT_STORE......

oschina
2015/02/23
3.6K
1

没有更多内容

加载失败,请刷新页面

加载更多

node调用dll

先安装python2.7 安装node-gyp cnpm install node-gyp -g 新建一个Electron-vue项目(案例用Electron-vue) vue init simulatedgreg/electron-vue my-project 安装electron-rebuild cnpm ins......

Chason-洪
今天
3
0
eclipse中项目svn转gitLab全过程

在工作中,我们可能会遇到项目从svn迁移到gitLab;此过程我们需要变化版本管理工具,上传代码。本篇博客记录了使用spring tool suit(sts/eclipse)进行项目迁移的全过程。 步骤: (1)端口之...

em_aaron
今天
3
0
scala学习(一)

学习Spark之前需要学习Scala。 参考学习的书籍:快学Scala

柠檬果过
今天
1
0
通俗易懂解释网络工程中的技术,如STP,HSRP等

导读 在面试时,比如被问到HSRP的主备切换时间时多久,STP几个状态的停留时间,自己知道有这些东西,但在工作中不会经常用到,就老是记不住,觉得可能还是自己基础不够牢固,知识掌握不够全面...

问题终结者
昨天
4
0
看了一下Maven的内容

了解了Maven其实是一个跨IDE的标准构建工具,能推广的原因估计是借了仓库的便利。 另一个作用是可以通过Maven的功能在社区版的IDEA去创建Web项目,下次实践看看

max佩恩
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部