剑指 Offer 60 n个骰子的点数

Tag: 剑指-Offer Posted on 2022-02-27 22:50:11 Edited on 2022-02-27 23:02:02 Views: 306

概述

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》,他上面也是暴力解。。。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/