ArrayList Recursion bheaviour

Question

我正在做一个问题，打印从(0,0(到(row-1，cols-1(的唯一路径。。但是很难理解arraylist的bheaviour。请解释一下这个bheavior和正确的方法。

static void distnctpaths(int maze[][], int i, int j, int r, int c, ArrayList < Integer > path) {
if (i == r && j == c) {
path.add(maze[i][j]);
System.out.println(path);
return;
}
if (i == r + 1 || j == c + 1)
return;
path.add(maze[i][j]);
distnctpaths(maze, i, j + 1, r, c, path);
distnctpaths(maze, i + 1, j, r, c, path);

}
public static void main(String[] args) {
int maze[][] = {
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 },
};
ArrayList < Integer > path = new ArrayList < > ();
distnctpaths(maze, 0, 0, 2, 2, path);
}

错误输出

[1, 2, 3, 6, 9]
[1, 2, 3, 6, 9, 5, 6, 9]
[1, 2, 3, 6, 9, 5, 6, 9, 8, 9]
[1, 2, 3, 6, 9, 5, 6, 9, 8, 9, 4, 5, 6, 9]
[1, 2, 3, 6, 9, 5, 6, 9, 8, 9, 4, 5, 6, 9, 8, 9]
[1, 2, 3, 6, 9, 5, 6, 9, 8, 9, 4, 5, 6, 9, 8, 9, 7, 8, 9]

正确输出(供参考(

[1, 2, 3, 6, 9]
[1, 2, 5, 6, 9]
[1, 2, 5, 8, 9]
[1, 4, 5, 6, 9]
[1, 4, 5, 8, 9]
[1, 4, 7, 8, 9]

Answer 1

您的代码包含一个简单的逻辑错误。当你在路径中添加一个位置时，你不会在完成后将其删除。

---

代码

public static void distinctPaths(int[][] maze, int i, int j, int r , int c, ArrayList<Integer> path)
{
if(i == r && j == c)
{
path.add(maze[i][j]);
System.out.println(path);
path.remove(path.size()-1);
return ;
}
if (i == r+1 || j == c+1) return;
path.add(maze[i][j]);
distinctPaths(maze,i,j+1, r, c, path);
distinctPaths(maze, i+1, j, r,c,path);
path.remove(path.size()-1);
}

---

改进

在上文中，存在额外的path.add(index)和path.remove(index)。这是相同的代码，经过一点修改，使其更加简洁，并消除了语句的重复。

public static void distinctPaths(int[][] maze, int i, int j, int r , int c, ArrayList<Integer> path)
{
if (i == r+1 && j == c) System.out.println(path);
if (i == r+1 || j == c+1) return;
path.add(maze[i][j]);
distinctPaths(maze,i,j+1, r, c, path);
distinctPaths(maze, i+1, j, r,c,path);
path.remove(path.size()-1);
}

它产生相同的输出，但更短更好。

---

输出

[1, 2, 3, 6, 9]
[1, 2, 5, 6, 9]
[1, 2, 5, 8, 9]
[1, 4, 5, 6, 9]
[1, 4, 5, 8, 9]
[1, 4, 7, 8, 9]

---

这将解决您的问题我没有提供任何试运行来显示path.remove(index)的意义。您可以自己运行调试器来执行此操作。如果你仍然面临任何问题，请发表评论。我会编辑我的答案来帮助你。