华为OD机试之找终点

找终点

题目描述

输入描述

输出描述

用例

源码和解析
解析：

示例代码：

import java.util.ArrayList;
import java.util.List;

public class T48 {
	public static boolean flag;// 是否存在 默认为false

	public static void main(String[] args) {
		String input = "1 2 3 7 1 5 9 3 2 1 2"; // "1 2 3 7 1 5 9 3 2 1";//
												// "7 5 9 4 2 6 8 3 5 4 3 9";
		List<Integer> nums = new ArrayList<Integer>();
		for (String str : input.split(" ")) {
			nums.add(Integer.parseInt(str));
		}
		System.out.println(nums);
		int res = dfs(nums);
		if (flag)
			System.out.println("结果为：" + res);
		if (!flag)
			System.out.println("结果为：-1");
	}

	public static int dfs(List<Integer> nums) {
		int objCount = nums.size();// 步数数量
		int stype = 0;// 第几步
		if (nums.get(0) <= 0) {// 第一个数 可能 负数或0 那么步子无法迈出去
			return -1;
		}
		for (stype = 1; stype < nums.size() / 2; stype++) {
			boolean f = false;// 第一步位stype 看下是否能移动到nums的最后一个成员
			int tempStype = stype;
			int index = 0;// 移动的索引
			int count = 0;// 一开始就第一步 后面每挪动一次就加1
			int tempCount = 0;
			while (tempStype < nums.size()) {
				index += tempStype;
				// System.out.println("index:"+index+" tempStype:"+tempStype);;
				count++;
				if (index == nums.size() - 1) {
					tempCount = count;
					// System.out.println("找到了,第一步为" + stype+"步数为"+count);
					f = true;
				} else if (index < nums.size()) {
					tempStype = nums.get(index);
				} else {
					// 越界了 没找到
					break;
				}
			}
			if (f) {
				flag = true;
				if (objCount > tempCount) {
					objCount = tempCount;
				}
			}

		}
		return objCount;
	}
}

代码运行示意图