[leetcode] 교 체 된 최 장 중복 문자 (슬라이딩 창)
메모: 문자열 길이 와 k 는 104 를 초과 하지 않 습 니 다.
예시 1:
입력: s = "ABAB", k = 2
출력: 4
해석: 두 개의 'A' 로 두 개의 'B' 로 바 꾸 고 반대로 도 마찬가지다.예시 2:
입력: s = "AABABBA", k = 1
출력: 4
해석: 중간 에 있 는 'A' 를 'B' 로 바 꾸 고 문자열 을 'AABBBBA' 로 바 꿉 니 다.하위 꼬치 'BBBB' 는 최 장 중복 자모 가 있 고 답 은 4 이다.
링크:https://leetcode-cn.com/problems/longest-repeating-character-replacement
사고 분석:
처음에 생각 했 던 동적 계획 은 생각 할 수록 이상 하 다 고 느 꼈 다.문 제 를 풀 어 보 니 미끄럼 창 이 었 습 니 다. * *미끄럼 창 은 구간 의 만족 조건 을 찾 는 것 입 니 다. * *만약 [l, r] 구간 의 수가 모두 조건 을 만족시킨다 면 r + + 구간 의 수가 조건 을 만족 시 키 지 못 할 때 까지.그 다음 에 l + + 구간 까지 조건 을 만족 시 킵 니 다.이렇게 r > = n 이 멈 출 때 까지 계속 앞으로 밀어 주세요.관건 은 구간 의 만족 조건 을 찾 는 것 이다.
이 문제 의 구간 만족 조건 은 기억 구간 에서 중복 자모 가 가장 많이 나타 나 는 횟수 는 maxcnt 이 며, r - l + 1 - maxcnt < = k 시 구간 만족 조건 이다.
왜 그 러 지?* * 구간 [l, r] 길이 에서 maxcnt 를 뺀 의 미 는 가장 많이 나타 난 문자 와 다른 개수, 즉 교체 해 야 할 문자 개수 이기 때 문 입 니 다. * *교체 할 문자 개수 < = k, 구간 만족 조건, r + +;그 > k, 구간 불만족 조건, l + +;
이렇게 하면 코드 를 쓰기 쉽다.해시 표 는 maxcnt 를 해결 한 후 미끄럼 창 에 따라 내 려 가면 됩 니 다.아래 코드:
class Solution {
public:
int characterReplacement(string s, int k) {
int l = 0, r = 0, n = s.length(), maxcnt = 0, ans = 0;
map<char,int> mp;
while(r < n)
{
mp[s[r]]++;
maxcnt = max(maxcnt,mp[s[r]]);
while(r-l+1 - maxcnt > k)
{
mp[s[l]]--;
l++;
}
ans = max(ans,r-l+1);
r++;
}
return ans;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
