1.字符串的排列

1.1.题目

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

1.2.解法一

思路：根据当前字符串Sn，计算出比它大1的字符串Sn+1，然后将Sn+1编程当前状态，递归执行。

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--]);//可别把这步给忘了呀！要严谨！严谨！！！
        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》）

注意，我看的是纪念版的《剑指offer》，这个版本作者给出的代码是错的。应该要传值，而不是指针。

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])//考虑到有重复的字符，所以要有这个循环
                ++i;
        }
    }
};

2.数组中出现次数超过一半的数字

2.1.题目

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

2.2.解法一(参考《剑指offer》)

既然出现次数大于一半，那么中位数可定是所求的结果。
通过比较的方式，来求一个数组中第k大的数，理论最优时间复杂度是O(n)，例如五分法，但代码比较繁琐。这里采用的方法，最差的时间复杂度虽然是O(n*n)，但平均复杂度也是O(n)哒。
采用快排的思想，跟快排的不同点是，快排把原数组分成两个子数组后，对这两个子数组都进行递归调用，而这里只对其中一个感兴趣的数组进行递归调用就可以啦，正因为这个，才使得平均时间复杂度由于快排的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》)

即使我们把所有其它的数都去对消这个出现频率最高的数，最后还是不能把这个数给对消完，因此就有如下算法：

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.题目

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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<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个数

4.1.题目

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4

4.2.解法一

用stl中的优先队列
建堆的时间复杂度是O(n)，查找一次的时间复杂度是O(logn)， k次就是O(klogn), 所以总的时间复杂度是O(n+klogn)，空间复杂度。。。是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个数排序，时间复杂度应该是取决于k吧，最差肯定是O(n*n)，平均。。。猜测应该是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.最大子数组的和

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.整数中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<b，它表示十进制的数ab小于ba，在这种定义下，它是个序，详细证明参考《剑指offer》
在上述序的前提下，把数组从小到大排序，然后依次打印出数组中的元素，打印的结果就是最终答案。

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.丑数

8.1.题目

题目描述

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

8.2.解法一（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<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.解法二：对解法一的优化(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<int> 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.解法

数据量达到了10^{5数量级，显然不能用O(n*n)算法，否则运算次数达到了O(10}10)，估计要消耗几十秒。。。
考虑归并排序，合并过程中，顺便把逆序对的数量也算出来。
注意每次更新逆序数都要对1000000007，否则溢出产生的错误会让人莫名其妙。。。（因为逆序对的数据类型是int型号，所能表示的最大数大致比2倍的1000000007多出一小点点，而2*10^5最高逆序对数是int所能表示的最大正整数的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;
};