題目描述

把n個骰子扔在地上，所有骰子朝上一面的點數(shù)之和為S，輸入n，打印出S的所有可能的值出現(xiàn)的概率。

解析：用兩個數(shù)組來存儲骰子點數(shù)的每一個總數(shù)出現(xiàn)的次數(shù)。在一個循環(huán)中，第一個數(shù)組中的第n個數(shù)字表示骰子和為n出現(xiàn)的次數(shù)，在下一次循環(huán)中，我們加上一個新的骰子，此時和為n的骰子出現(xiàn)的次數(shù)應該等于上一次循環(huán)中骰子點數(shù)和為n-1、n-2、n-3、n-4、n-5與n-6的次數(shù)的總和，所以我們把另一個數(shù)組的第n個數(shù)字設為前一個數(shù)組對應的第n-1、n-2、n-3、n-4、n-5與n-6之和。

#define maxValue 6 class Solution { public: vector<double> PrintProbability(int number){vector<double> v;if(number<=0)return v;int* count[2];//count 從1到maxValue*number分別存和為1到maxValue*number的次數(shù)和count[0]=new int[maxValue*number +1];count[1]=new int[maxValue*number +1];//初始化 for(int i=0;i<maxValue*number +1;i++){count[0][i]=0;count[1][i]=0;}int flag=0;//初始化一顆骰子的情況 for(i=1;i<=maxValue;i++){count[flag][i]=1;}for(int k=2;k<=number;k++){for(i=1;i<k;i++)count[1-flag][i]=0;for(i=k;i<=maxValue*k;i++){count[1-flag][i]=0;for(int j=1;j<=maxValue && j<=i ;j++)count[1-flag][i]+=count[flag][i-j];}flag=1-flag;}double sum=pow((double)maxValue,number);for(i=number;i<=maxValue*number;i++)v.push_back((double)(count[flag][i]/sum));delete count[0];delete count[1];return v;} }

題目描述

LL今天心情特別好,因為他去買了一副撲克牌,發(fā)現(xiàn)里面居然有2個大王,2個小王(一副牌原本是54張^_^)...他隨機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿！！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小 王可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”。LL決定去買體育彩票啦。 現(xiàn)在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運氣如何。為了方便起見,你可以認為大小王是0。

解析：統(tǒng)計0的數(shù)量，與快排后（除0）的牌間差值比較，若出現(xiàn)對子，直接否定

class Solution { public:static int compare(const int s1,const int s2){return s1<s2;}bool IsContinuous( vector<int> numbers ) {if(numbers.size() == 0)return false;sort(numbers.begin(),numbers.end(),compare);int length=numbers.size();int pos=0;int zeroCnt=0;while(numbers[pos]==0){pos++;zeroCnt++;}int dif=0;for(int i=pos;i<length-1;i++){if(numbers[i] == numbers[i+1])//對子return false;dif+=numbers[i+1]-numbers[i]-1;}return dif > zeroCnt?false:true;} };題目描述

每年六一兒童節(jié),NowCoder都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為NowCoder的資深元老,自然也準備了一些小游戲。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,他隨機指定一個數(shù)m,讓編號為1的小朋友開始報數(shù)。每次喊到m的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續(xù)1...m報數(shù)....這樣下去....直到剩下最后一個小朋友,可以不用表演,并且拿到NowCoder名貴的“名偵探柯南”典藏版(名額有限哦!!^_^)。請你試著想下,哪個小朋友會得到這份禮品呢？

解析：（約瑟夫環(huán)）數(shù)學映射：fun（n，m）= （fun（n-1,m) + m ）% n；或者用環(huán)形鏈表做(注意：vector：：erase（）用法)

class Solution { public:int LastRemaining_Solution(unsigned int n, unsigned int m){if(m<1 || n<1)return -1;int fun=0;for(int i=2;i<=n;i++){fun=(fun+m)%i;}return fun;} };
class Solution { public:int LastRemaining_Solution(unsigned int n, unsigned int m){if(m<1 || n<1)return -1;vector<int> v;for(int i=0;i<n;i++){v.push_back(i);}vector<int>::iterator current=v.begin();while(v.size()!=1){for(int i=1;i<m;i++){current++;if(current==v.end())current=v.begin();}current=v.erase(current);if(current==v.end())current=v.begin();}return (*current);} };

總結(jié)

以上是生活随笔為你收集整理的剑指offer 算法 （抽象建模能力）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。