Java ArrayLIst 添加对象出现的问题

最近在做Leetcode797的时候遇到了一个问题。

这道很简单,dfs跑到终点时将所有可能的道路temp(List)加入ArrayList 中,但是运行时发现ArrayList中所有的元素都变为空list了,原因是ArrayList在add的时候直接将对象的引用加入到了ArrayList中,引用指向的对象发生了改变导致ArrayList也发生了改变,解决方案是每次加入一个新建的List对象,这样即使temp发生了改变也没有关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序) 
//
// graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j]存在一条有向边)。
//
//
//
// 示例 1:
//
//
//
//
//输入:graph = [[1,2],[3],[3],[]]
//输出:[[0,1,3],[0,2,3]]
//解释:有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
//
//
// 示例 2:
//
//
//
//
//输入:graph = [[4,3,1],[3,2,4],[3],[4],[]]
//输出:[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
//
//
//
//
// 提示:
//
//
// n == graph.length
// 2 <= n <= 15
// 0 <= graph[i][j] < n
// graph[i][j] != i(即不存在自环)
// graph[i] 中的所有元素 互不相同
// 保证输入为 有向无环图(DAG)
//
//
//
// Related Topics 深度优先搜索 广度优先搜索 图 回溯 👍 249 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java:所有可能的路径
class P797AllPathsFromSourceToTarget{
public static void main(String[] args) {
Solution solution = new P797AllPathsFromSourceToTarget().new Solution();
// TO TEST
int [][] graph={{4,3,1},{3,2,4},{3},{4},{}};
System.out.println(solution.allPathsSourceTarget(graph));
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
List<List<Integer>> ans=new ArrayList<List<Integer>>();
List<Integer> temp= new ArrayList<Integer>();
int n;
boolean used[]=new boolean[16];
public void dfs(int x,List<Integer> temp,int [][] graph){
if(x==n-1){
ans.add(new ArrayList<>(temp));
return;
}
for(int i:graph[x]){
if(!used[i]){
temp.add(i);
used[i]=true;
dfs(i,temp,graph);
used[i]=false;
temp.remove(temp.size()-1);
}
}
}
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
n= graph.length;
used[0]=true;
temp.add(0);
dfs(0,temp,graph);
return ans;
}
}
//leetcode submit region end(Prohibit modification and deletion)

}

Author

Pemp

Posted on

2022-02-23

Updated on

2022-03-10

Licensed under

Comments