시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
우리는 정렬 정렬되지 않은 정수의 가장 길고 증가하는 하위 시퀀스를 찾아야합니다.
- 하위 시퀀스는 연속적 일 필요는 없습니다.
- 하위 시퀀스가 증가합니다.
몇 가지 예를 통해 더 잘 이해합시다.
차례
예
입력
[9, 2, 5, 3, 7, 10, 8]
산출
4
설명
가장 오래 증가하는 하위 시퀀스는 [2,3,7,10]입니다.
접근법 1 : 브 루트 포스
이 접근 방식에는 가능한 모든 하위 집합을 조사하고 본질적으로 증가하는 가장 긴 하위 시퀀스를 찾는 것이 포함됩니다.
이제 배열에서 i 번째 정수를 방문 할 때마다 두 가지 경우가있을 수 있습니다.
- 하위 시퀀스에 포함될 수 있습니다. 즉 이전 요소보다 큽니다.
- 이전 요소보다 작고 하위 시퀀스에 포함될 수 없습니다.
그러나 특정 위치에 요소를 포함하든 없든 해당 지점까지 특정 길이의 증가하는 하위 시퀀스가 존재하고 해당 시점까지 발생한 최대 길이를 반환 할 수 있습니다. 코드 스 니펫 (Java 및 C ++에서)으로 더 잘 이해합시다.
가장 긴 하위 시퀀스 증가를위한 Java 프로그램
class Solution
{
public int helper(int[] nums,int prev,int cur)
{
if(cur==nums.length)
return 0;
int on_include=0;
//If the element at current index is greater than
//previous element we add to the length of subsequence
if(nums[cur]>prev)
on_include=helper(nums,nums[cur],cur+1)+1;
//Even if we are not there must be an increasing subsequence
int on_ignore=0;
on_ignore=helper(nums,prev,cur+1);
return(Math.max(on_include,on_ignore));
}
public int lengthOfLIS(int[] nums)
{
int max=helper(nums,Integer.MIN_VALUE,0);
return max;
}
}
가장 오래 증가하는 하위 시퀀스를위한 C ++ 프로그램
class Solution
{
public:
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
public:
int helper(vector<int> nums,int prev,int cur)
{
if(cur==nums.size())
return 0;
int on_include=0;
//If we are greater than previous length we add to the length of subsequence
if(nums[cur]>prev)
on_include=helper(nums,nums[cur],cur+1)+1;
//Even if we are not there must be an increasing subsequence
int on_ignore=0;
on_ignore=helper(nums,prev,cur+1);
return(max(on_include,on_ignore));
}
public:
int lengthOfLIS(vector<int>& nums)
{
int max=helper(nums,-1,0);
return max;
}
};
복잡성 분석
시간 복잡성
O (n ^ 2) 여기서 N은 배열의 크기입니다. 여기서 우리는 O (N * N) 시간 복잡성을 유발하는 두 개의 for 루프를 실행합니다.
공간 복잡성
O (1) 상수 공간 c0mplexity로 이끄는 몇 가지 변수를 사용하기 때문입니다.
접근법 2 : 동적 프로그래밍
[9, 2, 5, 3, 7, 10, 8, 7]에 대해 가장 오래 증가하는 하위 시퀀스를 찾아 보겠습니다.
- 정수 배열 크기의 배열을 만들어 보겠습니다.
- 각 요소는 하나 이상의 길이의 하위 시퀀스입니다. 즉, 숫자 자체가 XNUMX로 배열을 초기화합니다.
1 1 1 1 1 1 1 1 - i 번째 위치마다 앞의 j 번째 위치를 봅니다.
- 만약 a [j]
- i = 2의 경우 i = 0과 i = 1을 통해 동일하게 찾습니다. 작업 후 수정 된 배열을 살펴 보겠습니다.
1 1 최대 (j + 1, i) (2)
1 1 1 1 1 - 모든 비교 후 최종 배열은 다음과 같이 볼 수 있습니다.
1 1 2 2 3 4 4 3 - 모든 숫자의 최대 값을 구하면 최대 하위 시퀀스의 길이가 4 인 것을 알 수 있습니다. 코드로 이것을 더 잘 이해합시다.
가장 긴 하위 시퀀스 증가를위한 Java 프로그램
class Solution
{
public int lengthOfLIS(int[] nums)
{
int ans[]=new int[nums.length];
for(int i=0;i<ans.length;i++)
ans[i]=1;
for(int i=1;i<nums.length;i++)
{
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j])
{ans[i]=Math.max(ans[i],(ans[j]+1));}
}
}
int max=0;
for(int i=0;i<ans.length;i++)
{
max=Math.max(ans[i],max);
}
return max;
}
}
가장 오래 증가하는 하위 시퀀스를위한 C ++ 프로그램
class Solution
{
public:
int cmax(int a,int b)
{
if(a>b)
return a;
else
return b;
}
public:
int lengthOfLIS(vector<int>& nums)
{
int ans[nums.size()];
int i,j;
for(i=0;i<nums.size();i++)
ans[i]=1;
for(i=1;i<nums.size();i++)
{
for(j=0;j<i;j++)
{
if(nums[i]>nums[j])
{ans[i]=cmax(ans[i],(ans[j]+1));}
}
}
int max=0;
for(int i=0;i<nums.size();i++)
{
max=cmax(ans[i],max);
}
return max;
}
};
복잡성 분석
시간 복잡성
위 솔루션의 시간 복잡도는 O (n ^ 2)입니다.
공간 복잡성
O (n) 왜냐하면 각 인덱스 뒤에 답을 저장하기 위해 배열을 사용하기 때문입니다.
