C++LeetCode 구현(904.과일 바구니 에 담 기)

[Leet Code]904.프 루트 인 투 바스켓 과일 을 과일 바구니 에 담는다.
In a row of trees, the `i`-th tree produces fruit with type `tree[i]`.
You start at any tree of your choice, then repeatedly perform the following steps:

Add one piece of fruit from this tree to your baskets.  If you cannot, stop.

Move to the next tree to the right of the current tree.  If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.
You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.
What is the total amount of fruit you can collect with this procedure?
Example 1:
Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1]. Example 2:
Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2]. If we started at the first tree, we would only collect [0, 1]. 
Example 3:
Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2]. If we started at the first tree, we would only collect [1, 2]. 
Example 4:
Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5 
Explanation: We can collect [1,2,1,1,2]. If we started at the first tree or the eighth tree, we would only collect 4 fruits. 
Note:

1 <= tree.length <= 40000

0 <= tree[i] < tree.length

이 문 제 는 우리 에 게 한 줄 의 나 무 를 주 었 다 고 합 니 다.나무 마다 나 는 과일 종 류 는 tree[i]입 니 다.지금 은 두 가지 조작 이 있다 고 합 니 다.첫 번 째 는 현재 나무의 과일 을 과일 바구니 에 넣 고 넣 지 못 하면 멈 추 는 것 입 니 다.두 번 째 는 다음 나무 로 이동 하 는 것 이다.다음 나무 가 없 으 면 멈춘다.지금 우 리 는 두 개의 과일 바 구 니 를 가지 고 있 는데,임의의 나무의 위치 에서 시작 할 수 있 지만,반드시 순서대로 1 과 2 를 조작 해 야 한다.우리 에 게 최대 몇 개의 과일 을 수집 할 수 있 는 지 물 어 봐 야 한다.솔직히 이 문제 의 제목 묘사 가 분명 하지 않다.블 로 거들 은 여러 번 보고 나 서 야 뜻 을 알 게 되 었 다.게시판 에 도 구설 수 있 는 댓 글 이 많 았 다.그러나 실제로 이 문 제 는 본질 적 으로 임의의 위치 에서 시작 해서 최대 두 가지 과일 만 모 을 수 있다 면 과일 을 얼마나 모 을 수 있 는 지 물 어 보 는 것 이다.그러면 더 추출 하면 사실은 최대 두 개의 서로 다른 문자 가 있 는 가장 긴 문자열 의 길이 입 니 다.예전 의[Longest Substring with At Most Two Distinct Characters](http://www.cnblogs.com/grandyang/p/5185561.html)똑 같 아 요.배경 만 바 뀌 었 을 뿐 코드 는 기본적으로 직접 사용 할 수 있어 요.블 로 거들 은 이렇게 문 제 를 내 는 것 이 좀 좋 지 않 은 것 같 아 요.완전히 중복 되 었 다.이전 에 그 문제 의 네 가지 해법 은 여기 서 완전히 사용 할 수 있 습 니 다.첫 번 째 는 HashMap 을 사용 하여 모든 과일 이 나타 나 는 횟수 를 기록 합 니 다.HashMap 에서 매 핑 수량 이 두 개 를 초과 할 때 우 리 는 매 핑 을 삭제 해 야 합 니 다.방법 은 미끄럼 창의 왼쪽 경계 start 의 과일 매 핑 값 을 1 로 줄 이 는 것 입 니 다.이때 0 으로 줄 이면 이 매 핑 을 삭제 합 니 다.그렇지 않 으 면 왼쪽 경계 에서 오른쪽으로 한 명 이동 합 니 다.맵 수량 이 두 개 로 돌아 갈 때 현재 창의 크기 로 결과 res 를 업데이트 하면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, start = 0, n = tree.size();
        unordered_map<int, int> fruitCnt;
        for (int i = 0; i < n; ++i) {
            ++fruitCnt[tree[i]];
            while (fruitCnt.size() > 2) {
                if (--fruitCnt[tree[start]] == 0) {
                    fruitCnt.erase(tree[start]);
                }
                ++start;
            }
            res = max(res, i - start + 1);
        }
        return res;
    }
};

우 리 는 HashMap 으로 문자 가 나타 난 개 수 를 매 핑 하 는 것 을 제외 하고 모든 숫자의 최신 좌 표를 매 핑 할 수 있다.예 를 들 어 문제 중의 예[0,1,2,2]는 첫 번 째 0 을 만 나 좌 표를 매 핑 하고 0,1 을 만 나 좌 표를 매 핑 한다.2 를 만 났 을 때 좌 표를 매 핑 한다.2 를 만 날 때마다 우 리 는 현재 HashMap 의 매 핑 수 를 판단 한다.만약 에 2 보다 크 면...그러면 하나의 맵 을 삭제 해 야 합 니 다.우 리 는 start=0 시 부터 오른쪽으로 찾 아야 합 니 다.모든 문자 가 HashMap 에서 의 맵 값 이 현재 좌표 start 와 같 는 지 확인 해 야 합 니 다.예 를 들 어 0,HashMap 은 이때 맵 값 이 0 이 고 left 의 0 과 같 습 니 다.그러면 우 리 는 0 을 삭제 하고 start 는 1 을 증가 한 다음 에 결 과 를 업데이트 합 니 다.이 를 통 해 전체 배열 을 옮 겨 다 닐 때 까지 유추 합 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, start = 0, n = tree.size();
        unordered_map<int, int> fruitPos;
        for (int i = 0; i < n; ++i) {
            fruitPos[tree[i]] = i;
            while (fruitPos.size() > 2) {
                if (fruitPos[tree[start]] == start) {
                    fruitPos.erase(tree[start]);
                }
                ++start;
            }
            res = max(res, i - start + 1);
        }
        return res;
    }
};

나중에 인터넷 에서 해법 을 보 았 습 니 다.이런 해법 은 미끄럼 창 sliding window 를 유지 하 는 것 입 니 다.포인터 left 는 시작 위 치 를 가리 키 고 right 는 window 의 마지막 위 치 를 가리 키 며 left 의 다음 점프 위 치 를 찾 는 데 사 용 됩 니 다.생각 은 다음 과 같 습 니 다.

현재 문자 가 이전 문자 와 같 으 면 계속 순환 합 니 다.

다 르 면 현재 문자 와 right 가 가리 키 는 문자 가 같 는 지 확인 하 십시오.

만약 같다 면,left 는 변 하지 않 고,오른쪽 은 i-1 로 뛴다.

다 르 면 업데이트 결과,left 는 right+1,right 는 i-1 로 변 합 니 다.

마지막 으로 순환 이 끝 난 후에 우 리 는 결과 res 와 n-left 의 크기 를 비교 하고 큰 것 으로 돌아 가 야 한다.이것 은 배열 이[5,3,5,2,1,1,1]이 라면 left=3 시,i=5,6 시 에 모두 계속 순환 하기 때문이다.i 가 7 까지 추 가 했 을 때 순환 이 뛰 었 기 때문이다.이때 정 답 은[2,1,1,1]이라는 네 개의 숫자 이 고 우리 의 결 과 는 res 는[5,3,5]이 세 개의 숫자 이기 때문에 우 리 는 마지막 으로 n-left 와 결과 res 의 크기 를 판단 해 야 한다.
또한 이 해법 은 서로 다른 문자 수가 2 개 인 경우 에 만 적용 되 며,k 개 라면 위의 두 가지 해법 을 사용 해 야 한 다 는 것 을 설명 해 야 한다.
해법 3:

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, left = 0, right = -1, n = tree.size();
        for (int i = 1; i < n; ++i) {
            if (tree[i] == tree[i - 1]) continue;
            if (right >= 0 && tree[right] != tree[i]) {
                res = max(res, i - left);
                left = right + 1;
            }
            right = i - 1;
        }
        return max(n - left, res);
    }
};

HashMap 을 사용 하지 않 는 해법 도 있 습 니 다.여기 서 우 리 는 몇 가지 변 수 를 사용 합 니 다.그 중에서 cur 는 현재 최 장자 배열 의 길이 이 고 a 와 b 는 현재 후보 인 두 개의 서로 다른 과일 종류 이 며 cntB 는 과일 b 의 연속 갯 수 입 니 다.우 리 는 모든 숫자 를 옮 겨 다 녔 습 니 다.만약 에 만난 과일 종류 가 a 와 b 중 어느 하나 라면 cur 는 1 을 증가 할 수 있 습 니 다.그렇지 않 으 면 cntB 는 1 을 증가 할 수 있 습 니 다.만약 에 새로운 과일 종류 라면 기본적으로 a 종 류 를 도 태 했 습 니 다.이 때 과일 을 선택 하여 유형 b 와 이 새로운 유형의 과일 로 구성 할 수 있 기 때문에 현재 길 이 는 cntB+1 입 니 다.그리고 cntB 를 업데이트 합 니 다.현재 과일 종류 가 b 라면 cntB 는 1 을 증가 합 니 다.그렇지 않 으 면 1 로 초기 화 합 니 다.cntB 가 집계 하 는 것 은 과일 종류 b 의 연속 개수 이기 때 문 입 니 다.그리고 현재 종류 가 b 가 아니라면 이때 a 대 가 는 b 이 고 b 대 가 는 새로운 종류 라 고 판단 합 니 다.마지막 으로 결과 res 를 cur 로 업데이트 하 는 것 을 잊 지 마 세 요.코드 는 다음 과 같 습 니 다.
해법 4:

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, cur = 0, cntB = 0, a = 0, b = 0;
        for (int fruit : tree) {
            cur = (fruit == a || fruit == b) ? cur + 1 : cntB + 1;
            cntB = (fruit == b) ? cntB + 1 : 1;
            if (b != fruit) {
                a = b; b = fruit;
            }
            res = max(res, cur);
        }
        return res;
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/904
참고 자료:
https://leetcode.com/problems/fruit-into-baskets/
https://leetcode.com/problems/fruit-into-baskets/discuss/170740/Sliding-Window-for-K-Elements
https://leetcode.com/problems/fruit-into-baskets/discuss/170745/Problem%3A-Longest-Subarray-With-2-Elements
https://leetcode.com/problems/fruit-into-baskets/discuss/170808/Java-Longest-Subarray-with-atmost-2-Distinct-elements
C++구현 LeetCode(904.과일 바구니 에 넣 기)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 과일 바구니 에 넣 기 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!