在一条街和一个集合中所有数值的总和可以被3整除:
- n + n + n = 3n
- (n-1) + n + (n + 1) = 3n
因此,如果您将解决方案中所有数字相加,您将得到一个形如3N + 2M的数字,其中M是对中的瓦片的值。对于每个M的值,除以三后的余数(total % 3
)是:
total % 3 = 0 -> M = {3,6,9}
total % 3 = 1 -> M = {2,5,8}
total % 3 = 2 -> M = {1,4,7}
因此,您只需要尝试三个可能的对而不是九个,这基于简单的加法。对于每个可能的对,删除具有该值的两个瓷砖,并进入算法的下一步以确定是否可行。
一旦您得到这个结果,就从最低值开始。如果该值的瓷砖少于三个,则它们必然是一个序列的第一个元素,因此删除该序列(如果无法删除,因为缺少瓷砖n+1或n+2,则表示手牌无效)并继续进行下一个最低值。
如果最低值至少有三个瓷砖,则将它们作为一组删除(如果您问“如果它们是序列的一部分怎么办?”请考虑如果是这样,那么还有三个n+1和三个n+2的瓷砖,也可以成为一组),然后继续进行。
如果到达空手牌,则手牌有效。
例如,对于您的无效手牌,总数为60,这意味着M = {3,6,9}:
Remove the 3: 112244556789
- Start with 1: there are less than three, so remove a street
-> impossible: 123 needs a 3
Remove the 6: impossible, there is only one
Remove the 9: impossible, there is only one
使用您提供的第二个示例12345555678999
,总和为78,这意味着M = {3,6,9}:
Remove the 3: impossible, there is only one
Remove the 6: impossible, there is only one
Remove the 9: 123455556789
- Start with 1: there is only one, so remove a street
-> 455556789
- Start with 4: there is only one, so remove a street
-> 555789
- Start with 5: there are three, so remove a set
-> 789
- Start with 7: there is only one, so remove a street
-> empty : hand is valid, removals were [99] [123] [456] [555] [789]
你的第三个例子11223378888999总共有78个,这会导致回溯:
Remove the 3: 11227888899
- Start with 1: there are less than three, so remove a street
-> impossible: 123 needs a 3
Remove the 6: impossible, there are none
Remove the 9: 112233788889
- Start with 1: there are less than three, so remove streets
-> 788889
- Start with 7: there is only one, so remove a street
-> 888
- Start with 8: there are three, so remove a set
-> empty, hand is valid, removals were : [99] [123] [123] [789] [888]