首页 > 试题广场 >

雀魂启动!

[编程题]雀魂启动!
  • 热度指数:16447 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小包最近迷上了一款叫做雀魂的麻将游戏,但是这个游戏规则太复杂,小包玩了几个月了还是输多赢少。
于是生气的小包根据游戏简化了一下规则发明了一种新的麻将,只留下一种花色,并且去除了一些特殊和牌方式(例如七对子等),具体的规则如下:

  1. 总共有36张牌,每张牌是1~9。每个数字4张牌。
  2. 你手里有其中的14张牌,如果这14张牌满足如下条件,即算作和牌
  • 14张牌中有2张相同数字的牌,称为雀头。
  • 除去上述2张牌,剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌(例如234,567等),刻子的意思是相同数字的3个数字牌(例如111,777)

例如:
1 1 1 2 2 2 6 6 6 7 7 7 9 9 可以组成1,2,6,7的4个刻子和9的雀头,可以和牌
1 1 1 1 2 2 3 3 5 6 7 7 8 9 用1做雀头,组123,123,567,789的四个顺子,可以和牌
1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头,都无法组成和牌的条件。

现在,小包从36张牌中抽取了13张牌,他想知道在剩下的23张牌中,再取一张牌,取到哪几种数字牌可以和牌。

输入描述:
输入只有一行,包含13个数字,用空格分隔,每个数字在1~9之间,数据保证同种数字最多出现4次。


输出描述:
输出同样是一行,包含1个或以上的数字。代表他再取到哪些牌可以和牌。若满足条件的有多种牌,请按从小到大的顺序输出。若没有满足条件的牌,请输出一个数字0
示例1

输入

1 1 1 2 2 2 5 5 5 6 6 6 9

输出

9

说明

可以组成1,2,6,7的4个刻子和9的雀头
示例2

输入

1 1 1 1 2 2 3 3 5 6 7 8 9

输出

4 7

说明

用1做雀头,组123,123,567或456,789的四个顺子
示例3

输入

1 1 1 2 2 2 3 3 3 5 7 7 9

输出

0

说明

来任何牌都无法和牌

备注:
请不要根据自己的常识为题目增加未提及的条件

对于20%的数据,保证和牌时一定是4个刻子+雀头的形式
头像 nullHui
发表于 2020-04-22 16:53:14
思路:1 牌组里有13张牌,然后想牌组中添加一张牌(1-9)循环10次,看是否能够胡牌,如果添加的这张牌使某个牌超过四张,失败 2 开始回溯算法:必须是递增的有序序列 2.1首先如果当前牌数不是3的倍数,如果至少前两张牌相同,让这两张牌作为一对,剩余牌进行 展开全文
头像 不想看论文
发表于 2022-03-28 15:52:19
看我的看我的,傻子都能看懂的——java版回溯 用一个card数组存储每张牌出现的次数,然后1 - 9每种大小的牌我们都去尝试三种情况: 比如,当前大小的牌为1 situation 1:把该牌当作雀头,判断剩余的牌是否可胡,如果可以胡,则返回true,如果不可以,则回溯,去判断下一种情况。 situ 展开全文
头像 zj134
发表于 2020-09-28 17:39:47
wo真的很短。。。 一开始思考了好久不知道如何下手,看了大家的评论之后自己整理了一下思路 总体的判断过程是一个dfs的过程: 首先取雀头(排序之后再取) 取完雀头之后,要么取刻子,要么取顺子(都是取三个数),那么取之前需要先判断是否能支持取,比如是否有三个一样的数字或者能够确保取到一个顺子 每取一 展开全文
头像 是猪字名的我念着倒
发表于 2020-08-17 12:17:36
用一个数组input记录1-9的个数先遍历:加入了哪个数字再遍历:哪个数字为雀头之后就是回溯算法了helper(int[] input , int i, int cnt)input:当前状态下数字1-9的个数i:从1到9的顺序来对i进行抉择(数量减3/连续三个数数量减1/什么都不做转而抉择第i+1个 展开全文
头像 17c89
发表于 2024-02-20 12:31:41
import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.util.stream.Collectors; public class Main { private stat 展开全文
头像 Louie.Ye
发表于 2021-03-20 21:49:26
1. 这道题解法很有意思,忘记哪儿看到的了,希望有人告知出处 将所有出的次数用桶的存起来, i从每个数开始遍历尝试,期间嵌套j作为雀头尝试【原本自己思路没有好的方法实现,只能两重循环】 #include<bits/stdc++.h> using namespace std; int 展开全文
头像 ccuteam鹏哥
发表于 2022-08-25 23:31:05
消砖块的思想。采用消砖块思想。先消雀头。再削刻子,再削顺子。削雀头是麻将编号Key对应的Value=Value-2。削刻子的方式是Value=Value-3。削顺子的方式是先取mm=min(Valuek,Valuek+1,Valuek+2),然后Valuei=Valuei-mm。 先把麻将记录 展开全文
头像 追击者732
发表于 2022-02-09 20:56:49
算法 回溯算法(递归) 思路 如果手中的14张牌是能和牌的,那么这14张牌分别参与雀头、顺子、刻子。进一步,把牌分成两部分,遍历牌数大于二的牌,让这些牌作为雀头,对剩下的牌,要么参与顺子的构造,要么参与刻子的构造。 根据这样的分析,分两层回溯算法。 特别的,对于牌数是4的牌,有两种组合方法:这四张 展开全文
头像 大厂算法岗必拿下
发表于 2021-09-20 05:06:52
三层递归。(回溯) 扑克牌转换成hash的方式进行存储,以至于可以从每一个牌进行遍历。 #include<bits/stdc++.h> using namespace std; vector<int> card(9);//统计每个牌出现的次数 bool hasTrib 展开全文
头像 小牛冲冲冲jiang
发表于 2021-09-20 05:50:58
这题太***了有13张牌然后从1到9 添加没有 出现四次的变成14张的完全手牌然后判断 该手牌能否hu能hu 就讲该数字添加到res中 calculate 用来寻找14张牌能否胡 isFindQue 递归寻找 在找到雀头的情况下,剩下的牌能够hu 传递数组列表时应该注意是否接下来的操作会改变数组, 展开全文