LeetCode 1363. 形成三的最大倍数

约 7 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 微软
标签
数组 动态规划 数学 排序 贪心

题目描述

✅ 1363. 形成三的最大倍数

image-20260928224426412

image-20260928224426413

题意分析

给定若干个零到九的数字，可以选择其中一部分，并任意调整它们的顺序，组成数值最大的三的倍数。每个数字的使用次数不能超过输入中的次数，允许不使用某些数字。

返回字符串，因为结果可能远超整数范围。不能组成任何非空合法数字时返回空串；如果可用结果只有零，返回单个 "0"，不保留多余前导零。

解法：计数 + 贪心

核心思路

[!blue]

十进制整数能被三整除，当且仅当数位和能被三整除。因此先把所有数字计数，并计算总和对三的余数，再删除少量数字使剩余和余零。数位顺序不影响整除性，确定保留哪些数字后再排列即可。

为了让数最大，首先尽量保留位数。只要结果含非零数字，降序排列后就没有前导零，多一位必然更大；只有全零情况需要最后统一成零。在保留位数相同的情况下，应尽量保留大数字，也就是从允许删除的类别中优先删除最小值。

若总和余一，最少的修正方式是删一个余一数字，候选按一、四、七的顺序寻找。不存在时，只能删两个余二数字，候选按二、五、八升序选两份。余二情况完全对称。余零数字的删除无法修正余数，只会损失位数，不应删除。

为什么后备的两份一定存在？以总和余一且没有余一数字为例，非零余数只能来自余二类，其数量乘二后余一，数量必然至少为二。余二且缺少余二类时同理。因此这两个分支覆盖所有情况，不需要考虑删除更多位。

删除函数先检查候选数量是否足够，再真正扣减计数。这样一次失败尝试不会破坏后备方案的输入。最后按九到零展开所有保留数字，得到这个多重集合能够组成的最大排列。

解题步骤

  1. 统计十种数字的次数，累加数位和。
  2. 和余一时优先删除一个最小余一数字，否则删除两个最小余二数字；余二时对称处理。
  3. 和余零时不删除，直接保留全部数字。
  4. 从九到零依次按频次拼接。
  5. 没有剩余数字则返回空串；降序结果首位为零说明全零，返回 "0"；否则返回完整结果。

代码实现

class Solution {

    public String largestMultipleOfThree(int[] digits) {
        int[] count = new int[10];
        int sum = 0;

        for (int d : digits) {
            count[d]++;
            sum += d;
        }

        int mod = sum % 3;

        // 先删一个匹配余数的数字，不存在时才删两个另一余数类。
        if (mod == 1 && !removeDigits(count, new int[] {
            1,
            4,
            7
        }, 1)) {
            removeDigits(count, new int[] {
                2,
                5,
                8
            }, 2);
        } else if (mod == 2 && !removeDigits(count, new int[] {
            2,
            5,
            8
        }, 1)) {
            removeDigits(count, new int[] {
                1,
                4,
                7
            }, 2);
        }

        StringBuilder res = new StringBuilder();

        // 同一保留多重集按降序排列，才能得到最大整数。
        for (int d = 9; d >= 0; d--) {
            for (int i = 0; i < count[d]; i++) {
                res.append(d);
            }
        }

        if (res.length() == 0) {
            return "";
        }

        // 降序后首位为零，说明剩下全是零，统一返回单个零。
        if (res.charAt(0) == '0') {
            return "0";
        }

        return res.toString();
    }

    private boolean removeDigits(int[] count, int[] candidates, int need) {
        int remain = need;

        for (int d : candidates) {
            remain -= Math.min(count[d], remain);
        }

        if (remain > 0) {
            return false;
        }

        for (int d : candidates) {
            while (count[d] > 0 && need > 0) {
                count[d]--;
                need--;
            }
        }

        return true;
    }
}

func largestMultipleOfThree(digits []int) string {

    count := make([]int, 10)
    sum := 0
    for _, d := range digits {
        count[d]++
        sum += d
    }

    mod := sum % 3
    // 先删一个匹配余数的数字，不存在时才删两个另一余数类。
    if mod == 1 && !removeDigits(count, []int{
        1,
        4,
        7,
    }, 1) {
        removeDigits(count, []int{
            2,
            5,
            8,
        }, 2)
    } else if mod == 2 && !removeDigits(count, []int{
        2,
        5,
        8,
    }, 1) {
        removeDigits(count, []int{
            1,
            4,
            7,
        }, 2)
    }

    res := make([]byte, 0, len(digits))
    // 同一保留多重集按降序排列，才能得到最大整数。
    for d := 9; d >= 0; d-- {
        for i := 0; i < count[d]; i++ {
            res = append(res, byte('0'+d))
        }
    }

    if len(res) == 0 {
        return ""
    }
    // 降序后首位为零，说明剩下全是零，统一返回单个零。
    if res[0] == '0' {
        return "0"
    }

    return string(res)
}

func removeDigits(count []int, candidates []int, need int) bool {
    remain := need
    for _, d := range candidates {
        if count[d] < remain {
            remain -= count[d]
        } else {
            remain = 0
        }
    }

    if remain > 0 {
        return false
    }

    for _, d := range candidates {
        for count[d] > 0 && need > 0 {
            count[d]--
            need--
        }
    }

    return true
}

复杂度分析

  • 时间复杂度：$O(n)$，统计和输出各扫描线性数量的数字，余数修正只检查固定数字集并至多删除两份。
  • 空间复杂度：$O(n)$，用于构造输出；频次数组及修正候选本身为常数空间。

关键点总结

[!green]

  • 整除性由数位和决定，数值大小由保留位数及降序排列决定。
  • 优先减少删除数量，同样数量下删除最小候选。
  • 候选按余数分组，删除两份时不要求它们数值相同。
  • 空结果与全零结果含义不同，必须分别返回。

易错点总结

[!yellow]

  • 为了删更小的数字而优先删两位，可能丢掉本来能保留的一位，整体结果反而更小。
  • 同余类别从大到小删除，会损失对高位更有价值的数字。
  • 删除尝试失败前已经修改计数，会污染另一种修正方案，需先确认数量足够。
  • 数字都删完时不能凭空返回零，只有确实保留了零才能返回 "0"。
  • 不应把拼接结果解析成整数，结果长度可能超出数值类型范围。

相似题目

题目 难度 关联与区别
1262. 可被三整除的最大和 中等 同样按模3分类舍弃元素，但本题目标是拼成整数的长度和字典序，原题最大化数值和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/74903862
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！