《剑指offer》
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.解法
数据量达到了105数量级，显然不能用O(n*n)算法，否则运算次数达到了O(1010)，估计要消耗几十秒。。。
考虑归并排序，合并过程中，顺便把逆序对的数量也算出来。
注意每次更新逆序数都要对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;
};
