1363. Largest Multiple of Three

题目信息

题号:

1363

难度:

Hard

主题:

数组、贪心、数位、模三

原题:

LeetCode 1363

重点:

从给定数字中选择任意非空子集并重排,构造数值最大的三的倍数;不能使用额外数字

题目重述

给定十进制数字数组 digits。可以选择其中任意数量的数字,每个元素最多使用一次,并按任意顺序连接成一个整数。

返回能够构造的最大三的倍数,以字符串表示。若无法构造非空结果,返回空字符串;若最优结果只由零组成,返回 "0" 而不是多个前导零。

1 <= digits.length <= 10^4,0 <= digits[i] <= 9。

自建示例

删除一个余数不合适的数字后降序排列:

输入:digits = [8,6,7,1,0]
输出:"8760"
解释:删除数字 1 后数位和为 21,可构造最大的三的倍数 8760。

没有非空三的倍数时返回空字符串:

输入:digits = [1,1]
输出:""
解释:可构造的非空整数数位和为 1 或 2,都不能被 3 整除。