LintCode : Dices Sum 骰子求和

悠悠 2021-06-24 16:10 405阅读 0赞

**试题：**  
Throw n dices, the sum of the dices’ faces is S. Given n, find the all possible value of S along with its probability.

Example  
Example 1:

Input: n = 1  
Output: \[\[1, 0.17\], \[2, 0.17\], \[3, 0.17\], \[4, 0.17\], \[5, 0.17\], \[6, 0.17\]\]  
Explanation: Throw a dice, the sum of the numbers facing up may be 1, 2, 3, 4, 5, 6, and the probability of each result is 0.17.  
Notice  
You do not care about the accuracy of the result, we will help you to output results.  
**代码：**  
有三个未知数：扔骰子次数，在当前次数上和的取值范围，当前次扔骰子可能出现的点数。

public class Solution {
        /**
         * @param n an integer
         * @return a list of Map.Entry<sum, probability>
         */
        public List<Map.Entry<Integer, Double>> dicesSum(int n) {
            // Write your code here
            // Ps. new AbstractMap.SimpleEntry<Integer, Double>(sum, pro)
            // to create the pair
            long[][] dp = new long[n+1][6*n+1];
            for(int i=1; i<=6; i++){
                dp[1][i] = 1;
            }
            
            for(int i=2; i<=n; i++){
                for(int j=i; j<=6*i; j++){
                    for(int k=1; k<=6&&k<=j; k++){
                        dp[i][j] = dp[i][j] + dp[i-1][j-k];
                    }
                }
            }
            
            double total = Math.pow(6,n);
            HashMap map = new HashMap<Integer,Double>();
            for(int i=n; i<=6*n; i++){
                map.put(i,dp[n][i]/total);
            }
            
            return new ArrayList<Map.Entry<Integer,Double>>(map.entrySet());
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，405人围观）

还没有评论，来说两句吧...

相关阅读

相关【LintCode 简单】167. 链表求和

1.问题描述：你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中`相反`的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形

浅浅的花香味﹌/ 2022年11月28日 13:28/ 0 赞/ 77 阅读

相关 case when求和用SUM

SELECT CITY, COUNT( ) ins, SUM( CASE WHEN OUT_TIME IS NOT NULL THEN

我就是我/ 2022年10月27日 13:59/ 0 赞/ 188 阅读

相关 Elasticsearch根据查询条件求和sum

一、概述现有news表，数据存放在Elasticsearch中。需要根据关键字查询之后，sum计算点击数。数据如下： { "conten

缺乏、安全感/ 2022年10月13日 12:45/ 0 赞/ 179 阅读

相关 3个骰子求和

给定一个整数，3至18，求3个骰子累加之和为这个整数，打印出这三个骰子各自显示的数 // 3RandomSum.cpp : 定义控制台应用程序的入口点。

超、凢脫俗/ 2022年08月18日 00:42/ 0 赞/ 149 阅读

相关避免mybatis SUM求和返回null

<select id="getOrderSumMoneyByUserCode" parameterType="string" resultType="bigD

女爷i/ 2022年06月09日 08:24/ 0 赞/ 258 阅读

相关 EOS骰子游戏dice.cpp程序源码

/ @file @copyright defined in eos/LICENSE.txt / include <util

矫情吗；*/ 2022年05月08日 01:20/ 0 赞/ 170 阅读

相关 [LintCode] Continuous Subarray Sum 连续子数组之和

Given an integer array, find a continuous subarray where the sum of numbers is the bigge

短命女/ 2022年02月01日 09:15/ 0 赞/ 138 阅读

相关 [HEOI2016]求和 sum

\[HEOI2016\]求和 sum 标签： NTT cdq分治多项式求逆第二类斯特林数 -------------------- Description

忘是亡心i/ 2021年09月29日 10:54/ 0 赞/ 245 阅读

相关 LintCode: Combination Sum

一个数可以使用多次图：　　节点：x（当前的和，当前要考虑的数a\[i\]）　　边：x-> 　　　　y1（当前的和，下一个要考虑的数a\[i+1\]）　　　　y

清疚/ 2021年09月19日 09:46/ 0 赞/ 163 阅读

相关 LintCode : Dices Sum 骰子求和

试题： Throw n dices, the sum of the dices’ faces is S. Given n, find the all possible va

悠悠/ 2021年06月24日 16:10/ 0 赞/ 406 阅读