《 검 지 offer 》

1. 문자열 의 배열
1. 1. 제목
제목 설명
문자열 을 입력 하고 이 문자열 의 모든 배열 을 사전 순서에 따라 출력 하 십시오.예 를 들 어 문자열 abc 를 입력 하면 문자 a, b, c 가 배열 할 수 있 는 모든 문자열 abc, acb, bac, bca, cab 와 cba 를 출력 합 니 다.
입력 설명
길이 가 9 을 넘 지 않 는 문자열 을 입력 하 십시오. 대소 문자 만 포함 합 니 다.
1, 2. 해법 1
사고: 현재 문자열 Sn 에 따라 1 보다 큰 문자열 Sn + 1 을 계산 한 다음 에 Sn + 1 을 현재 상태 로 프로 그래 밍 하여 재 귀적 으로 실행 합 니 다.

class Solution {
public:
    void sort_str(string &str) {
        for(int i=1 ; i0 && str[j] &rv){
        string s=rv[rv.size()-1];
        int i;
        for(i=s.size()-1 ; i>0 && s[i]<=s[i-1] ;--i)
            ;
        if(i==0) return;
        int j;
        for(j=s.size()-1 ; s[j]<=s[i-1]; --j)
            ;
        swap( s[i-1], s[j] );
        int n=s.size()-1;
        while(n>i)
            swap(s[i++],s[n--]);//         ！   ！  ！！！
        rv.push_back(s);
        f(rv);
    }
    
    vector Permutation(string str) {
        vector rv;
        if(str.empty()) return rv;
        sort_str(str);
        rv.push_back(str);
        f(rv);
        return rv;
    }

1.3. 해법 2 (검 지 offer 참조)
주의 하 세 요. 제 가 본 것 은 기념 판 인 을 보 았 는데 이 버 전 작가 가 제시 한 코드 가 틀 렸 습 니 다.지침 이 아니 라 값 을 전달 해 야 한다.

class Solution {
public:
    vector Permutation(string str) {
        vector rv;
        dfs(rv, str, 0);
        return rv;
    }
    void dfs(vector &rv, string s, size_t start){
        if(start==s.size()) return;
        size_t starth=start;
        while(starth

2. 배열 에 나타 난 횟수 가 절반 을 넘 는 숫자
2.1. 제목
제목 설명
배열 에 나타 난 숫자 가 배열 길이 의 절반 을 넘 으 니 이 숫자 를 찾 아 보 세 요.예 를 들 어 길이 가 9 인 배열 {1, 2, 3, 2, 2, 5, 4, 2} 을 입력 하 십시오.숫자 2 는 배열 에서 5 번 나타 나 배열 길이 의 절반 을 넘 기 때문에 출력 2.존재 하지 않 으 면 0 을 출력 합 니 다.
2.2. 해법 1 (검 지 offer 참조)
횟수 가 절반 이상 나 온 이상 중위 수 는 원 하 는 결과 일 것 이다.비교 하 는 방식 을 통 해 한 배열 에서 k 번 째 로 큰 수 를 구하 고 이론 적 으로 가장 좋 은 시간 복잡 도 는 O (n) 이다. 예 를 들 어 5 분 법 이지 만 코드 는 비교적 번거롭다.여기 서 사용 하 는 방법 은 최 악의 시간 복잡 도 는 O (n * n) 이지 만 평균 복잡 도 역시 O (n) 이다.빠 른 배열 의 사상 을 사용 하 는 것 과 빠 른 배열 의 차이 점 은 원래 의 배열 을 두 개의 배열 로 나 눈 후에 이 두 개의 배열 을 모두 재 귀적 으로 호출 하 는 것 이다. 여 기 는 그 중의 관심 이 있 는 배열 만 재 귀적 으로 호출 하면 된다. 그래서 평균 시간 복잡 도 는 빠 른 배열 의 O (nlogn) 로 인해 O (n) 가 되 었 다.

class Solution {
public:
    int MoreThanHalfNum_Solution(vector numbers) {
        if(numbers.empty()) return 0;
        int mid;
        if(numbers.size() < 3)
            mid=numbers[0];
        else{
            m=numbers.size()/2;
            mid=find_middle(numbers,0,numbers.size());
        }
        if(check(numbers,mid))
            return mid;
        return 0;
    }
private:
    int find_middle(vector &numbers, size_t l, size_t r){
        if(r-l ==1) return numbers[l];
        if(r-l ==2){
            if(numbers[l]>numbers[l+1]) swap(numbers[l],numbers[l+1]);
            return numbers[m];
        }
        partial(numbers,l,r);
        size_t i=l;
        size_t j=r-2;
        int pivod=numbers[r-1];
        while(true){
            while(numbers[++i]pivod){}
            if(ii) return find_middle(numbers,i+1,r);
        return numbers[m];
    }
    
    void partial(vector &numbers,size_t l, size_t r){
        size_t middle=(l+r)/2;
        if(numbers[l]>numbers[middle]) swap(numbers[l], numbers[middle]);
        if(numbers[l]>numbers[r-1]) swap(numbers[l],numbers[r-1]);
        if(numbers[middle] &numbers,int rv){
        int count=0;
        for(size_t i=0 ; inumbers.size()/2) return true;
        return false;
    }
    
    int m=0;
};

2.3. 해법 2 (검 지 offer 참조)
비록 우리 가 모든 다른 수 를 이 출현 빈도 가 가장 높 은 수 를 상쇄 하 더 라 도 결국 이 수 를 상쇄 할 수 없 기 때문에 다음 과 같은 알고리즘 이 있다.

class Solution {
public:
    int MoreThanHalfNum_Solution(vector numbers) {
        if(numbers.empty()) return 0;
        int rv;
        int count=0;
        for(int i=0; i < numbers.size() ; ++i){
            if(count==0){
                rv=numbers[i];
                ++count;
            }else if(rv==numbers[i])
                ++count;
            else
                --count;
        }
        if(count==0) return 0;
        if(check(numbers,rv)) return rv;
        return 0;
    }
private:
    bool check(vector &numbers,int rv){
        int count=0;
        for(int i=0; i < numbers.size(); ++i)
            if(rv==numbers[i]) ++count;
        return count>numbers.size()/2;
    }
};

3. 창고 의 압축, 팝 업 시퀀스
3.1. 제목
제목 설명
두 개의 정수 서열 을 입력 하 십시오. 첫 번 째 서열 은 창고 의 압축 순 서 를 표시 합 니 다. 두 번 째 서열 이 창고 의 팝 업 순서 인지 판단 하 십시오.창고 에 쌓 인 모든 숫자 가 같 지 않다 고 가정 하 세 요.예 를 들 어 서열 1, 2, 3, 4, 5 는 특정한 스 택 의 압 입 순서 이 고 서열 4, 5, 3, 2, 1 은 이 스 택 서열 에 대응 하 는 팝 업 서열 이지 만 4, 3, 5, 1, 2 는 이 스 택 서열 의 팝 업 서열 일 수 없다.(주의: 이 두 서열 의 길 이 는 같다)
3.2 해법
보조 스 택 을 만 듭 니 다. 예 를 들 어 12345 순서 로 스 택 에 들 어가 면 스 택 의 순서 가 45321 입 니 다. 스 택 이 비어 있 으 면 1 을 보조 스 택 에 들 어간 다음 에 스 택 의 요 소 를 계속 검사 한 다음 에 두 번 째 서열 의 첫 번 째 요소 와 다르다 는 것 을 알 게 되 었 습 니 다. 그래서 2 를 스 택 에 들 어가 서 스 택 의 요소 가 4 와 같 는 지 다시 확인 합 니 다. 4 를 눌 렀 을 때 스 택 의 꼭대기 요 소 는 4 와 같 으 면 스 택 에서 나 옵 니 다.또한 스 택 후 새로운 스 택 꼭대기 요소 가 두 번 째 서열 의 다음 요소, 즉 5 와 같 는 지 비교 하면 3 과 5 가 다 르 면 첫 번 째 서열 의 5 를 스 택 에 넣 습 니 다.상술 한 과정 은 사실상 창고 에서 나 와 창고 에 들 어 가 는 과정 을 재현 하 는 것 이다.두 번 째 서열 의 증 가 를 관찰 하면 두 번 째 서열 의 성장 이 가장 느 린 것 이 분명 하 다.만약 에 두 번 째 서열 이 스 택 서열 이 아니라면 유일한 상황 은 첫 번 째 서열 이 모두 스 택 에 들 어 갔 지만 스 택 꼭대기 요 소 는 두 번 째 서열 에서 처리 해 야 할 요소 와 다르다 는 것 이다.

class Solution {
public:
    bool IsPopOrder(vector pushV,vector popV) {
        vector stack1;
        auto ab=pushV.begin();
        auto bb=popV.begin();
        while(bb != popV.end()){
            if( ab == pushV.end() && stack1[stack1.size()-1] != *bb ) return false;
            if(stack1.empty() || stack1[stack1.size()-1] != *bb )
                stack1.push_back(*ab++);
            else{
                stack1.pop_back();
                ++bb;
            }
        }
        return true;
    }
};

4. 최소 k 개수
4.1 제목
제목 설명
n 개의 정 수 를 입력 하여 그 중에서 가장 작은 K 개 수 를 찾 아 라.예 를 들 어 4, 5, 1, 6, 2, 7, 3, 8 이라는 8 개의 숫자 를 입력 하면 가장 작은 4 개의 숫자 는 1, 2, 3, 4 이다.
4.2. 해법 1
stl 의 우선 대기 열 로 쌓 는 시간 복잡 도 는 O (n) 이 고 한 번 찾 는 시간 복잡 도 는 O (logn) 이 며 k 번 은 O (klogn) 이기 때문에 전체적인 시간 복잡 도 는 O (n + klogn) 이 고 공간 복잡 도 입 니 다.O (n) 입 니 다.

class Solution {
public:
    vector GetLeastNumbers_Solution(vector input, int k) {
        vector return_value;
        if(input.empty() || k <=0 || k>input.size())
            return return_value;
        priority_queue,greater > d(input.begin(),input.end());
        while(k--){
            return_value.push_back(d.top());
            d.pop();
        }
        return return_value;
    }
};

4.3. 해법 2
빨리 배열 하 는 사상 은 앞의 k 개 수 를 정렬 하 는 것 이 고 시간 복잡 도 는 k 에 달 려 있 을 것 이다. 최 악 은 O (n * n) 이 고 평균 이다.추측 은 O (n + klogk)

class Solution {
public:
    vector GetLeastNumbers_Solution(vector input, int k) {
        vector rv;
        if( input.empty() || k>input.size() ) return rv;
        partial_sort( input , 0 , input.size() , k );
        for(int i = 0 ; i < k ; ++i) 
            rv.push_back( input[i] );
        return rv;
    }
private:
    void partial_sort(vector &input, int l, int r, int k){
        if(r-l < 2) return;
        if(r-l == 2 ){
            if( input[l] > input[l+1] )
                swap( input[l] , input[l+1] );
            return;
        }
        mid( input, l , r );
        int i=l;
        int j=r-2;
        int pivod = input[r-1];
        while( i < j ) {
            while( input[++i] < pivod ) {}
            while( input[--j] > pivod ) {}
            if( i < j )
                swap( input[i] , input[j] );
            else
                break;
        }
        swap( input[i] , input[r-1] );
        partial_sort( input , l , i , k );
        if( k > i+1 ) partial_sort( input , i+1 , r , k);
    }
    
    void mid(vector &input , int l , int r) {
        int middle = ( l + r )/2;
        if( input[l] > input[r-1] ) swap( input[l] , input[r-1] );
        if( input[l] > input[middle] ) swap( input[l] , input[middle] );
        if( input[r-1] > input[middle] ) swap( input[r-1] , input[middle] );
        swap( input[r-2] , input[middle] );
    }
};

5. 최대 하위 배열 의 합

class Solution {
public:
    int FindGreatestSumOfSubArray(vector array) {
        int accum=0;
        int max=(1<<31);
        for( int i=0 ; i < array.size() ; ++i ){
            accum+=array[i];
            if(accum > max ) max=accum;
            if(accum < 0 ) accum=0;
        }
        return max;
    }
};

6. 정수 중 1 이 나 오 는 횟수
먼저 규칙 찾기: 구간 [0, 9] 에서 나타 난 횟수 는 f (1) = 1 이다.구간 [0, 99] 에서 나타 난 횟수 는 f (2) = 10f (1) + 10 이다. 여기 서 10f (1) 는 개 위 는 1 의 횟수 를 나타 내 고 10 은 1 의 횟수 를 나타 낸다. 예 를 들 어 10, 11,... 19 이 10 개의 수 는 모두 1 이다. 유추 하면 f (1) = 1 을 알 수 있다.f(n)=10f(n-1)+10^(n-1), n>1; 그래서 f (n) 의 통항: f (n) = n10 ^ (n - 1) 는 g (n) 으로 0 에서 n 중 1 이 나타 나 는 횟수 를 나타 낸다. 예 를 들 어 g (612372) 는 g (612372) = 6f (5) + 100000 + g (12372), 예 를 들 어 g (112372) = 1f (5) + 12372 + g (12372) 이 높 은 위치 에서 낮은 위치 로 계산 하면 이것 은 재 귀적 인 해법 이다.물론 낮은 자리 에서 높 은 자리 로 계산 할 수도 있 고 이 럴 때 는 재 귀적 이지 않 아 도 된다.코드 도 더 쉬 워 요.

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        if(n<=0) return 0;
        int count=0;
        int nn=n;
        if(nn%10) ++count;
        nn/=10;
        int pow=1;
        int idx=1;
        int temp;
        while(nn){
            temp=nn%10;
            count+=temp*idx*pow;
            if(temp>1) count+=pow*10;
            if(temp==1) count+=n%(pow*10)+1;
            ++idx;
            pow*=10;
            nn/=10;
        }
        return count;
    }
};

7. 배열 을 가장 작은 수로 배열 한다.
7.1. 제목
제목 설명
정수 배열 을 입력 하고 배열 의 모든 숫자 를 연결 하여 하나의 숫자 로 배열 하 며 연결 할 수 있 는 모든 숫자 중 가장 작은 숫자 를 인쇄 합 니 다.예 를 들 어 배열 {3, 32, 321} 을 입력 하면 이 세 숫자 가 배열 할 수 있 는 최소 숫자 는 321323 이다.
7.2. 해법 (검 지 offer 참조)
연산 a 를 정의 합 니 다. 상기 순서 에서 배열 을 작은 것 에서 큰 것 으로 정렬 한 다음 에 배열 의 요 소 를 순서대로 인쇄 합 니 다. 인쇄 결 과 는 최종 답 입 니 다.

class Solution {
public:

    string PrintMinNumber(vector numbers) {
        sort(numbers.begin(), numbers.end(), Solution());
        string s;
        s.reserve(numbers.size()*4);
        for(int i=0 ; i < numbers.size() ; ++i)
            s+=to_string(numbers[i]);
        return s;
    }
    
    bool operator ()(const int &a, const int &b){
        return less_(a,b);
    }
private:
    bool less_(const int &a, const int &b){
        long l=((long)a*pow(bit_(b)))+b;
        long r=((long)b*pow(bit_(a)))+a;
        return l

8. 실수
8.1. 제목
제목 설명
인자 2, 3, 5 만 포 함 된 수 를 축 수 (Ugly Number) 라 고 한다.예 를 들 어 6, 8 은 모두 추 수 이지 만 14 는 인자 7 을 포함 하기 때문이다.습관 적 으로 우 리 는 1 을 첫 번 째 못 생 긴 숫자 로 여 긴 다.어 릴 때 부터 큰 순서 로 N 번 째 축 수 를 구하 세 요.
8.2. 해법 1 (O (nlogn) 의 복잡 도)
작은 것 부터 큰 것 까지 배열 한 어릿광대 벡터 를 유지 합 니 다. 우리 가 다음 에 더 큰 어릿광대 수 를 계산 하려 고 할 때 이 벡터 의 특정한 요 소 를 2, 3 또는 5 로 곱 하면 이 과정의 복잡 도 는 log (n) 이기 때문에 전체적인 복잡 도 는 nlog (n) 입 니 다. 주의 하 세 요. 이분법 은 반드시 경계 조건 을 잘 처리 해 야 합 니 다. 예 를 들 어 여기,r - l = = 2 일 때 계속 재 귀 하면 순환 이 된다.

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<1) return 0;
        ugly.push_back(1);
        while(--index > 0)
            ugly.push_back(find_next());
        return ugly[ugly.size()-1];
    }
private:
    vector ugly;
    int find_next(){
        int m2=find_next_factor(2, 0, ugly.size());
        int m3=find_next_factor(3, 0, ugly.size());
        int m5=find_next_factor(5, 0, ugly.size());
        if(m2>m3) swap(m2, m3);
        if(m2>m5) swap(m2, m5);
        return m2;
    }
    int find_next_factor(int factor, size_t l, size_t r){
        if(r-l==1) return factor*ugly[l];
        if(r-l==2) return factor*ugly[l]>ugly[ugly.size()-1]?factor*ugly[l]:factor*ugly[l+1];
        int middle=(l+r)/2;
        if(factor*ugly[middle] > ugly[ugly.size()-1])
            return find_next_factor(factor, l, middle+1);
        return find_next_factor(factor, middle+1, r);
    }
};

8.3. 해법 2: 해법 1 에 대한 최적화 (O (n) 의 복잡 도)

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index < 1 ) return 0;
        ugly.push_back(1);
        while(--index)
            next_();
        return ugly[ugly.size()-1];
    }
private:
    void next_(){
        int temp2=ugly[next2idx]*2;
        int temp3=ugly[next3idx]*3;
        int temp5=ugly[next5idx]*5;
        int min_temp=temp2;
        if(min_temp>temp3) min_temp=temp3;
        if(min_temp>temp5) min_temp=temp5;
        if(min_temp == temp2) ++next2idx;
        if(min_temp == temp3) ++next3idx;
        if(min_temp == temp5) ++next5idx;
        ugly.push_back(min_temp);
    }
    vector ugly;
    size_t next2idx=0;
    size_t next3idx=0;
    size_t next5idx=0;
};

9. 첫 번 째 한 번 만 나타 나 는 문자
9.1. 제목
제목 설명
한 문자열 (1 < = 문자열 길이 < = 10000, 모두 알파벳 으로 구성) 에서 첫 번 째 로 한 번 만 나타 나 는 문 자 를 찾 아 그 위 치 를 되 돌려 줍 니 다.
9.2. 해법
hash 의 사상 을 사용 합 니 다. 그러나 요소 의 종류 가 너무 적 기 때문에 이 hashtable 은 충분 합 니 다. 충돌 을 어떻게 해결 하 는 지 전혀 고려 하지 않 아 도 됩 니 다. 만약 에 문자 가 굵 은 선 이 없 으 면 hashtable 에서 의 값 은 - 2 이 고 여러 번 나타 나 면 - 1 이 며 한 번 만 나타 나 면 나타 나 는 위치 입 니 다.마지막 으로 hashtable 을 옮 겨 다 니 며 가장 앞 에 있 는 위 치 를 얻 습 니 다.

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        size_t table_size='z'-'A'+1;
        size_t begin_='A';
        int hash_table['z'-'A'+1];
        for(int i=0 ; i < table_size ; ++i)
            hash_table[i]=-2;
        for(int i=0 ; i < str.size() ; ++i){
            int idx=str[i]-begin_;
            if( hash_table[idx] == -2)
                hash_table[idx]=i;
            else if(hash_table[idx] >= 0)
                hash_table[idx]=-1;
        }
        
        size_t min=10000;
        for(int i=0 ; i < table_size ; ++i)
            if(hash_table[i] >= 0 && hash_table[i] < min ) min=hash_table[i];
        if( min == 10000 ) return -1;
        return min;
    }
};

10. 배열 의 역순 대
10.1. 제목
제목 설명
배열 에 있 는 두 개의 숫자 가 앞의 숫자 가 뒤의 숫자 보다 크 면 이 두 개의 숫자 는 하나의 역순 대 를 구성한다.배열 을 입력 하여 이 배열 의 역순 쌍 의 총 P 를 구하 십시오.그리고 P 를 1000000007 모드 로 출력 합 니 다.출력 P% 1000000007
입력 설명:
제목 은 입력 한 배열 에 같은 숫자 데이터 범위 가 없습니다.% 50 의 데이터 에 대해 size < = 10 ^ 4% 75 의 데이터 에 대해 size < = 10 ^ 5% 100 의 데이터 에 대해 size < = 2 * 10 ^ 5
10.2. 해법
데이터 양 이 105 수량 급 에 이 르 렀 기 때문에 O (n * n) 알고리즘 을 사용 할 수 없 음 이 분명 하 다. 그렇지 않 으 면 연산 횟수 가 O (1010) 에 이 르 렀 고 몇 십 초 를 소모 할 것 으로 예상 된다.병합 순 서 를 고려 하고 합병 과정 에서 역순 대 수량 도 계산한다.매번 역 서 수 를 업데이트 할 때마다 1000000007 에 대해 야 합 니 다. 그렇지 않 으 면 넘 치 는 오류 가 영문 을 모 를 수 있 습 니 다.(역순 대 데이터 형식 은 int 모델 이기 때문에 표시 할 수 있 는 최대 수 는 대략 2 배의 1000000007 보다 조금 많 고 2 * 10 ^ 5 의 최고 역순 대 수 는 int 가 표시 할 수 있 는 최대 정수 의 10 배 이다.)

class Solution {
public:
    int InversePairs(vector data) {
        temp=data;
        return merge_sort(data, temp, 0, data.size());
    }
    int merge_sort(vector &data, vector &temp , size_t l , size_t r){
        if(r-l<=1) return 0;
        int middle=(l+r)/2;
        return (
                ( merge_sort(data, temp , l , middle) 
                + merge_sort(data, temp , middle , r) )%1000000007 
                + merge(data, temp , l , r))%1000000007;
    }
    int merge(vector &data, vector &temp , size_t l , size_t r){
        int middle=(l+r)/2;
        int i=l;
        int j=middle;
        int k=l;
        int rv=0;
        while( i < middle && j  temp;
};