解题思路
本题的关键是:每个参与者只按照初始队列顺序处理一次,并且移动到队首或队尾的人,其相对顺序要和初始队列保持一致。
因此不需要真的在链表中反复移动节点,可以使用分组模拟 + 顺序拼接的方法。
按照规则优先级处理每个节点:
- 如果号码不在
[0, 10^9] 范围内,直接返回 "-1"。
P14388.链表数字游戏(100分)
题目内容
在一个数字游戏中,m(1≤m≤105) 个参与者排成一队,每人持有一个整数号码牌 n(0≤n≤109)。游戏只进行一轮,按照初始队列的顺序(从队首到队尾)处理每个人,每人仅处理一次,处理规则如下:
-
如果号码是 3 的倍数,则将其淘汰(从队列中移除)。
-
否则,如果号码的十进制表示中包含数字 3,则将其移动到队尾。
-
否则,如果号码的十进制表示中包含数字 2,则将其移动到队首。
-
否则,位置保持不变。
-
对于规则 2、3:不论插入队首还是队尾,他们的相对顺序与他们在初始队列中的相对顺序保持一致。
优先级说明:
输入描述
给定一个表示所有排成队列的链表的头 ListNode
输出描述
1.输出一行整数,表示最终队列的号码牌顺序,用空格分隔
2.超过号码牌整数范围或者人数超过总人数限制,返回 "−1"
样例1
输入
{12,23,7,13,8}
输出
"7 8 23 13"
说明
处理过程:
-
淘汰 12→[23,7,13,8]
-
23 移动到队尾 →[7,13,8,23]
-
7 不变 →[7,13,8,23]
-
13 移动到队尾 →[7,8,23,13]
-
8 不变 →[7,8,23,13]
最终顺序为 7 8 23 13。
样例2
输入
{6, 23, 32, 33, 2, 3}
输出
"2 23 32"
说明
• 6:是 3 的倍数,淘汰。
• 23:同时包含 2 和 3,但包含数字 3 所以触发规则 2(优先级高于规则 3),移动到队尾。
• 32:同时包含 2 和 3,但包含数字 3 所以触发规则 2(优先级高于规则 3),移动到队尾。
• 33:是 3 的倍数($33 $% 3==0),淘汰。
• 2:包含数字 2,移动到队首。
• 3:是 3 的倍数,淘汰。
样例3
输入
{100000000 1}
输出
"-1"
说明
数字超过 109,非法返回 −1 字符串