剑指 Offer 60 n个骰子的点数

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-27 22:50:11
    编辑于：2022-02-27 23:02:02
    浏览量：688

概述

https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/

暴力解

使用一个哈希表记录当前各个值的可能，之后新加入一个骰子更新新的概率。

笑死，随便写写没打算过结果过了（而且竟然 beat 100%，这是暴力解啊喂）：

class Solution {
public:
    vector<double> dicesProbability(int n) {
        unordered_map<int, double> m;
        for (int i = 1; i <= 6; i ++) m[i] = double(1) / 6;
        for (int i = 2; i <= n; i ++) {
            unordered_map<int, double> newM;
            for (int j = 1; j <= 6; j ++) {
                for (auto iter = m.begin(); iter != m.end(); iter ++) {
                    newM[iter->first + j] += m[iter->first] / 6;
                }
            }
            m = newM;
        }
        vector<pair<int, double>> l;
        for (auto iter = m.begin(); iter != m.end(); iter ++) l.push_back({iter->first, iter->second});
        sort(l.begin(), l.end());
        vector<double> ans;
        for (auto& p : l) ans.push_back(p.second);
        return ans;
    }
};

时间复杂度 O(n^2)。

看了《剑指 Offer》，他上面也是暴力解。。。

Links: sword-offer-60