在下面尋找一些幫助來解決這個問題。我已經通過存盤每次移動的所有坐標來解決它，但是我認為這不符合時間和空間復雜性要求。
它還提到能夠修改輸入陣列。
這幾乎感覺像是一個提示或可能解決方案的一部分。
免責宣告...這不是家庭作業，我不會嘗試將任何解決方案作為我自己的解決方案。我只是好奇，也很生氣：）
我正在使用 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) 第 3 步，向南 2 步 (3, -1) -> (-2, -1) 第 4 步，向西 5 步 (-2, -1) -> (-2, 3) 第 5 步，向北 4 步 (-2, 3) -> (2, 3) 第 6 步，向東 4 步 (2, 3) -> (2, -3) 第 7 步，向南 6 步 (2, -3) -> ( -1, -3) 第 8 步，向西 3 步 (-1, -3) -> (-1, -1) 第 9 步，向北 2 步
在第 7 步和第 9 步中，烏龜觸碰到了之前的路徑，即： 在第 (2, 1) 點第 7 步在第 (2, -1) 點第 7 步 在第 (-1, -11) 點第 9 步移動
撰寫一個函式：class Solution { int solution(int[] A); } 給定海龜在陣列 A 中行走的描述，回傳海龜第一次接觸其先前路徑的移動次數，如果沒有發生這種情況，則回傳 0。例如，給定上面定義的陣列 A，函式應該回傳 7，因為海龜在第 7 次移動中在點 (2, 1) 處接觸了它的先前路徑。
假設：N是[1..100,000]范圍內的整數；陣列 A 的每個元素都是范圍內的整數
復雜度：預期的最壞情況時間復雜度為 O(N)；預期的最壞情況空間復雜度為 O(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;
}
uj5u.com熱心網友回復：
我不知道這是否是最好的解決方案，但我認為您需要從當前索引回傳 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/463766.html