코스 일정 II – LeetCode

난이도 중급
알고리즘 폭 우선 검색 코딩 깊이 우선 검색 Graph 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 토폴로지 정렬조회수 79

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

일부 과정에 전제 조건이있는 n 개의 과정 (0부터 n-1까지)에 참석해야합니다. 예를 들어, 쌍 [2, 1]은 코스 2를 수강했음을 나타냅니다. 코스 1을 수강 했어야합니다. 총 코스 수를 나타내는 정수 n과 전제 조건이있는 코스 목록이 주어집니다. n 개의 과정을 모두 완료 할 수있는 순서를 반환해야합니다. 가능한 대답이 없으면 빈을 반환하십시오. 정렬. 여러 답변이있는 경우 원하는 답변을 반환합니다.

코스 일정 II-LeetCode

입력 :  4

[[1,0], [2,0], [3,1], [3,2]]

출력 : [0, 1, 2, 3,]

입력 : 2

[[1, 0]]

출력 : [0,]

폭 우선 검색 사용

코스 일정 II 알고리즘 – LeetCode

  1. 코스 수를 나타내는 정수 n과 코스 및 필수 구성 요소를 저장하기위한 2D 배열 코스를 초기화합니다.
  2. 코스 배열이 null이면 빈 배열을 인쇄합니다.
  3. 전제 조건이 필요한 과정을 저장하기 위해 크기 n의 배열 pCounter를 만듭니다.
  4. 0에서 n-1로 이동하고 pCounter [course [i] [0]]를 증가시킵니다.
  5. 벡터 만들기 변발 모든 필수 구성 요소를 저장합니다.
  6. 0에서 n-1로 이동하고 현재 인덱스에 대한 pCounter의 값이 0인지 확인하고 현재 인덱스를 큐에 추가합니다.
  7. 크기 n의 배열 결과를 초기화합니다.
  8. 큐가 비어 있지 않은 동안 큐의 마지막 요소를 제거하고 결과 배열과 정수 c에 저장합니다.
  9. 내부 루프를 만들고 코스 배열의 [] [1] 값이 c 감소 pCounter [course [i] [0]]와 같은지 확인합니다.
  10. pCounter [course [i] [0]]이 0인지 확인합니다. queue에 course [i] [0]을 추가합니다.
  11. 결과 배열을 인쇄합니다.

실시

코스 일정 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은 주어진 코스 배열의 열 수를 나타냅니다.

참조

균열 시스템 설계 인터뷰
Translate »