剑指offer 算法 （抽象建模能力）

题目描述

把n个骰子扔在地上，所有骰子朝上一面的点数之和为S，输入n，打印出S的所有可能的值出现的概率。

解析：用两个数组来存储骰子点数的每一个总数出现的次数。在一个循环中，第一个数组中的第n个数字表示骰子和为n出现的次数，在下一次循环中，我们加上一个新的骰子，此时和为n的骰子出现的次数应该等于上一次循环中骰子点数和为n-1、n-2、n-3、n-4、n-5与n-6的次数的总和，所以我们把另一个数组的第n个数字设为前一个数组对应的第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的次数和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今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。

解析：统计0的数量，与快排后（除0）的牌间差值比较，若出现对子，直接否定

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;} };题目描述

每年六一儿童节,NowCoder都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为NowCoder的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为1的小朋友开始报数。每次喊到m的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续1...m报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到NowCoder名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？

解析：（约瑟夫环）数学映射：fun（n，m）= （fun（n-1,m) + m ）% 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);} };

总结

以上是生活随笔为你收集整理的剑指offer 算法 （抽象建模能力）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。