找到一個2維數組

我一直在這個問題上一段時間，無法拿出解決方案的最長遞增序列;我希望你能幫上忙..

我試圖找到最長的增加序列的數字。例如，如果我有以下4X4陣列：

[![enter image description here][1]][1] 

    int [] nums = { 
     {97 , 47 , 56 , 36}, 
     {35 , 57 , 41 , 13}, 
     {89 , 36 , 98 , 75}, 
     {25 , 45 , 26 , 17} 
    };

預期的結果：返回8和LIS 17，26，36，41，47，56，57，97 我沒有答案到了它，我試圖達到它。

17 (3,3) 
26 (3,2) 
36 (2,1) 
41 (1,2) 
47 (0,1) 
56 (0,2) 
57 (1,1) 
97 (0,0)

我希望我的例子是很清楚..

這是我的代碼;當我試圖找到最長的增長路徑時，它不會向後對角地進行。任何人都可以幫助我嗎？

public class Solution2 { 
    static int[] dx = { 1, -1, 0, 0 }; 
    static int[] dy = { 0, 0, 1, -1 }; 
    public static int longestIncreasingPath(int[][] matrix) { 
     if (matrix.length == 0) 
      return 0; 
     int m = matrix.length, n = matrix[0].length; 
     int[][] dis = new int[m][n]; 
     int ans = 0; 
     for (int i = 0; i < m; i++) { 
      for (int j = 0; j < n; j++) { 
       ans = Math.max(ans, dfs(i, j, m, n, matrix, dis)); 
      } 
     } 
     return ans; 
    } 

    static int dfs(int x, int y, int m, int n, int[][] matrix, int[][] dis) { 
     if (dis[x][y] != 0) 
      return dis[x][y]; 

     for (int i = 0; i < 4; i++) { 
      int nx = x + dx[i]; 
      int ny = y + dy[i]; 
      if (nx >= 0 && ny >= 0 && nx < m && ny < n && matrix[nx][ny] > matrix[x][y]) { 
       dis[x][y] = Math.max(dis[x][y], dfs(nx, ny, m, n, matrix, dis)); 
      } 
     } 
     return ++dis[x][y]; 
    } 

    public static void main(String[] args) { 
     int arr[][] = { 
      { 97, 47, 56, 36 }, 
      { 35, 57, 41, 13 }, 
      { 89, 36, 98, 75 }, 
      { 25, 45, 26, 17 } 
     }; 
     System.out.println(longestIncreasingPath(arr)); 
    } 
}

來源

2017-10-14 Al-otaibi Ayman

我不明白你正在嘗試做的。您列出了不在您提供的數組中的最長序列;我甚至沒有看到你的答案和你的數據之間的關係。這個最長的序列從哪裏來？ –

你的例子不清楚它將如何返回8？ – Lokesh

17-> 26-> 36-> 41-> 47-> 56-> 57-> 97 它從陣列的右下方往上走。我在示例中添加了座標。 –

據我所知，您嘗試執行深度優先搜索以查找遞增順序的最長路徑。如果是這樣，首先最好是將您訪問的號碼以某種方式標記出來。一個便利的解決方案是array。只要數字被標記，您就可以用它來檢查特定數字是否已經按遞增順序計數。這是對你的一點提示。

如果您仍然對深度優先搜索感到困惑，我建議您閱讀Depth-First Search Wikipedia page以更好地理解算法的全部內容。

HTH，葉夫根尼·

來源

2017-10-14 04:40:34

我只是增加了整個問題...我希望它比我所解釋的更清楚 –

DFS是一個很好的起點。閱讀**拓撲排序**（或只搜索「DAG最長路徑」）。 –

是的，這是一個具有挑戰性的問題，我無法解決它。我想我會忽略這個問題... –

我認爲我們正在尋找一個嚴格遞增序列（這是不是從原來的問題描述清楚）。然後可以通過動態編程方法來解決此問題：

1）按照降序排序單元格的值。

2）以遞減的順序分配的最長路徑的開始在此小區中的長度：

2a）中如果不能達到任何先前訪問的小區的分配1

2b）中另有指定1個+最大（可到達前一個單元格）

完成後，總體最大值是最長路徑的長度。路徑本身也可以通過在步驟2b）中記住最大單元格來找到。

在這個例子中這給：

          0,3 2,1 
cell 98 97 89 75 57 56 47 45 41 36 36 35 26 25 17 13 
length 1 1 1 2 2 3 4 2 5 6 6 7 7 7 8 7

來源

2017-10-14 05:11:37 Henry

由於順序約束增加，並將DFS /拓撲排序以獲得拓撲順序的方式，使它成爲一個將成爲DAG的圖，速度更快，它是'O（| V | + | E |）'這是線性時間（我想，但我就像睡着了，所以誰知道）。 –

@GergelyKőrössy這是事實，它會更快，但我認爲編程更復雜。 – Henry

多樣性是編程中最酷的事情。（另外我想DFS是因爲老師暗示使用可用於DFS的堆棧。） –

找到一個2維數組

回答

相關問題