海龟穿越自己的路径拼图/算法

Question

寻找下面解决这个问题的一点帮助。我已经通过存储每次移动的所有坐标解决了这个问题，但我认为这不符合时间&空间复杂度要求。

还提到能够修改输入数组。
这几乎就像是一个提示或可能解决方案的一部分。

免责声明…这不是家庭作业& &;我不会把任何解当做我自己的。我只是好奇，有点烦:)

我使用c#

给出了一个包含N个正整数的非空零索引数组A。一个LOGO乌龟站在(0,0)向北。它使A[0]向前移动一步顺时针旋转90度。然后A[1]向前移动一步顺时针旋转90度。等等。

例如:A[0] = 1 A[1] = 3 A[2] = 2 A[3] = 5 A[4] = 4 A[5]= 4 A[6] = 6 A[7] = 3 A[8] = 2

乌龟的行走方式如下:(0,0)->(0,1)第一步，向北1步(0,1) ->(3,1)第二步，向东3步(3,1)->(3， -1)第三步，2向南(3，-1)->(-2， -1)第4步，向西5步(-2，-1)->(- 2,3)第5步，向北4步(- 2,3)->(2,3)第6步，4步East (2,3) ->(2， -3)第7步，向南6步(2，-3)->(-1， -3) 8移动，向西3步(- 1,3)->(-1， -1)第9步，向北2步

在第7步和第9步中，海龟触及其先前的路径，即:在第7步(2,1)点在第7步(2，-1)点第9步点(-1，-11)

写一个函数:class Solution {int Solution (int[] a);},给定数组a中海龟的行走描述，返回海龟第一次触碰前一个动作的次数路径，如果没有这种情况，则为0。例如，给定数组A为上面定义的函数应该返回7，因为海龟在第7步时，在点(2,1)处触碰到它之前的路径

假设:N为[1..100,000]范围内的整数;每一个数组A的元素是

范围内的整数。复杂度:期望最坏情况时间复杂度为O(N);预期最坏情况下的空间复杂度是0(1)，超出了输入存储(不是计算输入参数所需的存储空间)。

可以修改输入数组的元素。

public static int Run(int[] input)
{
for (int i = 3; i < input.Length; i++)
{
if (input[i - 1] <= input[i - 3]) //If touching previous path is possible on this move
{
if (input[i] >= input[i - 2]) //this move >= opposite side
return i + 1;
if (1 == 0) //At least 1 other case here, but i'm stumped
return i + 1;
}
}
return 0;
}

Answer 1

我不知道这是否是最好的解决方案，但我认为你需要从当前索引返回4或5来检查这些路径是否可以交叉:

public static int Run(int[] input)
{
for (int i = 3; i < input.Length; i++)
{
if (input[i-1] <= input[i-3]) //If touching previous path is possible on this move
{
if (input[i] >= input[i-2]) //this move >= opposite side
return i + 1;
int fourBack = i >= 4 ? input[i-4] : 0; // Handle case where i < 4
int fiveBack = i >= 5 ? input[i-5] : 0; // Handle case where i < 5
if (input[i-1] >= input[i-3] - fiveBack 
&& input[i]   >= input[i-2] - fourBack 
&& input[i-2] >= fourBack)
return i + 1;
}
}
return 0;
}