分析
不能跳出的条件为
- 跳到值为0的地方还没有跳出
- 跳到以前跳过的地方则说明进入循环,永远不能跳出。
解题思路
基于上面的分析,只需要判断出现以上两种情况时是否跳出即可。
第一种情况很好判断,第二种情况很容易想到用一个Set存储跳过的位置,每次跳到一个新位置后判断这个位置是否在Set中出现过。若出现过,说明进入循环,不能跳出,如没有出现过,则将当前位置加入Set。
BUT
仔细分析可以不用Set来存储,“进入循环,不能跳出”就意味着不会对同一个位置的值访问两次,也就意味着访问过后的位置的值可以修改。因此可以将第二种情况转化为第一种情况,即,每次跳到一个新位置后,将该位置的值置为0。
java代码
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String inputStr = sc.nextLine().trim();
sc.close();
String[] nums = inputStr.substring(1, inputStr.length() - 1).split(",");
int offset = Integer.parseInt(nums[0]);
while (offset >= 0 && offset < nums.length) {
int num = Integer.parseInt(nums[offset]);
if (num == 0){
break;
}
nums[offset] = "0";//跳过的下标置位为0
offset += num;
}
if (offset < 0 || offset >= nums.length)
System.out.println("true");
else
System.out.println("false");
}
}
京公网安备 11010502036488号