시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
일부 과정에 전제 조건이있는 n 개의 과정 (0부터 n-1까지)에 참석해야합니다. 예를 들어, 쌍 [2, 1]은 코스 2를 수강했음을 나타냅니다. 코스 1을 수강 했어야합니다. 총 코스 수를 나타내는 정수 n과 전제 조건이있는 코스 목록이 주어집니다. n 개의 과정을 모두 완료 할 수있는 순서를 반환해야합니다. 가능한 대답이 없으면 빈을 반환하십시오. 정렬. 여러 답변이있는 경우 원하는 답변을 반환합니다.
차례
예
입력 : 4
[[1,0], [2,0], [3,1], [3,2]]
출력 : [0, 1, 2, 3,]
입력 : 2
[[1, 0]]
출력 : [0,]
폭 우선 검색 사용
코스 일정 II 알고리즘 – LeetCode
- 코스 수를 나타내는 정수 n과 코스 및 필수 구성 요소를 저장하기위한 2D 배열 코스를 초기화합니다.
- 코스 배열이 null이면 빈 배열을 인쇄합니다.
- 전제 조건이 필요한 과정을 저장하기 위해 크기 n의 배열 pCounter를 만듭니다.
- 0에서 n-1로 이동하고 pCounter [course [i] [0]]를 증가시킵니다.
- 벡터 만들기 변발 모든 필수 구성 요소를 저장합니다.
- 0에서 n-1로 이동하고 현재 인덱스에 대한 pCounter의 값이 0인지 확인하고 현재 인덱스를 큐에 추가합니다.
- 크기 n의 배열 결과를 초기화합니다.
- 큐가 비어 있지 않은 동안 큐의 마지막 요소를 제거하고 결과 배열과 정수 c에 저장합니다.
- 내부 루프를 만들고 코스 배열의 [] [1] 값이 c 감소 pCounter [course [i] [0]]와 같은지 확인합니다.
- pCounter [course [i] [0]]이 0인지 확인합니다. queue에 course [i] [0]을 추가합니다.
- 결과 배열을 인쇄합니다.
실시
코스 일정 II를위한 C ++ 프로그램 – LeetCode
#include <bits/stdc++.h>
using namespace std;
int len = 4;
void findOrder(int n, int course[4][2]){
if(course == NULL){
cout<<"empty array";
}
int pCounter[n];
for(int i=0; i<len; i++){
pCounter[course[i][0]]++;
}
vector<int> queue;
for(int i=0; i<n; i++){
if(pCounter[i]==0){
queue.push_back(i);
}
}
int numNoPre = queue.size();
int result[n];
int j=0;
while(queue.size()!=0){
int c = 0;
if(!queue.empty()){
c = queue.back();
queue.pop_back();
}
result[j++]=c;
for(int i=0; i<len; i++){
if(course[i][1]==c){
pCounter[course[i][0]]--;
if(pCounter[course[i][0]]==0){
queue.push_back(course[i][0]);
numNoPre++;
}
}
}
}
cout<<"[";
for(int i=0; i<n; i++){
cout<<result[i]<<",";
}
cout<<"]";
}
int main(){
int n = 4;
int course[4][2] = {{1,0}, {2,0}, {3,1}, {3,2}};
findOrder(n, course);
return 0;
}
[0,2,1,3,]
코스 일정 II를위한 자바 프로그램 – LeetCode
import java.util.*;
class selection{
static int[] findOrder(int n, int[][] course) {
if(course == null){
throw new IllegalArgumentException("empty array");
}
int len = course.length;
if(len == 0){
int[] res = new int[n];
for(int m=0; m<n; m++){
res[m]=m;
}
return res;
}
int[] pCounter = new int[n];
for(int i=0; i<len; i++){
pCounter[course[i][0]]++;
}
LinkedList<Integer> queue = new LinkedList<Integer>();
for(int i=0; i<n; i++){
if(pCounter[i]==0){
queue.add(i);
}
}
int numNoPre = queue.size();
int[] result = new int[n];
int j=0;
while(!queue.isEmpty()){
int c = queue.remove();
result[j++]=c;
for(int i=0; i<len; i++){
if(course[i][1]==c){
pCounter[course[i][0]]--;
if(pCounter[course[i][0]]==0){
queue.add(course[i][0]);
numNoPre++;
}
}
}
}
if(numNoPre==n){
return result;
}
else{
return new int[0];
}
}
public static void main (String[] args) {
int n = 4;
int[][] course = {{1,0}, {2,0}, {3,1}, {3,2}};
int[] result = findOrder(n, course);
System.out.print("[");
for(int i=0; i<result.length; i++){
System.out.print(result[i]+",");
}
System.out.print("]");
}
}
[0,1,2,3,]
코스 일정 II에 대한 복잡성 분석 – LeetCode
시간 복잡성
O (Q * M) 여기서 Q는 벡터 또는 전제 조건을 포함하는 목록이고 M은 행 수, 즉 주어진 쌍의 수입니다.
공간 복잡성
O (M * N) 여기서 M은 행 수를 나타내고 N은 주어진 코스 배열의 열 수를 나타냅니다.
