알고리즘 학습 - leetcode 659. 분할 배열 은 연속 서브 시퀀스 입 니 다.

1851 단어 알고리즘
오름차 순 으로 정렬 된 정수 배열 을 입력 하 십시오. (중복 숫자 를 포함 할 수 있 습 니 다) 몇 개의 하위 서열 로 나 누 어야 합 니 다. 그 중에서 각 하위 서열 은 적어도 세 개의 연속 정 수 를 포함 합 니 다.당신 에 게 돌아 가 이런 분할 을 할 수 있 습 니까?
예시 1:
  : [1,2,3,3,4,5]
  : True
  :
                : 
1, 2, 3
3, 4, 5

예시 2:
  : [1,2,3,3,4,4,5,5]
  : True
  :
                : 
1, 2, 3, 4, 5
3, 4, 5

예시 3:
  : [1,2,3,4,4,5]
  : False


알림:
  • 입력 한 배열 의 길이 범 위 는 [1, 10000]
  • 이다.
     
    문제 풀이 방향:
    맵 두 개 사용 하기  left 와 need
    left [i] 메모리 i 가 nums 배열 에 나타 난 횟수
    need [i] 에 따 르 면 앞의 것 은 연속 적 인 세 개의 정수 서열 을 구성 했다. 예 를 들 어 [1, 2, 3] 로 구 성 된 후에 need [4] 에 하 나 를 더 하고 4 가 있 으 면 need [5] 에 하 나 를 더 하 는 것 이다.
    class Solution {
    public:
        bool isPossible(vector& nums) {
            map left,need;
            for(int num:nums){  //     ,          
                left[num]++;
            }
            for(int num:nums){  //     ,               ,  left       0(        )
                if(left[num]==0)   //                 
                    continue;
                else if(need[num]>0){  //   ,              
                    need[num]--;
                    need[num+1]++;
                }
                else if((left[num+1]>0)&&(left[num+2]>0)){ //                    
                    left[num+1]--;
                    left[num+2]--;
                    need[num+3]++;
                }
                else  //   ,   false
                    return false;
                left[num]--;
            }
            return true;
        }
    };

    참고:
    https://blog.csdn.net/JackZhang_123 / article / details / 78866342 (알고리즘 사상)
    https://blog.csdn.net/u011806486/article/details/79827739(map 의 사용)

    좋은 웹페이지 즐겨찾기