找到一个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维数组

回答

相关问题