需要帮助解决具有挑战性的数据结构问题

Question

我遇到了这个问题，给定一个整数数组，判断整数序列是从左、右还是死端退出数组。您从左侧输入数组并沿指定方向移动N个索引（其中N是整数的值）（正是右，负是左）

Examples
[1,1,1] -> Exits Right
[1,-2]=> Exits Left
[2,0,-1]-> Deadends
[2,5,1,-2,0]-> Exits Right

我想到的一个解决方案是，若所有整数的值都是正的，那个么就向右退出或向左退出。但是，此解决方案并不涵盖所有场景。我需要帮助来解决这个问题。

Answer 1

这里有一些粗糙的golang：

package main

import (
  "fmt"
)

func WhereIsTheExit(arr []int) {
  
  if (len(arr) == 0) {
    fmt.Println("No elements")
    return
  } 

  i := arr[0]

  for p := 1; p < len(arr); p++ {

    fmt.Printf("Current value: %d\n", i)

    if (i > len(arr) - 1 || i < 0) {
      break
    }

    i += arr[i]

    fmt.Printf("Next value: %d\n", i)
  }

  if (i >= len(arr)) {
    fmt.Println("====> right")
  } else if (i < 0) {
    fmt.Println("====> left")
  } else {
    fmt.Println("====> deadend")
  }
}

func main() {

  empty := []int{}
  deadend := []int{1,2,0,-3}
  deadend2 := []int{1,0,-1}
  right := []int{2,0,3,0,0}
  right2 := []int{1,2,0,4,0,2,7,1}
  left := []int{1,-2}
  left2 := []int{1,2,0,3,0,0,-10}

  WhereIsTheExit(empty)
  WhereIsTheExit(deadend)
  WhereIsTheExit(deadend2)
  WhereIsTheExit(right)
  WhereIsTheExit(right2)
  WhereIsTheExit(left)
  WhereIsTheExit(left2)
}

试用：https://play.golang.org/p/KU4mapYf_b3

Answer 2

你可以这样做：

• 创建一个变量以保持索引位置，并用第一个值初始化它

基于此，下面是一个使用Javascript的示例：

js lang-js prettyprint-override">function printDirection(arr) {
  let index = arr[0];
  for (let i = 1; i < arr.length; i++) {
    /**
     * Below condition covers following cases:
     * 1. If the value is undefined. This will happen if index is out of bound
     * 2. If value is 0. In this case, `index` will never change and remaining iterations can be skipped
     */
    if (!arr[index]) break;
    index += arr[index]
  }
  if (index >= arr.length) {
    console.log('Exit Right')
  } else if (index < 0) {
    console.log('Exit Left')
  } else {
    console.log('Deadend')
  }
}

const data = [
  [1, 1, 1],
  [1, -2],
  [2, 0, -1],
  [2, 5, 1, -2, 0],
]
data.forEach((arr) => printDirection(arr))