LintCode : Dices Sum 骰子求和

悠悠 2021-06-24 16:10 490阅读 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 条评论，490人围观）

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

相关阅读

相关 lintcode206. 区间求和 I 线段树

给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模），以及一个查询列表。每一个查询列表有两个整数 \[start, end\] 。对于每个查询，计算出数组中从

柔光的暖阳◎/ 2023年07月06日 13:29/ 0 赞/ 30 阅读

相关 lintcode402. 连续子数组求和

给定一个整数数组，请找出一个连续子数组，使得该子数组的和最大。输出答案时，请分别返回第一个数字和最后一个数字的下标。（如果存在多个答案，请返回字典序最小的）样例

末蓝、/ 2023年07月04日 06:14/ 0 赞/ 21 阅读

相关 Leetcode-1155 Number of Dice Rolls With Target Sum(掷骰子的N种方法)

dp\[i\]\[j\]表示前i个骰子到达数字总和j的方案数 dp\[i\]\[j\] = Σdp\[i-1\]\[j-k\]，其中k是一个骰子能掷出的范围 1 d

「爱情、让人受尽委屈。」/ 2023年06月01日 08:47/ 0 赞/ 24 阅读

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

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

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

相关 case when求和用SUM

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

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

相关 3个骰子求和

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

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

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

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

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

相关 [HEOI2016]求和 sum

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

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

相关 LintCode: Combination Sum

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

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

相关 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 赞/ 491 阅读