1.字符串的排列

1.1.題目

題目描述

輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。

輸入描述

輸入一個字符串,長度不超過9(可能有字符重復(fù)),字符只包括大小寫字母。

1.2.解法一

思路：根據(jù)當(dāng)前字符串Sn，計(jì)算出比它大1的字符串Sn+1，然后將Sn+1編程當(dāng)前狀態(tài)，遞歸執(zhí)行。

class Solution {
public:
    void sort_str(string &str) {
        for(int i=1 ; i<str.size(); ++i)
            for(int j=i ; j>0 && str[j]<str[j-1] ; --j)
                swap(str[j], str[j-1]);
    }
    
    //必須保證rv非空
    void f(vector<string> &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--]);//可別把這步給忘了呀！要嚴(yán)謹(jǐn)！嚴(yán)謹(jǐn)?。?！
        rv.push_back(s);
        f(rv);
    }
    
    vector<string> Permutation(string str) {
        vector<string> rv;
        if(str.empty()) return rv;
        sort_str(str);
        rv.push_back(str);
        f(rv);
        return rv;
    }

1.3.解法二（參考了《劍指offer》）

注意，我看的是紀(jì)念版的《劍指offer》，這個版本作者給出的代碼是錯的。應(yīng)該要傳值，而不是指針。

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> rv;
        dfs(rv, str, 0);
        return rv;
    }
    void dfs(vector<string> &rv, string s, size_t start){
        if(start==s.size()) return;
        size_t starth=start;
        while(starth<s.size()-1 && s[starth]==s[starth+1])
            ++starth;
        if(starth==s.size()-1){
            rv.push_back(s);
            return;
        }
        for(int i=start; i<s.size();++i){
            char temp=s[i];
            swap(s[start],s[i]);
            dfs(rv,s,start+1);
            while(i<s.size()-1 && temp==s[i+1])//考慮到有重復(fù)的字符，所以要有這個循環(huán)
                ++i;
        }
    }
};

2.數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

2.1.題目

題目描述

數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0。

2.2.解法一(參考《劍指offer》)

既然出現(xiàn)次數(shù)大于一半，那么中位數(shù)可定是所求的結(jié)果。
通過比較的方式，來求一個數(shù)組中第k大的數(shù)，理論最優(yōu)時間復(fù)雜度是O(n)，例如五分法，但代碼比較繁瑣。這里采用的方法，最差的時間復(fù)雜度雖然是O(n*n)，但平均復(fù)雜度也是O(n)噠。
采用快排的思想，跟快排的不同點(diǎn)是，快排把原數(shù)組分成兩個子數(shù)組后，對這兩個子數(shù)組都進(jìn)行遞歸調(diào)用，而這里只對其中一個感興趣的數(shù)組進(jìn)行遞歸調(diào)用就可以啦，正因?yàn)檫@個，才使得平均時間復(fù)雜度由于快排的O(nlogn)變成了O(n)。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> 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<int> &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){}
            while(numbers[--j]>pivod){}
            if(i<j)
                swap(numbers[i],numbers[j]);
            else
                break;
        }
        swap(numbers[i],numbers[r-1]);
        if(m<i) return find_middle(numbers, l ,i);
        if(m>i) return find_middle(numbers,i+1,r);
        return numbers[m];
    }
    
    void partial(vector<int> &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[r-1]) swap(numbers[middle],numbers[r-1]);
        swap(numbers[middle],numbers[r-2]);
    }
    
    bool check(vector<int> &numbers,int rv){
        int count=0;
        for(size_t i=0 ; i<numbers.size(); ++i)
            if(rv==numbers[i]) ++count;
        if(count>numbers.size()/2) return true;
        return false;
    }
    
    int m=0;
};

2.3.解法二(參考《劍指offer》)

即使我們把所有其它的數(shù)都去對消這個出現(xiàn)頻率最高的數(shù)，最后還是不能把這個數(shù)給對消完，因此就有如下算法：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> 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<int> &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.題目

題目描述

輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）

3.2.解法

構(gòu)造一個輔助棧，例如：12345順序入棧，出棧序列是45321，如果棧是空的，就將1入輔助棧，然后繼續(xù)檢查棧頂元素，發(fā)現(xiàn)它和第二個序列的第一個元素不同，于是繼續(xù)將2入棧，再次檢查棧頂元素是否和4相同，...，當(dāng)壓入4的時候，棧頂元素和4相同，則出棧，并且比較出棧后新的棧頂元素是否和第二個序列的下一個元素，即5相同，顯然3和5不相同，則將第一個序列的5入棧。。。
上述過程實(shí)際上就是在重現(xiàn)出棧入棧的過程。觀察第二個序列的增長，顯然第二個序列增長是最慢的。如果第二個序列不是出棧序列，唯一的情況就是，第一個序列全部都入棧了，但棧頂元素跟第二個序列要處理的元素不同。。。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        vector<int> 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個數(shù)

4.1.題目

題目描述

輸入n個整數(shù)，找出其中最小的K個數(shù)。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字，則最小的4個數(shù)字是1,2,3,4

4.2.解法一

用stl中的優(yōu)先隊(duì)列
建堆的時間復(fù)雜度是O(n)，查找一次的時間復(fù)雜度是O(logn)， k次就是O(klogn), 所以總的時間復(fù)雜度是O(n+klogn)，空間復(fù)雜度。。。是O(n)

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

4.3.解法二

快排的思想，為前k個數(shù)排序，時間復(fù)雜度應(yīng)該是取決于k吧，最差肯定是O(n*n)，平均。。。猜測應(yīng)該是O(n+klogk)

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> 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<int> &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<int> &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.最大子數(shù)組的和

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> 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.整數(shù)中1出現(xiàn)的次數(shù)

先找規(guī)律：
區(qū)間[0,9]中，出現(xiàn)的次數(shù)是f(1)=1；
區(qū)間[0,99]中，出現(xiàn)的次數(shù)是:f(2)=10f(1)+10,這里，10f(1)表示個位是1的次數(shù)，10表示是為是1的次數(shù)，例如10,11,...,19這10個數(shù)的十位都是1.
類推，可以知道：
f(1)=1;
f(n)=10f(n-1)+10^(n-1), n>1;
于是f(n)的通項(xiàng)：
f(n)=n10^(n-1)
用g(n)表示0到n中1出現(xiàn)的次數(shù)，例如g(612372),那么，顯然有：
g(612372)=6f(5)+100000+g(12372)
再如：
g(112372)=1f(5)+12372+g(12372)
從高位到低位算起，這個是遞歸的解法。
當(dāng)然，也可以從低位向高位算起，這個時候就不用遞歸了。代碼也更簡單。

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.把數(shù)組排成最小的數(shù)

7.1. 題目

題目描述

輸入一個正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)，打印能拼接出的所有數(shù)字中最小的一個。例如輸入數(shù)組{3，32，321}，則打印出這三個數(shù)字能排成的最小數(shù)字為321323。

7.2. 解法（參考《劍指offer》）

定義運(yùn)算a<b，它表示十進(jìn)制的數(shù)ab小于ba，在這種定義下，它是個序，詳細(xì)證明參考《劍指offer》
在上述序的前提下，把數(shù)組從小到大排序，然后依次打印出數(shù)組中的元素，打印的結(jié)果就是最終答案。

class Solution {
public:

    string PrintMinNumber(vector<int> 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<r;
    }

    int pow(int n){
        int rv=1;
        while(n--){
            rv*=10;
        }
        return rv;
    }

    int bit_(int n){
        int rv=0;
        do{
            ++rv;
            n/=10;
        }while(n);
        return rv;
    }
};

8.丑數(shù)

8.1.題目

題目描述

把只包含因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6、8都是丑數(shù)，但14不是，因?yàn)樗蜃?。 習(xí)慣上我們把1當(dāng)做是第一個丑數(shù)。求按從小到大的順序的第N個丑數(shù)。

8.2.解法一（O(nlogn)的復(fù)雜度）

維持一個記錄從小到大排列的丑數(shù)矢量，當(dāng)我們要計(jì)算下一個更大的丑數(shù)的時候，不外乎就是把這個矢量的某一個元素乘以2,3，或者5.二分查找的話，這個過程的復(fù)雜度是log(n)，因此總的復(fù)雜度就是nlog(n)
注意，二分法一定要處理好邊界條件，例如這里，當(dāng)r-l==2的時候，如果繼續(xù)遞歸，則會死循環(huán)。

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<int> 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.解法二：對解法一的優(yōu)化(O(n)的復(fù)雜度)

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<int> ugly;
    size_t next2idx=0;
    size_t next3idx=0;
    size_t next5idx=0;
};

9.第一個只出現(xiàn)一次的字符

9.1.題目

題目描述

在一個字符串(1<=字符串長度<=10000，全部由字母組成)中找到第一個只出現(xiàn)一次的字符,并返回它的位置

9.2.解法

采用hash的思想，不過，因?yàn)樵氐姆N類太少，這個hashtable足夠大，完全不用考慮如何解決沖突
如果字符沒有粗線，則其在hashtable中的值是-2，如果出現(xiàn)了多次，則為-1，如果只出現(xiàn)一次，則是它所出現(xiàn)的位置。最后遍歷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.數(shù)組中的逆序?qū)?/h1>

10.1.題目

題目描述

在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)Α］斎胍粋€數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對1000000007取模的結(jié)果輸出。 即輸出P%1000000007

輸入描述:

題目保證輸入的數(shù)組中沒有的相同的數(shù)字
數(shù)據(jù)范圍：
對于%50的數(shù)據(jù),size<=10^4
對于%75的數(shù)據(jù),size<=10^5
對于%100的數(shù)據(jù),size<=2*10^5

10.2.解法

數(shù)據(jù)量達(dá)到了10^{5數(shù)量級，顯然不能用O(n*n)算法，否則運(yùn)算次數(shù)達(dá)到了O(10}10)，估計(jì)要消耗幾十秒。。。
考慮歸并排序，合并過程中，順便把逆序?qū)Φ臄?shù)量也算出來。
注意每次更新逆序數(shù)都要對1000000007，否則溢出產(chǎn)生的錯誤會讓人莫名其妙。。。（因?yàn)槟嫘驅(qū)Φ臄?shù)據(jù)類型是int型號，所能表示的最大數(shù)大致比2倍的1000000007多出一小點(diǎn)點(diǎn)，而2*10^5最高逆序?qū)?shù)是int所能表示的最大正整數(shù)的10倍。。。）

class Solution {
public:
    int InversePairs(vector<int> data) {
        temp=data;
        return merge_sort(data, temp, 0, data.size());
    }
    int merge_sort(vector<int> &data, vector<int> &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<int> &data, vector<int> &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 <r){
            if(data[i] < data[j] ){
                temp[k++]=data[i++];
                rv=(rv+j-middle)%1000000007;
            }else{
                temp[k++]=data[j++];
            }
        }
        while(i != middle){
            temp[k++]=data[i++];
            rv=(rv+j-middle)%1000000007;
        }
        while(j != r){
            temp[k++]=data[j++];
        }
        for(int i=l ; i < r ; ++i )
            data[i]=temp[i];
        return rv;
    }
private:
    vector<int> temp;
};