Java编程题之——可以到达所有点的最少点数目（某扣）-一一网

【摘要】题目描述：给你一个有向无环图， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [fromi, toi] 表示一条从点 fromi 到点 toi 的有向边。找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。你可以以任意顺序返回这些节点编号。先说说心得：心态炸裂，想着用深搜解决，代码写出来后提…

题目描述：
给你一个有向无环图， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [fromi, toi] 表示一条从点 fromi 到点 toi 的有向边。
找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。
你可以以任意顺序返回这些节点编号。
在这里插入图片描述
先说说心得：心态炸裂，想着用深搜解决，代码写出来后提交结果是这样的：通过65/66，没错，最后一个用例超时了，直接给我上了100000条数据，我直接炸了，先上深搜的代码：

class Solution { public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) { List<Integer>list=new ArrayList<>(); HashMap<Integer,HashSet<Integer>>map=new HashMap<>(); for(List<Integer>x:edges){ int start=x.get(0); int end=x.get(1); if(!map.containsKey(start)){ map.put(start,new HashSet<>()); } map.get(start).add(end); } boolean[]flag=new boolean[n]; for(int x:map.keySet()){ if(!flag[x]){ list.add(x); flag[x]=true; dfs(flag,list,map.get(x),map); } } return list; } public void dfs(boolean[]flag,List<Integer>list,HashSet<Integer>set,HashMap<Integer,HashSet<Integer>>map){ if(set==null||set.isEmpty()){ return; } for(int x:set){ if(!flag[x]){ flag[x]=true; dfs(flag,list,map.get(x),map); }else{ list.remove(Integer.valueOf(x)); } } }
}

  
 
  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

在这里插入图片描述
于是，我不得不换个做法：
将起点用哈希表存起来，然后遍历对应起点的每一个子节点，只要这个点在哈希表中出现了，那么说明这个起点是在别的长的路径中包含着，所以直接从哈希表中移除，最终哈希表中剩下的就是最终结果。

class Solution { public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) { HashSet<Integer>set=new HashSet<>(); List<Integer>list=new ArrayList<>(); for(int i=0;i<edges.size();++i){ int x=edges.get(i).get(0); int y=edges.get(i).get(1); set.add(x); list.add(y); } for(int x:list){ if(set.contains(x)){ set.remove(x); } } return new ArrayList<>(set); }
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18