【100题】第六十六~第七十题（颠倒栈、扑克牌顺子和掷骰子概率、数字数组排成最小数、求旋转数组中最小值、全排列）
一，颠倒栈。
1）题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。
2）分析：乍一看到这道题目，第一反应是把栈里的所有元素逐一pop出来，放到一个数组里，然后在数组里颠倒所有元素，最后把数组中的所有元素逐一push进入栈。这时栈也就颠倒过来了。颠倒一个数组是一件很容易的事情。不过这种思路需要显示分配一个长度为O(n)的数组，而且也没有充分利用递归的特性。
我们再来考虑怎么递归。我们把栈{1, 2, 3, 4, 5}看成由两部分组成：栈顶元素1和剩下的部分{2, 3, 4, 5}。如果我们能把{2, 3, 4, 5}颠倒过来，变成{5, 4, 3, 2}，然后在把原来的栈顶元素1放到底部，那么就整个栈就颠倒过来了，变成{5, 4, 3, 2, 1}。
接下来我们需要考虑两件事情：一是如何把{2, 3, 4, 5}颠倒过来变成{5, 4, 3, 2}。我们只要把{2, 3, 4, 5}看成由两部分组成：栈顶元素2和剩下的部分{3, 4, 5}。我们只要把{3, 4, 5}先颠倒过来变成{5, 4, 3}，然后再把之前的栈顶元素2放到最底部，也就变成了{5, 4, 3, 2}。
至于怎么把{3, 4, 5}颠倒过来……很多读者可能都想到这就是递归。也就是每一次试图颠倒一个栈的时候，现在栈顶元素pop出来，再颠倒剩下的元素组成的栈，最后把之前的栈顶元素放到剩下元素组成的栈的底部。递归结束的条件是剩下的栈已经空了。这种思路的代码如下：
template<typenameT>voidReverseStack(std::stack<T>& stack)
{
}
我们需要考虑的另外一件事情是如何把一个元素e放到一个栈的底部，也就是如何实现AddToStackBottom。这件事情不难，只需要把栈里原有的元素逐一pop出来。当栈为空的时候，push元素e进栈，此时它就位于栈的底部了。然后再把栈里原有的元素按照pop相反的顺序逐一push进栈。
注意到我们在push元素e之前，我们已经把栈里原有的所有元素都pop出来了，我们需要把它们保存起来，以便之后能把他们再push回去。我们当然可以开辟一个数组来做，但这没有必要。由于我们可以用递归来做这件事情，而递归本身就是一个栈结构。我们可以用递归的栈来保存这些元素。
基于如上分析，我们可以写出AddToStackBottom的代码：
// Add an element to the bottom of a stack:
template<typenameT>voidAddToStackBottom(std::stack<T>& stack, T t)
{
}
先弹出，处理，再恢复，化作子问题的一个重要方式
3）源码：
#include <iostream>#include <stack> using namespace std;template<typename T>void ReverseStack(stack<T>& stack){ if(!stack.empty()) { T top = stack.top();//Pop the top element stack.pop(); ReverseStack(stack); // Reverse the remaining stack AddToStackBottom(stack, top); //Add the top element to the bottom of the remaining stack }}template<typename T> void AddToStackBottom(stack<T>& stack, T t){ if(stack.empty()) { stack.push(t); } else { T top = stack.top(); stack.pop(); AddToStackBottom(stack, t); stack.push(top); }}void print(stack<int> mystack) {while(mystack.size()){cout<<mystack.top()<<" "; mystack.pop(); } }int main(){stack<int> mystack;mystack.push(1); mystack.push(2);mystack.push(3); mystack.push(4); mystack.push(5);print(mystack); printf("\n"); ReverseStack(mystack);printf("\n"); print(mystack); } 二，扑克牌和掷骰子
1）题目：扑克牌的顺子
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10 为数字本身，A 为1，J为11，Q 为12，K 为13，而大小王可以看成任意数字。
2）分析：
思路一：排序法，其中大小王看成0。然后，统计0个数，和数字间隔数，如果有重复（对子）则返回失败。间隔数小于等于2则成功，否则失败。
思路二：Hash法，类似排序。
3）源码:
注意：sort(int array[],array+nLength,comp); //注意添加 <algorithm> using namespace std;
qsort(int array[],nLength,sizeof(array[0]),compare); //自带的
#include <iostream>#include <algorithm>using namespace std;//函数功能 ： 从扑克牌中随机抽5张牌，判断是不是一个顺子//函数参数 ： pCards为牌，nLen为牌的张数//返回值 ： 是否顺子int comb(const int *x,const int *y){return x<y; //}int cmp(const void *x,const void *y){return *(int *)x - *(int *)y; //}bool IsContinuous(int *pCards, int nLen){if(pCards == NULL || nLen <= 0)return false;//sort(pCards, pCards + nLen,comb); //调用标准库的排序算法 qsort(pCards,nLen,sizeof(pCards[0]),cmp); //for(int i=0;i<nLen;++i) // cout<<pCards[i]<<" "; int i;int zeroCount = 0; //大小王用0表示int capCount = 0; //间隔数//统计0的个数for(i = 0; i < nLen; i++){if(pCards[i] == 0)zeroCount++;elsebreak;}//统计间隔数int preCard = pCards[i]; for(i = i + 1; i < nLen; i++){int curCard = pCards[i];if(preCard == curCard) //与前一张牌比较return false;elsecapCount += curCard - preCard - 1; //累加间隔数preCard = curCard;}return (zeroCount >= capCount)? true: false; //只要王的个数大于间隔数}int main(){int pCards[]={1,2,3,4,5};int pCards2[]={1,2,8,4,12};int i=IsContinuous(pCards,5);bool j=IsContinuous(pCards2,5);cout<<i<<endl;cout<<j<<endl;}1）题目：n 个骰子的点数。把n 个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，
2）分析：
用PN,S来表示N个骰子，顶面数字之和为S出现的概率，则：
PN,S=aN,S/6^N
其中aN,S为N个骰子顶面数之和为S的状态的数量，6^N为总的状态数量，因为每个骰子有6种状态，N个骰子组成的状态数就是6^N。
下面给出求ai,j的递推公式，即求i(1=<i<=N)个骰子顶面数之和为j(i=<j<=6*i)时的状态数量：
ai,j= ai-1,j-1 //第i个骰子顶面为1时，其他i-1个骰子顶面数之和为j-1时的状态数量
+ ai-1,j-2 //第i个骰子顶面为2时，其他i-1个骰子顶面数之和为j-2时的状态数量
+ ai-1,j-3 //第i个骰子顶面为3时，其他i-1个骰子顶面数之和为j-3时的状态数量
+ ai-1,j-4 //第i个骰子顶面为4时，其他i-1个骰子顶面数之和为j-4时的状态数量
+ ai-1,j-5 //第i个骰子顶面为5时，其他i-1个骰子顶面数之和为j-5时的状态数量
+ ai-1,j-6 //第i个骰子顶面为6时，其他i-1个骰子顶面数之和为j-6时的状态数量
其中递推公式中i>1。
对于任意的1=<i<=N，j<=0或j<i或j>6*i，ai,j=0。
3）源码：
非递归求解:
#include <iostream>#include <math.h>using namespace std;void PrintSumProbabilityOfDices(unsigned int n) { const unsigned int MAX=12; //max number of dices if(n>MAX) { printf("Overflow!\n"); return; }; unsigned int a[MAX+1][6*MAX+1]; unsigned int i,j,k; memset(a,0,sizeof(a)); /* a[i][j] i代表骰子个数 j代表 i个骰子可能出现的骰子的数量 * */ for(j=1;j<=6;j++)//只有一个骰子的时候，每一个数出现的次数都是 1 a[1][j]=1; for(i=2;i<=n;i++) //第 i个 骰子出现 for(j=i;j<=6*i;j++) //j为所有骰子可以出现的次数 { a[i][j]=0; //初始化要求的 数 for(k=1;k<=6&&k<=j;k++) //k代表 第 i个骰子出现的可能点数 k<=j 说明 不能超过当前所求所有骰子 总点数 a[i][j]+=a[i-1][j-k]; //其他 i-1个骰子 出现j-k 点的次数 } unsigned int nTotal=pow(6,n); for(i=n;i<=6*n;i++) printf("Sum=%d,Probability=%.15lf\n",i,a[n][i]*1.0/nTotal); } int main(){PrintSumProbabilityOfDices(2);}三，把数组排成最小的数。【经典牛逼的题】
1）题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。
例如：输入数组{32, 321}，则输出这两个能排成的最小数字32132。
请给出解决问题的算法，并证明该算法。
2）分析：这是09 年6 月份百度的一道面试题，
思路：根据“字典序”排序，先比较整数中第一个数字，然后再比较第二个，直到所有数都成字典序排列。
【很遗憾】这个是不可行的，比如32的字典序比322小，但是32322比32232大
那该如何是好？
主要是根据题目要求，先排列好顺序，然后按照顺序输出每个数。根据“字典序”排序已经被排除了，那么如何选择排序规则呢？
【巧妙】所以在这里自定义一个比较大小的函数，比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1那个大，如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面。
如果用char *表示字符串，那就可以使用qsort函数进行排序了，我这里用的是string，所以自定义了一个最简单的冒泡排序。
3）源码：
注意，int 转换为 string
#include<iostream>#include<algorithm>#include<string>#include<sstream>using namespace std;int compare1(string str1,string str2)//user defined compare function{string tmp1 = str1.append(str2);string tmp2 = str2.append(str1);if(tmp1.compare(tmp2)>=0)//tmp1 > tmp2 return true;return false;}void sort(string str[],int len)//Bubble sort{for(int i=len;i>0;i--){int exchange=0; for(int j=0;j<i;j++){if(compare1(str[j],str[j+1])){string tmp = str[j];str[j] = str[j+1];str[j+1] = tmp;exchange=1; }if(exchange==0)return; }}}int main(){int num[] = {332,41,322,32,414,4};int len = sizeof(num)/sizeof(int);//string *word = new string[len];string word[len];stringstream sst;for(int i=0;i<len;i++)//convert int to string{sst<<num[i];sst>>word[i];sst.clear(); /*第二种方法 将int 变为 string char *temp; sprintf(temp,"%d",num[i]); string str(temp); word[i]=str; */ /*第三种方法 将 int 变为 string char *temp; itoa(num[i],temp,10); string str(temp); word[i]=str; */ }sort(word,len);//Bubble sort array of string by the rule defined by compare1for(int i=0;i<len;i++){cout<<word[i];}getchar();return 0;}四，旋转数组中的最小元素。
1）题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
2）分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复杂度显然是O(N)。
二分查找法，这道题类似于“在已排序数组，旋转后，再查找某个数”这道题。
中值 > 数组开始 则 在右侧查找 3, 4, 5, 1, 2
中值 < 数组开始 则 在左侧查找（含中值） 4, 5, 1, 2, 3
退出条件：仅仅剩余一个值或者为顺序数组则取最小值
3）源码：
#include <iostream>using namespace std; int helper(int a[], int s, int t) {if (s == t || a[s] < a[t]) return a[s];int m = s + (t-s)/2;if (a[s]>a[m]) //中值小 return helper(a, s, m);else return helper(a, m+1, t);}int main(){int a[]={3,4,5,1,2}; int result=helper(a, 0, 4);cout<<result<<endl; }
下面的源码为自己原始代码，有些地方多考虑了，注意观察
注意:除以2 为右移 1 位
#include<iostream>using namespace std;int GetMinNum(int num[],int begin,int end){if(begin==end ||num[begin]<num[end])return num[begin]; int mid=begin +(end-begin)>>1;if(num[mid]>num[begin]) //右侧 return min(GetMinNum(num,mid+1,end) , num[begin]); else return min(GetMinNum(num,0,mid) , num[mid+1]); }int main(){int num[] = {3,4,5,1,2};int MinNum=GetMinNum(num,0,4); cout<<MinNum<<endl;getchar();return 0;}
五，给出一个函数来输出一个字符串的所有排列。参考
分析：
1） 每个元素依次放到首位，然后对其余元素递归
2） 当当前元素到达末尾的时候，输出该序列
相当于strlen（str）层循环，每层strlen(str)次。
源码一：注意应要使用数组参数char str[]，而不是用变量char *str
注意for 循环，第一个是 s ，就是说从第一个开始交换
#include <iostream>using namespace std;void MySort(char str[],int s,int e){if(s==e) cout<<str<<endl; else{for(int i=s;i<e;++i){swap(str[s],str[i]); MySort(str,s+1,e);swap(str[s],str[i]); } } }int main(){ char str[]="abc"; MySort(str,0,3);return 0;}
扩展：
如果不是求字符的所有排列，而是求字符的所有组合，应该怎么办呢？（P72）
思路：这里不采用交换方式，而是采用删减的方式。采用不同的剔除顺序，并用prex保留删减值，这样将得到所有符合条件的序列
#include <iostream>using namespace std;void MySort(string str,string prex){ string temp=str; cout<<prex<<endl; //注意这里输出 for(int i=0;i<str.length();++i){MySort(str.erase(i,1),prex+str.at(i)); //注意这里处理 str=temp; } }int main(){ string str ="abc"; MySort(str,"");return 0;}