2025年leetcode--两个盒子中球的颜色数相同的概率

leetcode--两个盒子中球的颜色数相同的概率题目是 LeetCode 第 191 场周赛的第四题 链接 1467 两个盒子中球的颜色数相同的概率 具体描述见原题 一种做法是我们先将所有的球都先放到右边盒子里 然后逐渐从右边盒子往左边盒子放球 拿 0 1 balls 0 个第 0 种颜色的球 再拿 0 1 balls 1 个第 1 种颜色的球

大家好,我是讯享网,很高兴认识大家。

 题目是LeetCode第191场周赛的第四题,链接:1467. 两个盒子中球的颜色数相同的概率。具体描述见原题。

 一种做法是我们先将所有的球都先放到右边盒子里,然后逐渐从右边盒子往左边盒子放球(拿0、1...balls[0]个第0种颜色的球,再拿0、1...balls[1]个第1种颜色的球…),当左右盒子的球的数量一样的时候,我们看此时两个盒子里球的颜色数是否一样,一样的话就可以计算一下当下这种左边右边各n个球且有相同颜色数的情况下的排列组合数,以左边为例,假设此时左边球的情况可以用数组L表示,则其可能的排列总数为: N l e f t = n ! ∏ i = 0 n − 1 L [ i ] ! N_{left}=\frac{n!}{\prod_{i=0}^{n-1}L[i]!} Nleft​=∏i=0n−1​L[i]!n!​,分子上是n个球的排列总数,但因为有相同颜色的球,所以会有重复,需要除去相同颜色球的排列,也就是分母所示。右边的排列总数 N r i g h t N_{right} Nright​是类似的,所以就可以得到当前的一个排列总数为 N l e f t × N r i g h t N_{left}\times N_{right} Nleft​×Nright​。

 为了遍历上面所示的从右边盒子拿球到左边盒子的所有情况,就需要用到DFS+回溯了,这里回溯的作用是将之前拿到左边盒子的球拿回到右边盒子。时间复杂度就是 O ( n ∏ i = 1 n − 1 b a l l s [ i ] ) O(n\prod_{i=1}^{n-1}balls[i]) O(n∏i=1n−1​balls[i]),空间复杂度为 O ( n ) O(n) O(n)。


讯享网

 JAVA版代码如下:

class Solution { private int[] right; private int[] left; private int n; private double result; private double[] factorial; private double countOneSide(int[] item) { // 计算左边/右边盒子里球的排列组合数 double res = factorial[n]; for (int i : item) { if (i > 1) { res /= factorial[i]; } } return res; } private int countColor(int[] item) { // 计算盒子里有多少种颜色的球 int res = 0; for (int i : item) { if (i > 0) { ++res; } } return res; } private boolean dfs(int idx, int leftNum) { int leftColor = countColor(left), rightColor = countColor(right); if (leftColor > rightColor || leftNum > n) { // 剪枝 return false; } if (leftNum == n) { // 左边和右边盒子里球的数量已经一样了 if (leftColor == rightColor) { result += countOneSide(left) * countOneSide(right); } // 这里返回false,因为再从右边盒子往左边盒子拿球只能使得左边球的数量大于n return false; } if (idx >= right.length) { return true; } boolean cont = true; // 从右边盒子里中取i个第idx种颜色放到左边盒子里去 for (int i = 0; i <= right[idx] && cont; ++i) { left[idx] += i; right[idx] -= i; cont = dfs(idx + 1, leftNum + i); // 回溯 left[idx] -= i; right[idx] += i; } return true; } public double getProbability(int[] balls) { // 先将所有球放在右边盒子 right = balls; // 左边盒子一开始是空的 left = new int[balls.length]; n = 0; for (int b : balls) { n += b; } factorial = new double[n + 1]; factorial[1] = 1.0; for (int i = 2; i <= n; ++i) { factorial[i] = factorial[i - 1] * i; } n /= 2; result = 0.0; dfs(0, 0); double totalCount = factorial[n * 2]; for (int b : balls) { totalCount /= factorial[b]; } return result / totalCount; } } 

讯享网

 提交结果如下:


小讯
上一篇 2025-04-05 18:30
下一篇 2025-01-10 08:40

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/77449.html