leetcode 1042 인접 하지 않 은 꽃 염색 문제
7534 단어 알고리즘
paths [i] = [x, y] 는 화원 x 에서 화원 y 까지 의 양 방향 경 로 를 묘사 했다.
또 정원 에 들 어가 거나 떠 날 수 있 는 3 가지 이상 의 경로 가 없다.
당신 은 모든 화원 에 꽃 을 선택 하여 경 로 를 통 해 연 결 된 모든 화원 의 꽃의 종 류 를 서로 다 르 게 해 야 합 니 다.
선택 한 방안 을 배열 형식 으로 되 돌려 주 는 것 이 답 입 니 다. 그 중에서 answer [i] 는 제 (i + 1) 정원 에서 재배 한 꽃의 종류 입 니 다.꽃의 종 류 는 1, 2, 3, 4 로 표시 한다.답 이 있 을 것 을 보증 하 다.
예시 1:
입력: N = 3, paths = [1, 2], [2, 3], [3, 1] 출력: [1, 2, 3]
예시 2:
입력: N = 4, paths = [1, 2], [3, 4] 출력: [1, 2, 1, 2]
예시 3:
입력: N = 4, paths = [1, 2], [2, 3], [3, 4], [4, 1], [1, 3], [2, 4] 출력: [1, 2, 3, 4]
class Solution {
public:
vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
vector<int> G[N];
for (int i=0; i<paths.size(); i++){//
G[paths[i][0]-1].push_back(paths[i][1]-1);
G[paths[i][1]-1].push_back(paths[i][0]-1);
}
vector<int> answer(N,0);//
for(int i=0; i<N; i++){
set<int> color{1,2,3,4};
for (int j=0; j<G[i].size(); j++){
color.erase(answer[G[i][j]]);//
}
answer[i]=*(color.begin());//
}
return answer;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.