[数据结构与算法][题解]《算法零基础100讲》(第30讲) 概率与统计

1227. 飞机座位分配概率

数学

一分钟ac给我搞懵了…在求出来n=3是的概率是0.5时直接猜结论比一大答案就都是0.5，然后自己也没有想到就过了…

太草率了！我们来简单理解一波。假设总共有n个人，第一个人的选择无非就是两种：在自己的座位上和不在自己的座位上。显然，第一种情况的概率是$\frac{1}{n}$,而且根据题目的描述，只要第一个人选择的是自己的座位，后面的人都只能选择自己的座位。然后分析第一个人不在自己座位上的情况，假设第一个人做到了第m个位置上，那么$2\backsim m?1$的人就都一定坐到了自己的座位上，对第m个人来说，他如果坐在了1的位置上，那么后面就又都坐在了自己的座位上，所以就可以把1的位置当成是m的位置，然后就变成了一个缩小的原问题，这样就能找到递推关系。求出来n=2时概率为0.5就很容易发现由于递推关系所以n>2时的概率都一定是0.5

class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        if(n==1) return 1;
        return 0.5;
    }
};

LCP 11. 期望个数统计

数学

题目超唬人，其实并不难系列。求两个下降序列相同的期望有多大，因为是下降的序列，所以出现一次的元素位置一定是固定的。对于出现多次的元素，全排列以后某一种排列出现的期望是1，所以其实就是求去重以后数组的元素数

class Solution {
public:
    int expectNumber(vector<int>& scores) {
        sort(scores.begin(),scores.end());
        scores.erase(unique(scores.begin(),scores.end()),scores.end());
        return scores.size();
    }
};

470. 用 Rand7() 实现 Rand10()

拒绝采样

先来想想用rand7()来实现rand5()怎么实现。rand7()保证了出现1~7的概率都是$\frac{1}{7}$，而rand5()需要保证的是出现1 ~ 5的可能性是相等的,那么我们就可以在出现6，7的时候继续计算（拒绝出现67）这样就可以使出现1~5的概率都是$\frac{1}{7}$，实现了等可能性。凡是我们这里是1 ~ 7来使1 ~10等可能性，样本容量变大了所以无法直接用拒绝样本的方法来求。但是我们可以组合一下，一个等概率事件加上另一个等概率事件每一种情况发生的概率肯定还是相等的，于是我们可以$rand2()?5+rand5()$

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int t,v;
        while((t=rand7())>5);
        while((v=rand7())==7);
        return v%2*5+t; 
    }
};

1093. 大样本统计

两遍模拟

这道题的中位数还是有一点恶心的

class Solution {
public:
    vector<double> sampleStats(vector<int>& count) {
        vector<double>res;
        double sum=0,cnt=0,minn=255,maxn=0,st=0,num=0;
        for(double i=0;i<256;i++){
            if(count[i]){
                sum+=i*count[i],cnt+=count[i];
                minn=min(minn,i),maxn=max(maxn,i);
                if(count[i]>st) st=count[i],num=i;
            }
        }
        double mid=0;
        int sm=0;
        for (int i=0;i<256;i++) {
            sm+=count[i];
            if (sm*2>cnt) {
                mid=i;
                break;
            } else if(sm*2==cnt) {
                for(int j=i+1;j<256;j++) {
                    if (count[j] != 0) {
                        mid=(i+j)/2.0;
                        break;
                    }
                }
                break;
            }
        }
        return {minn,maxn,sum/cnt,mid,num};
    }
};

剑指 Offer 60. n个骰子的点数

动态规划

先考虑n枚骰子的情况可能出现的点数，有n枚骰子都是1和是n，最大的就是两枚骰子都是6，和是$6n$中间的数字当然也有可能啦。n枚骰子和出现m就是n-1枚骰子和是m-1,m-2,…,m-6的概率加起来乘上$\frac{1}{6}$

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double>ans;
        double dp[15][1000]={0};
        for(int i=1;i<=6;i++) dp[1][i]=1/6.0;
        for(int i=2;i<=n;i++)
            for(int j=i;j<=6*i;j++){
                for(int v=1;v<=6&&j>v;v++)
                    dp[i][j]+=dp[i-1][j-v];
                dp[i][j]*=1/6.0;
            }
        for(int i=n;i<=6*n;i++) ans.push_back(dp[n][i]);
        return ans;
    }
};