1363. Largest Multiple of Three¶
题目信息¶
- 题号:
1363
- 难度:
Hard
- 主题:
数组、贪心、数位、模三
- 原题:
- 重点:
从给定数字中选择任意非空子集并重排,构造数值最大的三的倍数;不能使用额外数字
题目重述¶
给定十进制数字数组 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 整除。