시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
반복 문자가 없는 가장 긴 부분 문자열 LeetCode 솔루션 – 주어진 현, 우리는 문자를 반복하지 않고 가장 긴 부분 문자열의 길이를 찾아야합니다.
몇 가지 예를 살펴 보겠습니다.
차례
예
pwwkew
3
설명 : 대답은 길이가 3 인“wke”입니다.
aav
2
설명 : 대답은 길이가 2 인“av”입니다.
접근 방식 -1 반복되는 문자가없는 가장 긴 부분 문자열
브 루트 포스
중복 문자에 대해 모든 하위 문자열이 하나인지 확인
- 시간 복잡성
- 형성 될 문자열 수 = n * (n + 1) / 2
- 각 문자열을 확인하는 데 걸리는 시간 = O (n)
- 따라서 시간 복잡도 = O (n ^ 3)
- 공간 복잡성
- 고유성 확인을위한 발생 문자 저장 = n
- 따라서 공간 복잡성 = O (n)
접근 방식 -2 반복되는 문자가없는 가장 긴 부분 문자열
슬라이딩 윈도우
이제 우리는 최대 길이 부분 문자열 + 반복되는 문자가 없습니다.
- 격언하자
- 음 길이는 최대 0으로 초기화됩니다.
- 우리는 i 에 j-1 이미 확인되었습니다
- j 번째 캐릭터를 만날 때마다
- s [j]가 반복되지 않는 경우
- 하위 문자열에 추가 할 수 있습니다.
- 하위 문자열의 길이를 늘릴 수 있습니다.
- j는 증가 할 수 있습니다.
- s [j]를 HashSet에 기록 / 추가 할 수 있습니다.
- s [j]가 반복되면
- 우리는 문자를 제거합니다
- 출발점, 즉 내가 변해야 해
- 하위 문자열이 반복되지 않을 때까지이 작업을 수행합니다.
- s [j]가 반복되지 않는 경우
반복 문자가 없는 가장 긴 부분 문자열을 위한 Java 프로그램 LeetCode 솔루션
import java.util.*;
class Solution
{
public int lengthOfLongestSubstring(String s)
{
int max=0;
HashSet<Character>hash=new HashSet<Character>();
int i=0;
int j=0;
while(i<s.length() && j<s.length())
{
if(hash.contains(s.charAt(j)))
{
hash.remove(s.charAt(i));
i=i+1;
}
else
{
hash.add(s.charAt(j));
j=j+1;
max=Math.max(j-i,max);
}
}
return max;
}
}
class Main{
public static void main(String[] args){
int answer = (new Solution()).lengthOfLongestSubstring("pwwkew");
System.out.print(answer);
}
}
pwwkew
3
C ++ 프로그램
class Solution
{
public:
int maxs(int a,int b)
{
if(a>b)
return a;
else
return b;
}
public:
int lengthOfLongestSubstring(string s)
{
int max=0;
set<char>hash;
int i=0;
int j=0;
while(i<s.length() && j<s.length())
{
if(hash.count(s[j]))
{
hash.erase(s[i]);
i=i+1;
}
else
{
hash.insert(s[j]);
j=j+1;
max=maxs(j-i,max);
}
}
return max;
}
};
pwwkew
3
복잡성 분석
시간 복잡성: 의 위에)
공간 복잡성: O (k) 여기서 k는 슬라이딩 윈도우의 크기입니다.
접근 방식 -3 반복되는 문자가없는 가장 긴 부분 문자열
최적화 된 슬라이딩 윈도우
위의 접근 방식에서는 반복되는 문자를 만날 때까지 계속 문자를 제거하고 문자열의 시작을 변경합니다.
해시 맵을 사용하여 repeating_character의 마지막 발생을 유지할 수 있으며 i (하위 문자열의 시작)를 해당 지점으로 이동하여 O (1) 연산을 수행 할 수 있습니다.
자바 프로그램
import java.util.*;
class Solution
{
public int lengthOfLongestSubstring(String s)
{
int max=0;
HashMap<Character,Integer>hash=new HashMap<Character,Integer>();
int i=0;
int j=0;
while(j<s.length())
{
if(hash.containsKey(s.charAt(j)))
{
i=Math.max(hash.get(s.charAt(j)),i);
}
hash.put(s.charAt(j),j+1);
max=Math.max(j-i+1,max);
j=j+1;
}
return max;
}
}
class Main{
public static void main(String[] args){
int answer = (new Solution()).lengthOfLongestSubstring("abcdefg");
System.out.print(answer);
}
}
abcdefg
7
C ++ 프로그램
class Solution
{
public:
int maxs(int a,int b)
{
if(a>b)
return a;
else
return b;
}
public:
int lengthOfLongestSubstring(string s)
{
int max=0;
map<char,int>hash;
int i=0;
int j=0;
while(j<s.length())
{
if(hash.count(s[j]))
{
i=maxs(hash[s[j]],i);
}
hash[s[j]]=j+1;
max=maxs(j-i+1,max);
j=j+1;
}
return max;
}
};
aabbccddee
2
복잡성 분석
시간 복잡도 : O (n)
공간 복잡도 : O (k) 여기서 k는 슬라이딩 윈도우의 크기입니다.
