形成三的最大倍数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
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
# 总结
- 分析出几种情况，然后分别对各个情况实现
