【算法】【华为】2019华为笔试 找终点：给定一个正整数数组，最大为100个成员，从第一个成员开始，走到数组最后一个成员最少的步骤数，

■题目描述
给定一个正整数数组，最大为100个成员，从第一个成员开始，走到数组最后一个成员最少的步骤数，
第一步必须从第一元素开始，1<=步长<len/2, 第二步开始以所在成员的数字走相应的步数，如果目标不可达返回-1，只输出最少的步骤数量

1. 思路1：从前往后进行遍历，第一步走1步，求解；第一步走2步，求解，第一步走…… 走（len/2）步，分别求解，如果可以达到终点，则记录步数，如果步数足够小，则保存。这样复杂度是O($n^2$)。
2. 思路2：从后往前遍历，指针记录距离尾部距离，例如：nToTail=0，指针在9位置；nTotail=1，指针在3位置，由于3!=nToTail而且大于nToTail，不计算，指针继续前移；同样，指针一直移动，直到nToTail=6此时data[len-1-6]=6，保存此时的步长并继续向前移动，直到找到表头为止；此时，指针移动到nToTail=9,data[len-1-9]=9，所以更新最大步长为9；继续找到表头，无符合的数据了
3. 从刚才找到的最大步长开始继续往前找，令指针指向data[len-1-9]位置，更新距离为0。此时，len-1-9已经小于len/2所以可以一步到位；否则应该从9开始，继续往前找，直到找到一个步长，可以从后往前越过len/2的位置。

可以看到，思路2的耗时明显很少，采用思路2进行编码

PS：会不会有从前往后走能走通，但是从后往前走走不通的情况呢：
考虑到类似：1,3,1,2,120,1,0的输入，从后往前走，会遇到120，此时会走不通，但是走到2的时候，由于走两步到倒数第二个1，所以120并不影响。（这个证明并不严谨，大概是这个意思）
代码：

#include <iostream>

using namespace std;
/**********************************************/
// 给定一个正整数数组，最大为100个成员，从第一个成员开始，
// 走到数组最后一个成员最少的步骤数，
// 第一步必须从第一元素开始，1 <= 步长 < len / 2, 
// 第二步开始以所在成员的数字走相应的步数，如果目标不可达返回 - 1，
// 只输出最少的步骤数量
int FindEnd(int* numbers, int length) {
	if (numbers == nullptr || length <= 1)
	{
		return -1;//不存在，输出-1
	}
	int nIndex = length - 1; // 尾部指针
	int nToTailDist = 0; // 指针距离尾部距离
	int nMaxStep = 0; // 最大距离
	int nStep = 0; // 当前走的步数
	while (true)
	{
		if (nToTailDist == numbers[nIndex] && nMaxStep < nToTailDist)
		{
			// 找到可达步长
			nMaxStep = nToTailDist;
		}

		nIndex--; // 移动指针
		nToTailDist++; 

		if (nIndex < 0)
		{
			if (nMaxStep ==0)
			{    
				// 如果该回合没有找到一个最大步数，说明卡住了，没有可达步数
				return -1;
			}
			nStep++;
			nIndex = length - 1 - nMaxStep;
			if (nIndex <= length / 2)
			{
				if (nIndex>0)
				{
					nStep++;
					return nStep;
				}
				else {
					return nStep;
				}
			}
			nToTailDist = 0;
			nMaxStep = 0;
		}
	}
	return -1;
}

void Test(int v1,int v2,const char*name) {
	if (v1 == v2) {
		cout << name << ": pass" << endl;
	}
	else {
		cout<<name << ": FAIL!!" << " should be " << v2 << endl;
	}
}

void Test_FindEnd() {
	// 标准测试用例:走2步到9，从9到尾部结束
	// 答案：2
	int test1[12] = { 7,5,9,4,2,6,8,3,5,4,3,9 };
	Test(FindEnd(test1, 12), 2, "test1");

	//测试用例2：正好从第一步9步（len/2）走到9，然后到终点
	// 答案：2
	int test2[19] = { 1,2,3,4,5,2,5,6,7,9,4,2,6,8,3,5,4,3,9 };
	Test(FindEnd(test2, 19), 2, "test2");

	//测试用例3：一步就可以结束
	// 答案：1
	int test3[10] = { 9,4,2,6,8,3,5,4,3,9 };
	Test(FindEnd(test3, 10), 1, "test3");

	//测试用例4：没有路线可以到尾部1
	// 答案：-1
	int test4[4] = { 9,4,10,12};
	Test(FindEnd(test4, 4), -1, "test4");

	//测试用例5：没有路线可以到尾部2
	//答案：-1
	int test5[12] = { 1,2,4,2,1,1,100,120,1,2,3,4 };
	Test(FindEnd(test5, 12), -1, "test5");

	//测试用例6：异常输入
	// 答案：-1
	int *test6 = nullptr;
	Test(FindEnd(test6, 1), -1, "test6");

	//测试用例7：最短步数：从index=3走到4，再走到1，只需要3步
	// 答案：3
	int test7[10] = {3,1,1,1,4,1,1,1,1,1};
	Test(FindEnd(test7, 10), 3, "test7");


	//测试用例8：
	// 答案：1
	int test8[2] = { 1,1 };
	Test(FindEnd(test8, 2), 1, "test8");

	//测试用例9：异常测试
	// 答案：-1
	int test9[1] = { 1 };
	Test(FindEnd(test9, 1), -1, "test9");

	// 考虑输入0的情况
	int test10[7] = { 1,3,1,2,120,1,0 };
	Test(FindEnd(test7, 7), -1, "testA");
}

int main()
{
	Test_FindEnd();
}