알고리즘 기계 시험 시 뮬 레이 션 문제 part 1

- 1 함수 값 구하 기 제목 설명
정의 슈퍼 와 함수 F 는 다음 과 같 습 니 다: F (0, n) = n, 모든 정수 n. F (k, n) = F (k – 1, 1) + F (k – 1, 2) +... + F (k – 1, n), 모든 정수 k 와 n. 아래 Solution 류 에서 F (k, n) 를 계산 하 는 함수 (1 < = k, n < = 14) 를 실현 하 십시오. class Solution {public: int F (int k, int n) {};예 1: F (1, 3) = 6 예 2: F (2, 3) = 10 예 3: F (10, 10) = 167960 주의: Solution 류 의 코드 만 제출 하면 됩 니 다. 로 컬 에서 main 함수 테스트 프로그램 을 작성 할 수 있 지만 main 함수 의 코드 를 제출 할 필요 가 없습니다. 클래스 와 함수 의 이름 을 수정 하지 않도록 주의 하 십시오.

1 이 문 제 를 분석 하면 분 치 법 으로 풀 수 있 지만 대량의 중복 계산 이 시간 을 초과 할 수 있 음 을 고려 하여 동태 적 인 계획 을 사용 하 는 것 이 더욱 적합 하 다.

1 코드 분 치 법

class Solution {
public:
int F(int k,int n){
    int value=0;
    if(k==0)
        return n;
    else{
        for(int i=1;i<=n;i++)
            value+=F(k-1,i);
        return value;
    }
}
};  

동적 계획 법

class Solution {
public:
int F(int k,int n){
    vector<vector<int>> log(k+1,vector<int>(n+1));
    for(int i=1;i<=n;i++)
        log[0][i]=i;
    for(int i=1;i<=k;i++)
        for(int l=1;l<=n;l++){
            log[i][l]=0;
            for(int j=1;j<=l;j++)
                log[i][l]+=log[i-1][j];
        }
    return log[k][n];
}

};  

2 회의 배정 제목 설명

N 개 회 의 를 동시에 개최 해 야 한다. 회의 참가 인원 은 각각 A [0], A [1], A [N - 1] 이다. 현재 M 개 회의실, 회의실 수용 인원 은 각각 B [0], B [1], B [M - 1] 이다.M < = 100000, 각 회의의 참석 인원 과 각 회의실 의 수용 인원 은 모두 1 과 1000 사이 입 니 다. 아래 Solution 류 를 위해 상기 문 제 를 해결 하 는 함수 assign ConferenceRoom. 함수 매개 변수 A 와 B 의 의 미 는 위 와 같 습 니 다. 반환 값 은 최대 배정 가능 한 회의 수 입 니 다. class Solution {public: int assign ConferenceRoom (vector & A, vector & B) {};예 1: A = {2, 3}, B = {1, 2}, 답 은 1. 예 2: A = {3, 4, 5}, B = {10, 3, 2}, 답 은 2.

2 욕심 산법 을 분석 하 는 응용어 릴 때 부터 크게, 매번 딱 맞 는 것 을 고 를 수 있다.아니면 큰 것 부터 작은 것 까지.

2 코드 가 어 릴 때 부터 큰 방법

class Solution {
public:
int assignConferenceRoom(vector<int>& A, vector<int>& B) {
    int num=0,k=0,isend=0;
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    for(int i=0;i0;
        while(B[k]if(k>=B.size()){
isend=1;
break;
}
}
if(isend==0){
k++;
num++;
}
if(k>=B.size())
break;
}
return num;
}
};

큰 것 에서 작은 것 까지 의 방법: 두 배열 을 정렬 하고 최대 회의실 로 최대 수 요 를 만족 시 키 지 못 하면 다음 의 수 요 를 볼 수 있다.

class Solution {  
public:  
    int assignConferenceRoom(vector<int>& A, vector<int>& B) {  
        sort(A.begin(),A.end());  
        sort(B.begin(),B.end());  
        int a=A.size()-1;  
        int b=B.size()-1;  
        int count=0;  
        while(a>=0&&b>=0){  
            if(B[b]else{  
b--;  
a--;  
count++;  
}  
}  
return count;  
}  
};

3 등가 이 진 트 리 제목 설명

두 개의 이 진 트 리 는 구조 가 같 고 대응 하 는 노드 의 값 이 같 습 니 다. 우 리 는 이 두 개의 이 진 트 리 를 등가 라 고 부 릅 니 다. 예 를 들 어 아래 두 개의 이 진 트 리 는 등가 1 / \ / \ \ \ 2 3, 2 이하 두 개 도 등가 1 / \ / \ \ \ 2, 32 두 개의 이 진 트 리 p 와 q 를 제시 하여 등가 여 부 를 판단 합 니 다. p 와 q 의 결 점 수 는 100000 보다 많 지 않 습 니 다.각 노드 의 수 치 는 1 과 100000000 사이 입 니 다. 아래 Solution 류 를 위해 상기 문 제 를 해결 하 는 isEqual 함 수 를 실현 하 십시오. 함수 의 두 매개 변수 p 와 q 는 각각 두 개의 이 진 트 리 의 뿌리 노드 를 대표 합 니 다. p 와 q 를 뿌리 로 하 는 이 진 트 리 등 가 는 함수 가 true 로 돌아 갑 니 다. 그렇지 않 으 면 false 로 돌아 갑 니 다. / * Definition for a binary tree node. struct TreeNode.{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; */ class Solution { public: bool isEqual(TreeNode* p, TreeNode* q) { } }; 메모: Solution 류 의 코드 만 제출 하면 됩 니 다. 로 컬 에서 main 함수 테스트 프로그램 을 작성 할 수 있 지만 main 함수 의 코드 를 제출 할 필요 도 없고 TreeNode 의 정 의 를 제출 할 필요 도 없습니다. 클래스 와 함수 의 이름 을 수정 하지 않도록 주의 하 십시오.

3 분석 은 매우 전형 적 인 문제 이다. 선착순 으로 옮 겨 다 니 는 응용 이 라 고 할 수 있 고 DFS 의 응용 이 라 고 할 수 있 으 며 분 치 법의 응용 이 라 고 할 수 있다.

3 코드

class Solution {
public:
bool isEqual(TreeNode* p, TreeNode* q) {
        if(p==NULL &&q==NULL)
            return 1;
        else if(!p||!q)
            return 0;
        else{
            if(p->val==q->val)
                return isEqual(p->left,q->left)&& isEqual(p->right,q->right);
             else
                 return 0;
         }
}
};