形成三的最大倍数Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。

由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。如果无法得到答案，请返回一个空字符串。返回的结果不应包含不必要的前导零。

示例 1：

输入：digits = [8,1,9]
输出："981"

示例 2：

输入：digits = [8,6,7,1,0]
输出："8760"

示例 3：

输入：digits = [1]
输出：""

示例 4：

输入：digits = [0,0,0,0,0,0]
输出："0"

提示：

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

# 思路

Integer[] digitsArray = Arrays.stream(digits).boxed().toArray(Integer[]::new);

# 解法

import java.util.Arrays;

class Solution {
    private String strMax(String s1, String s2) {
        if (s1.length() == s2.length())
            return s1.compareTo(s2) > 0 ? s1 : s2;
        return s1.length() > s2.length() ? s1 : s2;
    }

    public String largestMultipleOfThree(int[] digits) {
        // Sort digits in descending order
        Integer[] digitsArray = Arrays.stream(digits).boxed().toArray(Integer[]::new);
        Arrays.sort(digitsArray, (a, b) -> b - a);

        StringBuilder y0 = new StringBuilder();
        StringBuilder y1 = new StringBuilder();
        StringBuilder y2 = new StringBuilder();

        for (int digit : digitsArray) {
            char c = (char) (digit + '0');
            switch (digit % 3) {
                case 0:
                    y0.append(c);
                    if (y1.length() > 0)
                        y1.append(c);
                    if (y2.length() > 0)
                        y2.append(c);
                    break;
                case 1:
                    String tmp_y1 = y1.toString();
                    y1 = new StringBuilder(strMax(y1.toString(), y0.toString() + c));
                    if (y2.length() > 0)
                        y0 = new StringBuilder(strMax(y0.toString(), y2.toString() + c));
                    if (tmp_y1.length() > 0)
                        y2 = new StringBuilder(strMax(y2.toString(), tmp_y1 + c));
                    break;
                case 2:
                    String tmp_y0 = y0.toString();
                    if (y1.length() > 0)
                        y0 = new StringBuilder(strMax(y0.toString(), y1.toString() + c));
                    if (y2.length() > 0)
                        y1 = new StringBuilder(strMax(y1.toString(), y2.toString() + c));
                    y2 = new StringBuilder(strMax(y2.toString(), tmp_y0 + c));
                    break;
            }
        }

        if (y0.length() > 0 && y0.charAt(0) == '0')
            return "0";
        return y0.toString();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# 总结

分析出几种情况，然后分别对各个情况实现

#Java