题目

给定一个数组，里面有若干个0-9的数字, 可能会重复出现，找出用这些数组成的最大的3的倍数

1
int result = solution(int[] array);
parameter type meaning
array int[] 由0-9的数字组成,可以重复出现
result int 排列array里的数字，得到最大的能被3整除的数

思路

由于3的特殊性，组成该数的所有数字也能被3整除

从结果反推

1
最大的3的倍数=合并(降序(数字集合))

那么该如何找这个数字集合呢

针对这一问题，可以将所有数字分为三类

variable meaning
numLeft0 除以3余0即3的倍数的集合
numLeft1 除以3余1的数的集合
numLeft2 除以3余2的数的集合

显然，numLeft0应该是数字集合的子集

1
数字集合.concatenate(numLeft0)

对于numLeft1和numLeft2
我们希望优先考虑数字更大的数，因此，我们将这两个列表降序排列

为了使引入的数是3的倍数，可以考虑重复向数字集合中同时添加numLeft1与numLeft2中各一个数

如果numLeft1与numLeft2的长度相同，那么数字集合就添加完成了

但多数情况下长度不相等：

如果numLeft1更多

尝试在剩余的数中3 by 3地向数字集合添加，这样能保证添加的数能被3整除

如果最后还有两个数没有添加，那么在数字集合中替换1个从numLeft2添加的数，为这2个没有添加的数。因为在整除3这个问题上，两个余数为1的数与一个余数为2的数是等效的

如果numLeft2更多

和上文类似

尝试在剩余的数中3 by 3地向数字集合添加，这样能保证添加的数能被3整除

如果最后还有两个数没有添加，那么在数字集合中替换1个从numLeft1添加的数，为这2个没有添加的数。因为在整除3这个问题上，两个余数为2的数与一个余数为1的数是等效的

到此，数字集合就构造完成了,剩下的工作就简单了

1
2
3
4
5
数字集合.sort();//升序
int result=0;
for(int i=0;i<数字集合.length;i++){
    result+=数字集合.get(i)*10**i;
}

最后附上整体代码

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
54
55
56
57
58
59
public static long solution(int[] numbers){
    ArrayList<Integer> numLeft0=new ArrayList<>();
    ArrayList<Integer> numLeft1=new ArrayList<>();
    ArrayList<Integer> numLeft2=new ArrayList<>();
    for (int n : numbers)
    {
        if (n % 3 == 0)
        {
            numLeft0.add(n);
        }
        else if (n % 3 == 1)
        {
            numLeft1.add(n);
        }
        else if (n % 3 == 2)
        {
            numLeft2.add(n);
        }
    }
    numLeft1.sort((a,b)->-a.compareTo(b));//降序
    numLeft2.sort((a, b) -> -a.compareTo(b));
    ArrayList<Integer> result = new ArrayList<>(numLeft0);


    int numLeft1_count,numLeft2_count;
    numLeft1_count=Math.min(numLeft1.size(),numLeft2.size());
    numLeft2_count=numLeft1_count;

    boolean isNumLeft1More=numLeft1.size()>numLeft2.size();
    var more=isNumLeft1More?numLeft1:numLeft2;
    int increase=(more.size()-numLeft1_count)/3;
    if(isNumLeft1More){
        numLeft1_count+=3*increase;
        if(numLeft1.size()-numLeft1_count>1){
            numLeft1_count+=2;
            numLeft2_count--;
        }
    }else {
        numLeft2_count+=3*increase;
        if(numLeft2.size()-numLeft2_count>1){
            numLeft1_count--;
            numLeft2_count+=2;
        }
    }
    for(int i=0;i<numLeft1_count;i++){
        result.add(numLeft1.get(i));
    }
    for(int i=0;i<numLeft2_count;i++){
        result.add(numLeft2.get(i));
    }
    result.sort(Integer::compareTo);

    long result_int=0;
    for(int i=0;i<result.size();i++){
        result_int+= (long) result.get(i) *(int)Math.pow(10,i);
    }
    return result_int;
}