使用陣列解決Java任務

-1

我試圖編寫一個解決方案來解決與Java中的數組相關的問題。問題是這樣的：使用陣列解決Java任務

您正在給定長度Ñ的陣列，從0索引到Ñ - 1.該數組的每個元素是0或1只能移動到索引其中包含0.首先你在0 ^第位置。在每一步你可以做以下事情之一：

向前或向後走一步。

跳過正確長度m轉發。

這意味着你可以從位置x移動到X + 1，X - 在一個移動1或X米。新位置必須包含0.也可以移動到大於n-1的任何位置。

你不能從位置0向後移動。如果你移動到任何大於n-1的位置，你就贏了比賽。

鑑於數組和跳躍的長度，您需要確定是否有可能贏得比賽。

這裏是例子測試用例：
6 5 
0 0 0 1 1 1 
YES 
6 3 
0 0 1 1 1 0 
NO 

我的代碼：

import java.io.*; 
import java.util.*; 

public class hcrkarryjump { 

    public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 
     int n = sc.nextInt(); 
     int m = sc.nextInt(); 
     int a[]=new int[n]; 
     for(int k=0;k<n;k++) 
      a[k]=sc.nextInt(); 
     int i=0; 
     while(i<n){ 
      if(a[i]==0) 
       i++; 
      if(a[i]==1){ 
       if(a[i+1]==0 &&(i+m>=n-1)) 
        System.out.println("YES"); 
       else 
        System.out.println("NO"); 
      } 
     } 
    } 
}

的代碼進入一個無限循環，並請糾正我，如果有任何錯誤。

來源

2016-05-31 Sai Pardhu

歡迎來到StackOverflow。請閱讀我們的[問]頁面提示如何改善您的問題。偉大的問題傾向於從社區提供更快，更好的答案 – ochi

@ochi：我認爲這個問題很好，問題是有一個無限循環。看到無限循環發生的地方也很清楚。 – Makoto

_「這意味着你可以從一個位置移動到另一個位置」 - 爲什麼你忽略了關鍵信息？定位到什麼「一舉」？ –

你得到一個無限循環，因爲你從來沒有一次你到A [1] == 1

爲了避免無限循環增加，你的代碼應該是：

import java.io.*; 
import java.util.*; 

public class hcrkarryjump { 

    public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 
     int n = sc.nextInt(); 
     int m = sc.nextInt(); 
     int a[]=new int[n]; 
     for(int k=0;k<n;k++) 
      a[k]=sc.nextInt(); 
     int i=0; 
     while(i<n){ 
      // Check if we have something to do 
      if(a[i]==1){ 
       // We do stuff 
       if(a[i+1]==0 &&(i+m>=n-1)) 
        System.out.println("YES"); 
       else 
        System.out.println("NO"); 
      } 
      // and increment for the while check and next loop 
      i++; 
     } 
    } 
}

來源

2016-05-31 21:54:20 TheBakker

我不太瞭解所寫的規則，所以不能肯定地說「這是對的」或「這是錯誤的」。然而，我會指出（只是爲了防止它*是無意的），就像你編寫代碼一樣，如果'a [i] == 0'爲'true'，你現在就增加'i'兩次。 – Monkeygrinder

是的，我想去除if（a [i] == 0）i ++;所有在一起，但我認爲它可能在那裏，以避免一個額外的循環，因爲它沒有做任何事情，但一旦它不損害代碼增加。 – TheBakker

另一個值得注意的事情是，如果i + 1 = n，'a [i + 1]'會拋出異常。 – Monkeygrinder

如果您曾經遇到過一個[i]！= 0（因此它是1）的情況，您將完成迭代，但是您不會向變量i添加內容。

所以如：

Take 1 step i => 1 
Land on 0, ok i => 2 
Land on 1, print yes or no, i=> 2 
Land on the same 1, print ... , i => 2

爲此而（我< n）爲不斷成立的情況下。

來源

2016-05-31 21:53:54 MrKickkiller

正如其他有說，你永遠不會增加i一次a[i] == 1。它會坐在那裏旋轉在相同的位置（值爲i）。

但是，您的算法是有缺陷的。考慮這種情況：

8 3 
0 1 0 0 1 0 1 1 
↑     start position 
     ↑   forward 3 (couldn't forward 1 or backward 1) 
    ↑    backward 1 (couldn't forward 1 or 3) 
      ↑  forward 3 (couldn't backward 1 and already been to forward 1) 
       ↑ forward 3 (couldn't forward 1 or backward 1) WIN !!!

您不檢查所有3個選項（向後1，向前1，向前X）。

你也不檢查你是否已經在某個地方。不檢查你是否在某處，你的代碼可能結束循環：前進1，後退1，前進1，後退1，前進1，後退1，前進1，後退1等等......

現在考慮這個：

16 5 
0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 1 
↑         start position 
      ↑       forward 5 
        ↑    forward 5 
        ↑     backward 1 DEAD END !!! (or loop if not checking "been there") 
↑         backtrack to here 
    ↑         forward 1 
    ↑        forward 1 
       ↑      forward 5 
         ↑   forward 5 
            ↑ forward 5 WIN !!!

正如你所看到的，你可能需要回溯到找到正確的路徑。無論您首先嚐試的3個選項（後向1，前向1，前向X）中的哪一個都是如此。

這樣的回溯邏輯通常使用遞歸方法實現，但也可以通過手動維護堆棧來完成。

最後，當你完成搜索，也就是說，如果你到了年底，打印YES和停止搜索，你應該只打印YES或NO，或者如果你已經嘗試了所有組合沒有得到到最後，打印NO。

來源

2016-05-31 22:29:05 Andreas

使用陣列解決Java任務

回答

相關問題