一个非空的整数数组(至少有一个元素,可正可负)
按规则移动后是否能跳出数组
[1]
true
[2,1,3,5]
true
[2,1,-3]
true
[1,1,1,2,-1,1,-3]
false
import java.util.Scanner;public class Main{public static void main(String args[]){Scanner sc=new Scanner(System.in);while(sc.hasNext()){String s=sc.next();String str=s.substring(1,s.length()-1);String ss[]=str.split(",");int a[]=newint[ss.length];for(int i=0;i<ss.length;i++)a[i]=Integer.parseInt(ss[i]);boolean o=false;int count=0;int k=0;while(count<=a.length){count++;k+=a[k];if(k<0||k>=a.length){o=true;break;}}System.out.println(o);}}}其实很简单，也不用专门弄个数组去标记，只要让他在里面跳a.length次，只要他其中有一次跳出来了，就为true，否则就是false了。
//关键点一: 处理入参，这里是直接输入一个字符串(表示数组)，需要进行拆分转化为数组
//关键点二: 越界的条件是当前元素下标加上元素值，如果小于0或者大于等于数组长度，就越界，返回true;
// 永不越界条件是当前元素下标加上元素值之后，跳转到之前已经访问过的元素下标，构成死循环，返回false
//辅助: 构建一个辅助数组，用于标记已经访问过的元素
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String[] strings = sc.nextLine().replace("[", "").replace("]", "").split(",");
int[] nums = new int[strings.length];
for(int i = 0; i < nums.length; ++i){
nums[i] = Integer.parseInt(strings[i].trim());
}
System.out.print(process(nums));
}
public static boolean process(int[] nums){
if(nums == null || nums.length == 0)
return false;
//使用一个额外的数组记录当前元素是否已经被访问过，如果是就返回false
int[] temp = new int[nums.length];
for(int i = 0; i < nums.length;){
if(temp[i] == 1)
return false;
int index = i + nums[i];
if(index < 0 || index >= nums.length)
return true;
temp[i] = 1;
i = index;
}
return true;
}
} 不用再去申请一个辅助数组做标记，直接再原数组上标记即可，如果某一次跳到标记过的位置，则表示跳不出来
import java.util.Scanner;
import static java.lang.System.in;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(in);
String[] str = sc.nextLine().replace("[", "").replace("]", "").split(",");
int[] data = new int[str.length];
for (int i = 0; i < data.length; i++) {
data[i] = Integer.parseInt(str[i]);
}
int i = 0;
int temp = 0;
while (true) {
if (i < 0 || i >= data.length) {
System.out.println(true);
return;
} else if (data[i] == Integer.MAX_VALUE) {
System.out.println(false);
return;
} else {
temp = data[i];
data[i] = Integer.MAX_VALUE;
i += temp;
}
}
}
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.next();
String[] strNumber = str.substring(1, str.length() - 1).split(",");
int[] number = new int[strNumber.length];
for (int i = 0; i < strNumber.length; i++) {
number[i] = Integer.parseInt(strNumber[i]);
}
int index = 0, count = 0;
while (count <= number.length) {
count++;
index += number[index];
if (index < 0 || index >= number.length) {
System.out.println("true");
return;
}
}
System.out.println("false");
}
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
const int N = 1E2;
const char* const DELIM = ",";
// ======================== The begin of function declaration =====================
char* my_strncpy(char* __destination, const char* __source, const size_t __size);
int my_strlen(const char* s);
void printArray(const int* arr, int size);
bool depth_first_search_algorithm(const int* arr, const int arrSize, int* visited, int curr);
// ======================== The end of function declaration =====================
int main(const int argc, const char* argv[]) {
char input[10 * N], str[10 * N] = {0};
gets(input);
int arr[N], visited[N] = {0}, arrSize = 0;
char* tok = strtok(my_strncpy(str, input + 1, my_strlen(input) - 2), DELIM);
while (tok) {
*(arr + arrSize++) = atoi(tok);
tok = strtok(NULL, DELIM);
}
// printArray(arr, arrSize);
bool ret = depth_first_search_algorithm(arr, arrSize, visited, 0);
return printf("%s\n", ret ? "true" : "false"), 0;
}
bool depth_first_search_algorithm(const int* arr, const int arrSize, int* visited, int curr) {
if (curr < 0 || curr >= arrSize) return true;
if (!*(arr + curr) || *(visited + curr))
return false; // 原地转圈圈 或 跳入了一个环
*(visited + curr) = 1; // mark as visited
if (depth_first_search_algorithm(arr, arrSize, visited, curr + *(arr + curr)))
return true;
return false;
}
char* my_strncpy(char* __destination, const char* __source, const size_t __size) {
// defensive programming
assert(__destination != NULL && __source != NULL);
char *p = __destination, *q = __source;
int n = __size;
while (n--) *p++ = *q++;
return __destination; // 函数调用链，是函数式编程的技巧
}
int my_strlen(const char* s) {
// defensive programming
assert(s != NULL);
if (!*s) return 0; // boundary condition
const char* p = s;
while (*++p);
return p - s;
}
void printArray(const int* arr, const int size) {
int i;
putchar('[');
for (i = 0; i < size; ++i) {
printf("%d", *(arr + i));
if (i < size - 1) printf(", ");
}
printf("]\n");
}
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
String[] strs = input.substring(1,input.length()-1).split(",");
int len = strs.length;
int[] num = new int[len];
for(int i = 0; i < len; i++){
num[i] = Integer.parseInt(strs[i]);
}
HashSet<Integer> set = new HashSet<>();
int location = 0;
while(location >= 0 && location < len){
if(!set.add(location)){
System.out.println("false");
return;
}
location += num[location];
}
System.out.println("true");
}
} 
//代码通过
string[] input = Console.ReadLine().Replace("[", "").Replace("]", "").Split(',');
int length = input.Length;
int[] arr = new int[length];
for (int i = 0; i < length; i++)
{
arr[i] = int.Parse(input[i]);
}
int index = 0;
bool isJump = true;
while (index < length && index >= 0)
{
if (arr[index] == 0)
{
isJump = false;
break;
}
int temp = arr[index];
arr[index] = 0;
index += temp;
}
Console.WriteLine(isJump.ToString().ToLower());
Console.ReadLine(); 
const readline = require('readline')
const rl = readline.createInterface({
input: process.stdin,
ouput: process.stdout
})
let inArr = []
rl.on('line',line=>{
if(!line) return
inArr.push(line.trim())
if(inArr.length === 1){
let arr = inArr[0].slice(1,-1).split(',').map(e=>+e)
let dp = new Array(arr.length+1).fill(1)
let i = 0
let flag = true
while (i<arr.length) {
dp[i]=0
i+=arr[i]
if(dp[i] == 0){
console.log(false)
flag = false
break
}
}
if(flag){
console.log(true)
}
}
}) 
//c++集合方法
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
int main()
{
int num;
vector<int> v;
int i=0;
while(getchar()!=']')
{
cin>>num;
v.push_back(num);
}
unordered_map<int,int> m;
while(true)
{
if(i>=v.size()||i<0)
{
cout<<"true";
return 0;
}
if(m.find(i)==m.end())
m.insert({i,v[i]});
else
{
cout<<"false";
return 0;
}
i+=v[i];
}
}
//java数组方法
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
String s=scanner.next();
String[] ss=s.replace("[","").replace("]","").split(",");
int[] a=new int[ss.length];
for(int i=0;i<a.length;i++)
a[i]=Integer.parseInt(ss[i]);
System.out.println(fun(a));
}
public static boolean fun(int[] a){
int index=0;
int[] temp=new int[a.length];
int i=0;
while(true)
{
if(temp[i]==1)
return false;
temp[i]=1;
i+=a[i];
if(i<0||i>=a.length)
return true;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
//总结目前牛客问题 第一,没有循环输入问题, 第二 有循环输入问题, 第三 输入有多余空格问题 ,第四 中间插入多余空行问题 ....
namespace Test0001
{
class Program
{
public static void Main(string[] args)
{
//string line;
//while (!string.IsNullOrEmpty(line = Console.ReadLine())) Func(line);
Func(Console.ReadLine());
}
public static void Func(string line)
{
var s1 = line.TrimStart('[').TrimEnd(']').Split(',').Select(x => int.Parse(x)).ToArray();
int end = s1.Length - 1, index = 0;
while (true)
{
if (s1[index] == 0)
{
Console.WriteLine("false");
return;
}
int t = index;
index += s1[index];
s1[t] = 0;//走过的位置直接变为0;
if (index < 0 || index > end)
{
Console.WriteLine("true");
return;
}
}
}
}
}
直接使用原数组,走过的位置直接赋值为0即可,因为走过的位置肯定不能再走不然无线循环肯定出不去,所以走过的位置直接赋值为0,之后遇到0就说明走不出去
使用一个计数器j来辅助判断是否有循环的情况，具体来说是使用j来和数组长度n比较，如果j在
每次i移位时自加1，易知如果有循环存在，则j肯定会大于n，当然我们可以使用任意大的正数来
辅助判断（可以设想一种很慢的跳出方式为数组每个值都为1，所以用n效率比较高）。然后我们
再以j来移位，如果j能移动到j==i，则说明循环存在。
不过这道题牛客的后台应该有问题，代码在本题运行都可以，在牛客上却不能完全AC。
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> input;
int tmp;
while(cin>>tmp)
{
input.push_back(tmp);
if(cin.get()=='\n')
break;
}
int i=0;
int j=0;
int n=input.size();
while(i<n&&i>=0)
{
if(input[i]==0)
{
cout<<"false";
break;
}
if(j>=n)
{
j=i+input[i];
while(j!=i&&j<n&&j>=0)
{
j+=input[j];
}
if(j==i)
{
cout<<"false";
break;
}
}
i+=input[i];
j++;
}
if(i>=n||i<0)
{
cout<<"true";
}
} 
def out_of(data): #用visit数组记录已访问过的下标
index, step = 0, data[0]
visit = [0] * len(data)
visit[0] = 1
while True:
index += step
if index >= len(data) or index < 0:
return True
if visit[index]:
return False
step = data[index]
visit[index] = 1
data = list(map(int, input()[1:-1].split(',')))
print('true' if out_of(data) else 'false')
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
getline(cin,s);
s = s.substr(1,s.length()-2);
istringstream ss(s);
int x;
char c;
vector<int> a;
while(ss>>x){
a.push_back(x);
if(ss>>c);
else
break;
}
bool flag = true;
bool vis[a.size()];
memset(vis, false, sizeof(vis));
int p = 0;
while(p>=0 && p<a.size()){
if(vis[p]){
flag = false;
break;
}else{
vis[p] = true;
p += a[p];
}
}
cout<<(flag?"true":"false")<<endl;
return 0;
}
import java.util.Scanner;
public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String str = sc.nextLine(); String substring = str.substring(1, str.length()-1); String[] num = substring.split(","); int a[]=new int[num.length]; for(int i=0;i<a.length;i++) { a[i]=Integer.parseInt(num[i]); } int sum=0,i=0; boolean flag=false;
//根据题意推出公式sum=sum+a[sum],sum为每次的数组下标 while(true) { i++; if(sum<0) { flag=true; break; } sum=sum+a[sum]; if(sum>=a.length) { flag=true; break; } if(i>=2000)break;//运行2000次还没有跳出循环，说明是死循环，数组永远不越界，跳出循环，返回false } System.out.println(flag); }
}
public class Test2 {
public static void main(String[] args) {
Test2 test2=new Test2();
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
System.out.println(test2.test(arr));
}
public boolean test(int[] arr) {
int len=arr.length;
int i=0;
while(i<len&&i>-1) {
if(arr[i]!=0) {
int newIndex=i+arr[i];
if(newIndex>len-1||newIndex<0) { //数组越界 返回true
return true;
}else if(arr[i]==-arr[newIndex]){ //避免在两个数之间跳来跳去
return false;
}else {
i=newIndex; //更新下次的索引下标
}
}else {
return false;
}
i++;
}
return false;
}
} 
var readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.on('line', function (input) {
var inp = input.substring(1, input.length - 1).split(',').map(item => parseInt(item))
console.log(outOrInArr(inp))
});
function outOrInArr(arr) {
let j = 0, able = true;
while (arr[j]) {
let tmp = arr[j];
arr[j] = false;
if (tmp > 0) {
j += tmp
} else if (tmp === 0) {
able = false;
break
} else if (tmp < 0) {
j += tmp
}
}
return typeof arr[j] === 'number' || arr[j] === false ? false : able;
} 
/*
我的想法，每次记录该位置的值加上下标是否能小于0或者大于数组长度，
和值在数组内的时候，将这个和值作为下一个计算的数组下标，同时将上一个计算过的数组值赋值MAX_value，
当这个下标下的数组值等于MAX的时候，跳出循环，表明不能跳出数组
*/
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
String str = input.nextLine();
//取出数组
String[] str1 = str.substring(1,str.length()-1).split(",");
//赋值给整型数组
int[] arr = new int[str1.length];
for(int i = 0;i<str1.length;i++)
arr[i] = Integer.parseInt(str1[i]);
int index = 0;//记录下标
while(index<arr.length){
if(arr[index]!=Integer.MAX_VALUE){
if(arr[index]+index<0||arr[index]+index>=arr.length){//数组越界了
System.out.println(true);
return;
}else{//数组还没有越界
int temp = arr[index];//先把这个值保存一下
arr[index] = Integer.MAX_VALUE;//将这个访问过的值标记起来
index = temp+index;//下一个坐标等于下标与对应的数组值的和
}
}else{
System.out.println(false);
return;
}
}
}
} 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
