시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
N 번째 카탈로니아 수 문제에서 정수 n을 지정했습니다. 처음 n 개의 카탈루냐 숫자를 찾으십시오. 카탈루냐 숫자는 많은 계산 문제에서 볼 수있는 일련의 양의 정수입니다.
계산하는 데 사용됩니다.
- n 개의 키가있는 BST (이진 검색 트리).
- 특정 유형의 격자 경로.
- 순열
그리고 더 많은 그러한 문제. 카탈루냐 숫자의 재귀 공식은 –
C0 = 0 및 Cn + 1 = Σ Ci Cni n> = 0 및 n => i> = 0 인 경우.
카탈로니아 어 숫자 시리즈의 처음 몇 개의 숫자 – 각각 n = 1, 1, 2, 5, 14 …… 인 경우 0, 1, 2, 3, 4 ……
차례
예
입력 : n=2
출력 : 1 1
입력 : n=9
출력 : 1 1 2 5 14 42 132 429
N 번째 카탈 론 수에 대한 재귀 방법
암호알고리즘
- 초기화 a 변수 n.
- 기본 사례 – n이 1보다 작 으면 반환 1.
- 재귀 사례 – 1과 n (0 포함) 사이의 모든 i에 대해 모든 cat (i) x cat (ni-0)의 합계를 반환합니다.
시간 복잡성 : O (3n)
공간 복잡성 : O (1)
N 번째 카탈 론 번호 구현
C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
long int cat(int n){
// Base case
if(n<=1)
return 1;
// cat(n)= sum of cat(i)*cat(n-i-1)
long int r = 0;
for (int i=0; i<n; i++)
r += cat(i)*cat(n-i-1);
return r;
}
int main(){
int n=3;
for (int i=0; i<n; i++)
cout<<cat(i)<< " ";
return 0;
}
1 1 2
자바 프로그램
class Catalan{
int cat(int n) {
int r = 0;
// Base case
if(n<=1) {
return 1;
}
// cat(n)= sum of cat(i)*cat(n-i-1)
for(int i=0; i<n; i++) {
r+=cat(i)*cat(n-i-1);
}
return r;
}
public static void main(String[] args) {
Catalan c = new Catalan();
int n=3;
for (int i=0; i<n; i++) {
System.out.print(c.cat(i) + " ");
}
}
}
1 1 2
N 번째 카탈루냐 숫자에 대한 동적 프로그래밍 방법
암호알고리즘
- 카탈루냐 숫자를 저장하려면 변수 n과 배열 c를 초기화합니다.
- 의 처음 두 요소를 초기화합니다. 정렬 각각 1과 1로.
- 2부터 하나씩 n까지 모든 값을 탐색하고 배열 값을 c [j] * c [ij-1]의 합으로 업데이트합니다.
- c [n]을 반환합니다.
시간 복잡성 : 의 위에2)
공간 복잡성 : O(n)
N 번째 카탈 론 번호 구현
C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
long int cat(int n){
long int c[n+1];
// Initialisation of first two values
c[0]=1;
c[1]=1;
for(int i=2; i<=n; i++){
c[i] = 0;
for(int j=0; j<i; j++)
c[i] += c[j] * c[i-j-1];
}
// Return last number in array
return c[n];
}
int main(){
int n=3;
for(int i=0; i<n; i++)
cout << cat(i) << " ";
return 0;
}
1 1 2
자바 프로그램
class Catalan{
static int cat(int n){
int c[] = new int[n + 2];
// Initialisation of first two values
c[0]=1;
c[1]=1;
for(int i=2; i<=n; i++){
c[i] = 0;
for(int j=0; j<i; j++)
c[i] += c[j] * c[i-j-1];
}
// Return last number in array
return c[n];
}
public static void main(String[] args) {
int n=3;
for(int i=0; i<n; i++){
System.out.print(cat(i) + " ");
}
}
}
1 1 2
이항 계수 사용
여기서는 공식을 직접 사용하여 n 번째 카탈로니아 숫자를 찾습니다.
Cn = ( ( 2n! ) / ((n + 1)! n!))
시간 복잡성 : O (N)
공간 복잡성 : O (1)
N 번째 카탈로니아 숫자 구현
C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
long int biCoef(int n, int m){
long int r=1;
if(m>(n-m))
m=n-m;
for (int i=0; i<m; ++i){
r *= (n-i);
r /= (i+1);
}
return r;
}
long int cat(int n){
// Calculate value of 2nCn
long int c = biCoef(2*n, n);
// return 2nCn/(n+1)
return c/(n+1);
}
int main(){
int n=3;
for (int i=0; i<n; i++)
cout << cat(i) << " ";
return 0;
}
1 1 2
자바 프로그램
class Catalan{
static long biCoef(int n, int m){
long r=1;
if(m>(n-m))
m=n-m;
for (int i=0; i<m; ++i){
r *= (n-i);
r /= (i+1);
}
return r;
}
static long cat(int n){
// Calculate value of 2nCn
long c = biCoef(2*n, n);
// return 2nCn/(n+1)
return c/(n+1);
}
public static void main(String[] args) {
int n=3;
for(int i=0; i<n; i++){
System.out.print(cat(i) + " ");
}
}
}
1 1 2
