시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
또한 반복 문자가 없는 가장 긴 부분 문자열 LeetCode 솔루션 – 주어진 문자열 s를 나타냅니다. 우리는 찾을 필요가 가장 긴 부분 문자열 반복되는 문자 없이.
예:
Input: s = "abcabcbb"
Output: 3
설명 :
- 반복되는 문자가 없는 가장 긴 부분 문자열의 길이는 3입니다.
- 문자열은 "abc"입니다.
Input: s = "bbbbb"
Output: 1
설명 :
- 모든 문자가 동일하므로 문자가 반복되지 않는 가장 긴 부분 문자열의 길이는 1입니다.
접근
아이디어 :
- 이 문제를 해결하기 위한 주요 아이디어는 해시 맵.
- 또한 무차별 대입 접근 방식을 사용하여 모든 하위 문자열을 고려하고 하위 문자열에 고유한 모든 문자가 포함되어 있는지 확인할 수 있습니다. 무차별 대입 접근 방식은 어레이의 최대 크기가 5 * 10^4이기 때문에 시간 제한 초과 판정을 제공합니다.
- 문자열의 문자를 다음과 같이 저장하는 해시맵을 유지하십시오. 키와 그 위치 가치로 유지하고 두 포인터 최대 하위 문자열을 정의합니다.
- 오른쪽 포인터를 이동하여 문자열을 스캔하고 해시맵을 업데이트합니다.
- 문자가 이미 해시맵에 있는 경우 왼쪽 포인터를 마지막으로 찾은 동일한 문자의 오른쪽으로 이동합니다. 두 포인터는 앞으로만 이동할 수 있습니다.
- 마지막으로 모든 문자가 다른 가장 긴 부분 문자열의 길이를 갖게 됩니다.
암호
반복 문자가 없는 가장 긴 부분 문자열 C++ 솔루션:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> occ(260,-2);
int n = s.length(),ans = 0,j = 0;
for(int i=0;i<n;i++){
if(occ[s[i]]==-2){
ans = max(ans,i-j+1);
}
else{
while(j<=occ[s[i]]){
occ[s[j++]] = -2;
}
}
occ[s[i]] = i;
}
return ans;
}
};
반복 문자가 없는 가장 긴 부분 문자열 Java 솔루션:
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max=0;
for (int i=0, j=0; i<s.length(); ++i){
if (map.containsKey(s.charAt(i))){
j = Math.max(j,map.get(s.charAt(i))+1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-j+1);
}
return max;
}
}
복잡성 분석:
시간 복잡성
위 코드의 시간 복잡성은 의 위에) 문자의 발생을 추적하기에 충분한 크기의 벡터를 사용하거나 일정한 시간에 삽입 및 삭제를 허용하는 우수한 해시 함수(여기서 N = 입력 문자열의 크기)를 사용하는 경우.
공간 복잡성
위 코드의 공간 복잡성은 다음과 같습니다. O (M) 여기서 M = 해시맵의 크기입니다. 해시맵은 문자 항목을 저장합니다. 솔루션의 공간 복잡도는 전적으로 해시맵에 따라 다릅니다. 해시맵의 크기가 더 크면 공간 복잡도가 더 커질 것입니다.
