《 프로그래머 면접 금 전 》 은 경로 검사 가 있다.

【 성명: 판권 소유, 전재 출처 표시, 상업 용도 로 사용 하지 마 십시오. 연락처:[email protected]] 제목 링크:http://www.nowcoder.com/practice/1b83885969f14329bf9222c1c54469a7?rp = 1 & ru = / ta / cracking - the - coding - interview & qru = / ta / cracking - the - coding - interview / question - ranking 제목 설명 은 방향 도 에 대해 하나의 알고리즘 을 실현 하여 두 점 사이 에 하나의 경로 가 존재 하 는 지 찾 아 보 세 요.그림 에 있 는 두 노드 의 포인터 Undirected Graph Node * a, Undirected Graph Node * b (데이터 형식 에 신경 쓰 지 마 십시오. 그림 은 방향 이 있 습 니 다) 를 지정 합 니 다. 두 점 사이 에 하나의 경로 (a 에서 b 또는 b 에서 a) 가 존재 하 는 지 여 부 를 나타 내 는 bool 을 되 돌려 주 십시오.사고의 간단 한 그림 의 옮 겨 다 니 는 문제 에 대해 이미 방문 한 결점 에 대해 우 리 는 표 시 를 해서 순환 을 방지 해 야 한다

/*
struct UndirectedGraphNode {
    int label;
    vector<struct UndirectedGraphNode *> neighbors;
    UndirectedGraphNode(int x) : label(x) {}
};*/

class Path
{
	public:
		bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b)
		{
			// write code here
			if(a==nullptr)
				return false;
			if(b==nullptr)
				return false;
			if(a == b)
				return true;
			return hasPath(a,b) || hasPath(b,a);
		}
		bool hasPath(UndirectedGraphNode *a,UndirectedGraphNode *b)
		{
			queue<UndirectedGraphNode*> Q;
			map<int,bool> vis;
			Q.push(a);
			vis[a->label] = true;
			while(!Q.empty())
			{
				UndirectedGraphNode *cur = Q.front();
				Q.pop();
				if(cur==b)
					return true;
				for(UndirectedGraphNode *node:cur->neighbors)
				{
					if(vis[node->label]==true)
						continue;
					vis[node->label] = true;
					if(node==b)
						return true;
					Q.push(node);
				}
			}
			return false;
		}
};

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

프로그래머 면접 금전 - 면접 문제 02.01 - 중복 노드 제거

프로그래머 면접 금전 - 면접 문제 02.01 - 중복 노드 제거 이 문 제 는 두 개의 지침 문제 로 지침 이 움 직 이지 않 고 이동 하려 면 노드 의 지침 을 제거 해 야 합 니 다. 두 가지 관건 이 있 습 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

《 프로그래머 면접 금 전 》 은 경로 검사 가 있다.

좋은 웹페이지 즐겨찾기