V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
NicholasZhan
V2EX  ›  问与答

请教一个算法题:摇骰子, 3 个 1 和两个五一个六比, 3 个 1 获胜这种

  •  
  •   NicholasZhan · 102 天前 · 1371 次点击
    这是一个创建于 102 天前的主题,其中的信息可能已经有所发展或是发生改变。

    楼主今天去面试了,最后的压轴题是: A 和 B 两人摇骰子,一人摇 5 次。要我找出他们俩谁赢了。获胜规则是这样的:相同数字出现最多的获胜,次数相同则数字大的获胜。例如:A 出了 6 个 1,B 出了 5 个 6 和 1 个 5,则 A 获胜。楼主的思路是先统计每人每个数字出现次数,然后按照出现次数和数字本身降序排列。排序规则是这样的,出现次数多的大,次数相同则比较数字。这样就能比较出胜负了。

    没想到的是,面试官突然把题目升级了:假设有 5000 个人,每个骰子有 5000 个面,每个人摇 5000 次,还是一样的规则,让我找出获胜者😢。原来的算法肯定是不行的,面试官给的提示是如何遍历一遍就给每个人打个分,然后比较分数,我只想到了权重,出现次数越多权重越大。但是具体的算法还是没能设计出来,听闻 V 站大佬多,特来请教下 ORZ 。

    34 条回复    2021-08-30 16:13:38 +08:00
    cpstar
        1
    cpstar  
       102 天前
    8 进制比特位,不知道行不行,LZ 试试
    wy315700
        2
    wy315700  
       102 天前
    5000 进制
    cpstar
        3
    cpstar  
       102 天前
    5000 个面啊。。。删除我 1 楼的话
    xloger
        4
    xloger  
       102 天前
    上班摸鱼中,没仔细看题啊,“遍历一遍就给每个人打个分”,如你所说权重,那意思是比如没重复的就是正常分数,重复一次的就是正常分数*5000,重复两次就是正常分数*5000*2 的这个思路?计算一个数,这个数是重复 N 的最小值能大于重复 N-1 的最大值的,把这个设为权重,那重复次数多分数一定高于次数低的。
    好,我继续去工作了...大佬们加油!
    cpstar
        5
    cpstar  
       102 天前
    但是从取最大的算法看,确实只遍历一次足以。只不过每次遍历,需要比较的东西太多。
    反正不是排序算法,不用考虑如何把 O(n^2)降到 O(nlogn)之类的
    binux
        6
    binux  
       102 天前 via Android
    就是取最大,最多就是自定义一个比较算法罢了。
    shpkng
        7
    shpkng  
       102 天前
    存个当前最佳结果(点数和次数)和当前最高玩家的 id,
    for 5000 遍历所有玩家,
    每次循环里模拟投骰子,
    循环完和当前最大值比,

    这样就是一次循环, 你的解法里存每个人的数据再去排序是没意义的, 直接留最大的那个就好了, 因为题目的要求只是得到一个胜者
    bfdh
        8
    bfdh  
       102 天前   ❤️ 1
    66654 和 66611 谁胜?
    前者胜的话,确实遍历一次就行;后者胜的话,我再想想。
    NicholasZhan
        9
    NicholasZhan  
    OP
       102 天前
    @bfdh 后者胜
    NicholasZhan
        10
    NicholasZhan  
    OP
       102 天前
    规则有点像我们斗地主中的炸弹,相同的牌越多,威力越大。大的抵消了,再看第二大的炸弹,以此类推
    misdake
        11
    misdake  
       102 天前
    先按照第一段那样统计每个人的结果,得到有序的(次数,数字)列表,把这个列表看作字符串,这个字符串就是得分,或者把他编码成一个 5000 进制的数字,每一位依次是(次数 1, 数字 1, 次数 2, 数字 2, ..., 次数 n, 数字 n, ...)。后面没有了就填 0 。
    然后写一个“字符串”比较或者这个 5000 进制数字比较的函数,然后根据需求进行排序或者取最大。
    cpstar
        12
    cpstar  
       102 天前
    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];
    }
    }
    }
    cpstar
        13
    cpstar  
       102 天前
    @cpstar 12# 的方法解决不了 8#。
    8#的问题已经涉及排序了。
    tyx1703
        14
    tyx1703  
       102 天前 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
    zmxnv123
        15
    zmxnv123  
       102 天前
    如果 A > B & B > C => A > C,我理解取最大肯定是一个 O(n)算法
    NicholasZhan
        16
    NicholasZhan  
    OP
       102 天前
    @tyx1703 老哥你有考虑过幂运算的溢出问题吗😂
    cpstar
        17
    cpstar  
       102 天前
    @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
    这就错了,
    lin07hui
        18
    lin07hui  
       102 天前
    权重:5000 * (数量 - 1) * 骰子值 + 骰子值
    lin07hui
        19
    lin07hui  
       102 天前
    @lin07hui 18# 权重:5000 * (数量 - 1) + 骰子值
    tyx1703
        20
    tyx1703  
       102 天前 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
    Encloud
        21
    Encloud  
       102 天前
    @tyx1703 每人摇 5000 次的话,极端情况就会有 5000 位的超大数
    tyx1703
        22
    tyx1703  
       102 天前 via iPhone
    @Encloud 按位放在数组中
    wangyongbo
        23
    wangyongbo  
       102 天前
    leetcode 上有这道题目吗?
    NicholasZhan
        24
    NicholasZhan  
    OP
       102 天前
    @cpstar
    @wy315700
    @xloger
    @binux
    @shpkng
    @bfdh
    @misdake
    @tyx1703
    @zmxnv123
    @lin07hui
    @Encloud
    @tyx1703 感谢大家的热情解答,进制的解法真的很棒👍
    NicholasZhan
        25
    NicholasZhan  
    OP
       102 天前
    @wangyongbo 貌似没有哦😂
    cctrv
        26
    cctrv  
       102 天前 via iPhone
    這種當然做製表啊!

    把 111111 - 666666 的組合先窮盡然後按勝利到輸做一個表。

    5000 人全部查表就好了。
    cctrv
        27
    cctrv  
       102 天前 via iPhone
    不好意思,5000 面⋯看漏了
    lin07hui
        28
    lin07hui  
       101 天前
    @tyx1703
    66641: (6+6+6) * 6^5 + (4+1) * 6^0
    66631: (6+6+6) * 6^5 + (3+2) * 6^0
    这两个相等了,应该是 66641 赢才对
    lin07hui
        29
    lin07hui  
       101 天前
    @tyx1703
    66641: (6+6+6) * 6^5 + (4+1) * 6^0
    66632: (6+6+6) * 6^5 + (3+2) * 6^0
    这两个相等了,应该是 66641 赢才对
    tyx1703
        30
    tyx1703  
       101 天前 via iPhone
    @lin07hui 确实考虑不周,直接加还是有问题
    bdataby11
        31
    bdataby11  
       97 天前
    假设有 5000 个人,每个骰子有 5000 个面(每一面的点数是 1-5000 ),每个人摇 5000 次;获胜规则是这样的:相同数字出现最多的获胜,次数相同则数字大的获胜。
    1.把每个人摇五千次的结果先做内部排序,统计出每个数字出现的次数,最后只要记录每个人的相同次数出现最多的数字以及其次数,5 千个人就是 5 千行结果。
    2.针对次数对 5 千行结果做排序,找到次数最大的值。如果次数最大的结果有多个,再选出次数最大的
    bdataby11
        32
    bdataby11  
       97 天前
    假设有 5000 个人,每个骰子有 5000 个面(每一面的点数是 1-5000 ),每个人摇 5000 次;获胜规则是这样的:相同数字出现最多的获胜,次数相同则数字大的获胜。
    1.把每个人摇五千次的结果先做内部排序,统计出每个数字出现的次数,最后只要记录每个人的相同次数出现最多的数字以及其次数(如第五个人 数字 1500 次数 225 ),5 千个人就是 5 千行结果。
    2.针对次数对 5 千行结果做排序,找到次数最大的值。如果次数最大的结果有多个,再选出次数最大的
    bdataby11
        33
    bdataby11  
       97 天前
    假设有 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 相等的有多个,就要继续往下比较了。
    NicholasZhan
        34
    NicholasZhan  
    OP
       97 天前
    @bdataby11 嗯,是我漏了条件,5000 面的骰子点数是 1-5000,感谢指出
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1181 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 18:04 · PVG 02:04 · LAX 10:04 · JFK 13:04
    ♥ Do have faith in what you're doing.