AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

P3810. 数字排列

中等通过率 36% · 提交 513 · 通过 184
回溯DFS排序数学

小慕在筹备团队的年会活动,设计了一个趣味游戏: 屏幕上会显示 1 到 9 中任意 4 个不重复的数字,参与者需要尽快找出这些数字能拼成的所有数字中,从小到大排列位于第 N 位的那个数字,其中 N 等于屏幕上给出的数字中最大的那个(如果拼出的数字总数不到 N 个,则取最后一个数字即可)。 注意: - 数字 进行数字拼接,且屏幕上不会同时出现 2 和 5; - 数字 6 可以当作 9 来使用,9 也可以当作 6 来使用进行数字拼接,且屏幕上不会同时出现 6 和 9。 例如,屏幕上给出:1,4,8,7,则可以拼接出的数字依次为: > 1,4,7,8,14,17,18,41,47,48,71,74,78,81,84,87,147,148,178 …(后续数字省略)。那么第 N(即8)个数字是 41。

提示:带虚线的词点一下有通俗解释。

输入描述

输入以逗号分隔的 4 个 int 类型整数的字符串。

输出描述

输出为这几个数字可拼成的数字从小到大排列位于第 N (N为输入数字中最大的数字)位置的数字, 如果输入的数字不在范围内或者有重复,则输出-1。

示例

示例 1

输入

1,4,8,7

输出

41

说明:可以构成的数字按从小到大排序为: 1,4,7,8,14,17,18,41,47,48,71,74,78,81,84,87,147,148,178 … (省略后面的数字), 故第8个为41

示例 2

输入

2,5,1,4

输出

-1

说明:2和5不能同时出现

示例 3

输入

3,0,9,5

输出

-1

说明:0不在1到9范围内

示例 4

输入

3,9,7,8

输出

39

说明:注意9可以当6使用,所以可以构成的数字按从小到大排序为:3,6,7,8,9,36,37,38,39,63,67,68,73,76,78,79,83 … (省略后面的数字)。故第9个为39

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解
数字排列 - 核心思路图解 输入: 1,4,8,7 2↔5, 6↔9 可互换 (本题无2,5,6,9) 生成所有排列 (1位,2位,3位,4位) 排序后的序列(部分) 1, 4, 7, 8, 14, 17, 18, 41, 47, 48, 71, 74, 78, 81, 84, 87, 147, 148, 178, ... N = 最大数字 = 8 第8个 = 41 输出: 41 异常: 重复/范围外 输出 -1
写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「数字排列」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。