LintCode——筛子求和
2024-04-05 23:29:04
描述：扔n个骰子，向上面的数字之和为 S 。给定 Given n，请列出所有可能的 S 值及其相应的概率。
样例：给定n=1，返回 [ [1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]
解题思路：假定有n个骰子，那么可投掷出的数字在n~6n之间，即S的取指在n~6n之间，n个骰子投掷会出现6的n次方种情况；我们采用递归思想，求n个骰子投出num的情况数的时，需要递归求n-1个骰子投出num-1,num-2,num-3...num-6的情况，而求n-1个骰子投出num-1的情况数的时候，需要递归求n-2个骰子投出num-2,num-3,num-4...，num-12的情况；依次类推，其中会有重复求解的过程，为了优化算法，我们采用动态规划技术来减少不必要的重复求解过程。使用HashMap<string,double>来存储已经计算好的情况数。这里String作为键，用以标记“x个骰子投出y”，值Double为情况数。
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
List<Map.Entry<Integer, Double>> list = new ArrayList<Map.Entry<Integer,Double>>(5 * n + 1);
Double pro = 0.0;
double total = Math.pow(6, n);
double conditions = 0;
HashMap<String,Double> hashMap = new HashMap<>();
for(int i = n;i <= 6 * n;i++){
pro = 0.0;
conditions = findCombs(i, n,hashMap);
pro = conditions / total;
list.add(new AbstractMap.SimpleEntry<Integer, Double>(i,pro));
}
return list;
}
public static double findCombs(int num,int n,HashMap<String, Double>hashMap){
//为了简化计算，假设每个骰子最小值为0，最大值为5，共n个骰子
double total = 0;
String key = String.valueOf(num) + "," + String.valueOf(n);
if(hashMap.containsKey(key)){//若前面已经计算过该状态则直接返回结果
return hashMap.get(key);
}
if(num <= 0){
if(n >= 1)
total = 0;
else
total = 1;//0 个骰子得到0 是可以的
}
else{
//num >0
if(n < 1){
total = 0;
}
else if(n == 1){
if(num > 6)
total = 0;
else
total = 1;
}
else{
int ceil = num <= 6 ? num : 6;
for(int i = 1;i <= ceil;i++){
total += findCombs(num-i, n-1,hashMap);
}
}
}
hashMap.put(key, total);
return total;
}
}
最新文章
- 利用Python进行数据分析(14) pandas基础: 数据转换
- C# Azure 存储-分布式缓存Redis工具类 RedisHelper
- checking for tgetent()... configure: error: NOT FOUND!
- Map/Reduce 工作机制分析 --- 作业的执行流程
- 阿里 classloader
- JS 生成26个大小写字母
- 如何下载某些 flash 在线视频 并使用ffmpeg下载分段并加密的m3u8视频流
- dedecms 使noflag参数及其过滤多个属性的修改方法
- linux0.12 链接过程
- 阿里巴巴Java开发手册思维导图
- springMVC 实现redis分布式锁
- 来了，老弟!__二进制部署kubernetes1.11.7集群
- 编程语言吐槽之Java与C
- 27.MySQL备份与恢复
- lintcode-401-排序矩阵中的从小到大第k个数
- C 类网络的子网快速划分
- ACM -- 算法小结（八）字符串算法之Manacher算法
- Spring3X升级到Spring4X时，出现的问题
- EZOJ #227
- java时间操作工具类