请教一个算法题：摇骰子， 3 个 1 和两个五一个六比， 3 个 1 获胜这种
NicholasZhan · 2021-08-25 15:03:47 +08:00 · 2173 次点击这是一个创建于 1204 天前的主题，其中的信息可能已经有所发展或是发生改变。
楼主今天去面试了，最后的压轴题是： A 和 B 两人摇骰子，一人摇 5 次。要我找出他们俩谁赢了。获胜规则是这样的：相同数字出现最多的获胜，次数相同则数字大的获胜。例如：A 出了 6 个 1，B 出了 5 个 6 和 1 个 5，则 A 获胜。楼主的思路是先统计每人每个数字出现次数，然后按照出现次数和数字本身降序排列。排序规则是这样的，出现次数多的大，次数相同则比较数字。这样就能比较出胜负了。
没想到的是，面试官突然把题目升级了：假设有 5000 个人，每个骰子有 5000 个面，每个人摇 5000 次，还是一样的规则，让我找出获胜者😢。原来的算法肯定是不行的，面试官给的提示是如何遍历一遍就给每个人打个分，然后比较分数，我只想到了权重，出现次数越多权重越大。但是具体的算法还是没能设计出来，听闻 V 站大佬多，特来请教下 ORZ 。
 |
1
cpstar 2021-08-25 15:05:20 +08:00
8 进制比特位，不知道行不行，LZ 试试
|
 |
2
wy315700 2021-08-25 15:05:23 +08:00
5000 进制
|
|
3
cpstar 2021-08-25 15:10:36 +08:00
5000 个面啊。。。删除我 1 楼的话
|
 |
4
xloger 2021-08-25 15:10:55 +08:00
上班摸鱼中，没仔细看题啊，“遍历一遍就给每个人打个分”，如你所说权重，那意思是比如没重复的就是正常分数，重复一次的就是正常分数*5000，重复两次就是正常分数*5000*2 的这个思路？计算一个数，这个数是重复 N 的最小值能大于重复 N-1 的最大值的，把这个设为权重，那重复次数多分数一定高于次数低的。
好，我继续去工作了...大佬们加油！ |
|
5
cpstar 2021-08-25 15:13:24 +08:00
但是从取最大的算法看，确实只遍历一次足以。只不过每次遍历，需要比较的东西太多。
反正不是排序算法，不用考虑如何把 O(n^2)降到 O(nlogn)之类的 |
 |
6
binux 2021-08-25 15:21:30 +08:00 via Android
就是取最大，最多就是自定义一个比较算法罢了。
|
 |
7
shpkng 2021-08-25 15:22:36 +08:00
存个当前最佳结果(点数和次数)和当前最高玩家的 id,
for 5000 遍历所有玩家, 每次循环里模拟投骰子, 循环完和当前最大值比, 这样就是一次循环, 你的解法里存每个人的数据再去排序是没意义的, 直接留最大的那个就好了, 因为题目的要求只是得到一个胜者 |
 |
8
bfdh 2021-08-25 15:24:08 +08:00  1
66654 和 66611 谁胜？
前者胜的话，确实遍历一次就行；后者胜的话，我再想想。 |
 |
9
NicholasZhan OP @bfdh 后者胜
|
|
10
NicholasZhan OP 规则有点像我们斗地主中的炸弹，相同的牌越多，威力越大。大的抵消了，再看第二大的炸弹，以此类推
|
 |
11
misdake 2021-08-25 15:35:57 +08:00
先按照第一段那样统计每个人的结果，得到有序的(次数,数字)列表，把这个列表看作字符串，这个字符串就是得分，或者把他编码成一个 5000 进制的数字，每一位依次是(次数 1, 数字 1, 次数 2, 数字 2, ..., 次数 n, 数字 n, ...)。后面没有了就填 0 。
然后写一个“字符串”比较或者这个 5000 进制数字比较的函数，然后根据需求进行排序或者取最大。 |
|
12
cpstar 2021-08-25 15:37:00 +08:00
sum[5000][5000]=0//全都清零，第一维为人，第二维为骰子结果
maxp=0//最大的人 maxr=0//最大的骰子结果 maxs=0//最大的骰子技术 for (ppl=1..5000) {//遍历人 for (times=1..5000) {//遍历次数 sum[ppl][result]++//result 为当此骰子结果 if(sum[ppl][result]>maxs||(sum[ppl][result]=maxs&&result>maxr)) {//次数超，或者次数相等结果超 maxp=ppl;maxr=result;maxs=sum[ppl][result]; } } } |
 |
14
tyx1703 2021-08-25 16:34:43 +08:00 via iPhone
同 2 楼，n 进制解决
6 面骰子的权重：6^0 * S_1 + 6^1 * S_2 + … + 6^5 * S_6，其中 S_n 为 出现 n 次的点数的和 66654: (6+6+6) * 6^5 + (5+4) * 6^0 66611: (6+6+6) * 6^5 + (1+1) * 6^1 |
 |
15
zmxnv123 2021-08-25 16:46:45 +08:00
如果 A > B & B > C => A > C，我理解取最大肯定是一个 O(n)算法
|
|
16
NicholasZhan OP @tyx1703 老哥你有考虑过幂运算的溢出问题吗😂
|
|
17
cpstar 2021-08-25 17:33:32 +08:00
@tyx1703 14# @NicholasZhan 16# 溢出还不算事，两个 6 四个 5 要赢于三个 6 三个 5 的。
另外 14#的算法写错了吧，没看懂 66654 不应该是 6*3*6^5+5*6^4+4*6^3 么 66611 不应该是 6*3*6^5+1*2*6^0 么？ 如果是这样的话， A:665555: 6*2*6^5+5*4*6^4=119232 B:666555: 6*3*6^5+5*3*6^4=159408 这就错了， |
 |
18
lin07hui 2021-08-25 17:54:51 +08:00
权重：5000 * (数量 - 1) * 骰子值 + 骰子值
|
|
20
tyx1703 2021-08-25 18:02:55 +08:00 via iPhone
@NicholasZhan 这只是举个计算的例子，高进制所有位的值保存在数组中，按位比较
@cpstar 写错了，应该是 (6+6+6) * 6^2 + (1+1) * 6^1 665555: 6 出现 2 次，放在第 2 位； 5 出现 4 次，放在第 4 位 5*4*6^3 + 6*2*6^1 666555: 6 出现 3 次，放在第 3 位； 5 出现 3 次，放在第 3 位 (6*3 + 5*3) * 6^2 |
 |
23
wangyongbo 2021-08-25 18:34:59 +08:00
leetcode 上有这道题目吗？
|
|
24
NicholasZhan OP |
|
25
NicholasZhan OP @wangyongbo 貌似没有哦😂
|
 |
26
cctrv 2021-08-26 01:22:00 +08:00 via iPhone
這種當然做製表啊！
把 111111 - 666666 的組合先窮盡然後按勝利到輸做一個表。 5000 人全部查表就好了。 |
|
27
cctrv 2021-08-26 01:23:39 +08:00 via iPhone
不好意思，5000 面⋯看漏了
|
|
28
lin07hui 2021-08-26 10:40:45 +08:00
|
|
29
lin07hui 2021-08-26 10:42:27 +08:00
|
 |
31
bdataby11 2021-08-30 14:21:30 +08:00
假设有 5000 个人，每个骰子有 5000 个面（每一面的点数是 1-5000 ），每个人摇 5000 次；获胜规则是这样的：相同数字出现最多的获胜，次数相同则数字大的获胜。
1.把每个人摇五千次的结果先做内部排序，统计出每个数字出现的次数，最后只要记录每个人的相同次数出现最多的数字以及其次数，5 千个人就是 5 千行结果。 2.针对次数对 5 千行结果做排序，找到次数最大的值。如果次数最大的结果有多个，再选出次数最大的 |
|
32
bdataby11 2021-08-30 14:23:07 +08:00
假设有 5000 个人，每个骰子有 5000 个面（每一面的点数是 1-5000 ），每个人摇 5000 次；获胜规则是这样的：相同数字出现最多的获胜，次数相同则数字大的获胜。
1.把每个人摇五千次的结果先做内部排序，统计出每个数字出现的次数，最后只要记录每个人的相同次数出现最多的数字以及其次数（如第五个人 数字 1500 次数 225 ），5 千个人就是 5 千行结果。 2.针对次数对 5 千行结果做排序，找到次数最大的值。如果次数最大的结果有多个，再选出次数最大的 |
|
33
bdataby11 2021-08-30 14:47:42 +08:00
假设有 5000 个人，每个骰子有 5000 个面（每一面的点数是 1-5000 ），每个人摇 5000 次；获胜规则是这样的：相同数字出现最多的获胜，次数相同则数字大的获胜。
1.把每个人摇五千次的结果先做内部排序，统计出每个数字出现的次数，最后只要记录每个人的相同次数出现最多的数字以及其次数（如第五个人 数字 1500 次数 225 ），5 千个人就是 5 千行结果。 2.针对次数对 5 千行结果做排序，找到次数最大的值。如果次数最大的结果有多个，再选出次数最大的 答主有些情况都没说明，每个骰子有 5000 个面，那它每一面的点数如果范围是 1-6，那是没有意义的，应该是 1-5000 比较合理。 还有个问题要考虑到，比如最终结果为[数字 1500 次数 300]的人数有两个人 a b 这时候就得取 a b 两个的 top2 做规则 [相同数字出现最多的获胜，次数相同则数字大的获胜] 比较，如果 ab 的 top2 都相等，要继续比较 top3 top4 ...topn 等等。 最最最极端的情况，5000 个人的 top1 和 topn 都相等 @NicholasZhan 大佬说的斗地主中的炸弹就差不多，我刚开始只考虑到 top1 的情况，但是如果 top1 相等的有多个，就要继续往下比较了。 |
|
34
NicholasZhan OP @bdataby11 嗯，是我漏了条件，5000 面的骰子点数是 1-5000，感谢指出
|
Select Language