当前位置:网站首页>Li Kou interview question 04.01 Path between nodes
Li Kou interview question 04.01 Path between nodes
2022-07-07 07:55:00 【Yangshiwei....】
subject :
analysis :
This can be done in the form of establishing adjacency tables , Use one hashmap Store which nodes each node can point to , And then start Put in queue , Find out the correspondence key The node that can be reached and has not been visited in the value , Put it in the queue and set the value of the corresponding Boolean array to true, If the queue is empty, there is no path .
Code :
class Solution {
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
boolean[] b=new boolean[n];
HashMap<Integer,List<Integer>> hhash=new HashMap<Integer,List<Integer>>();
Queue<Integer> q=new LinkedList();
for(int i=0;i<graph.length;i++){
if(!hhash.containsKey(graph[i][0])){
hhash.put(graph[i][0],new ArrayList());
}
List list=hhash.get(graph[i][0]);
list.add(graph[i][1]);
}
q.offer(start);
b[start]=true;
while(!q.isEmpty()){
int s=q.poll();
if(!hhash.containsKey(s)){
continue;
}else{
List list=hhash.get(s);
for(int j=0;j<list.size();j++){
int i=(int)list.get(j);
if(!b[i]){
if(i==target){
return true;
}else{
b[i]=true;
q.offer(i);
}
}
}
}
}
return false;
}
}
边栏推荐
猜你喜欢
探索Cassandra的去中心化分布式架构
[guess-ctf2019] fake compressed packets
通信设备商,到底有哪些岗位?
2022 welder (elementary) judgment questions and online simulation examination
QT learning 28 toolbar in the main window
[UTCTF2020]file header
A bit of knowledge - about Apple Certified MFI
【webrtc】m98 screen和window采集
buuctf misc USB
LeetCode 90:子集 II
随机推荐
图解GPT3的工作原理
【p2p】本地抓包
自定义类加载器加载网络Class
知识点滴 - 关于苹果认证MFI
pytest+allure+jenkins环境--填坑完毕
Tianqing sends instructions to bypass the secondary verification
Open source ecosystem | create a vibrant open source community and jointly build a new open source ecosystem!
Button wizard script learning - about tmall grabbing red envelopes
2022 simulated examination question bank and online simulated examination of tea master (primary) examination questions
【webrtc】m98 screen和window采集
The configuration that needs to be modified when switching between high and low versions of MySQL 5-8 (take aicode as an example here)
2022年全国最新消防设施操作员(初级消防设施操作员)模拟题及答案
[performance pressure test] how to do a good job of performance pressure test?
leanote私有云笔记搭建
C语言航班订票系统
PHP exports millions of data
Weibo publishing cases
Qt学习27 应用程序中的主窗口
Solution: could not find kf5 (missing: coreaddons dbusaddons doctools xmlgui)
Qt学习28 主窗口中的工具栏