2021-12-31：给定一个arr，里面的数字都是0~9， 你可以随意使用arr中的数字，哪怕打乱顺序也行， 请拼出一个能被3整除的，最大的数字，用str形式返回。 来自去哪儿网。

答案2021-12-31：

递归。从左往右遍历，要i还是不要i。 贪心的思路解法 : 先得到数组的累加和，记为sum 1 . 如果sum%3 == 0，说明所有数从大到小拼起来就可以了 2 . 如果sum%3 == 1，说明多了一个余数1， 只需要删掉一个最小的数(该数是%3 == 1的数); 如果没有，只需要删掉两个最小的数(这两个数都是%3 == 2的数); 3 . 如果sum%3 == 2，说明多了一个余数2， 只需要删掉一个最小的数(该数是%3 == 2的数); 如果没有，只需要删掉两个最小的数(这两个数都是%3 == 1的数); 如果上面都做不到，说明拼不成。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "sort"
)

func main() {
    A := []int{1, 2, 3, 4, 1}
    ret := max3(A)
    fmt.Println(ret)
}

func max3(A []int) string {
    if len(A) == 0 {
        return ""
    }
    mod := 0
    arr := make([]int, 0)
    for _, num := range A {
        arr = append(arr, num)
        mod += num
        mod %= 3
    }
    if (mod == 1 || mod == 2) && !remove(&arr, mod, 3-mod) {
        return ""
    }
    if len(arr) == 0 {
        return ""
    }
    //arr.sort((a, b) -> b - a);
    sort.Slice(arr, func(i, j int) bool {
        return arr[i] > arr[j]
    })
    if arr[0] == 0 {
        return "0"
    }
    //StringBuilder builder = new StringBuilder();
    builder := make([]byte, 0)
    for _, num := range arr {
        //builder.append(num);
        builder = append(builder, []byte(fmt.Sprint(num))...)
    }
    return string(builder)
}

// 在arr中，要么删掉最小的一个、且%3之后余数是first的数
// 如果做不到，删掉最小的两个、且%3之后余数是second的数
// 如果能做到返回true，不能做到返回false
func remove(arr *[]int, first, second int) bool {
    if len(*arr) == 0 {
        return false
    }
    //arr.sort((a, b) -> compare(a, b, first, second));
    sort.Slice(*arr, func(i, j int) bool {
        return compare((*arr)[i], (*arr)[j], first, second) < 0
    })
    size := len(*arr)
    if (*arr)[size-1]%3 == first {
        //arr.remove(size - 1)
        *arr = (*arr)[0 : size-1]
        return true
    } else if size > 1 && (*arr)[size-1]%3 == second && (*arr)[size-2]%3 == second {
        //arr.remove(size - 1)
        //arr.remove(size - 2)
        *arr = (*arr)[0 : size-2]
        return true
    } else {
        return false
    }
}

// a和b比较:
// 如果余数一样，谁大谁放前面
// 如果余数不一样，余数是0的放最前面、余数是s的放中间、余数是f的放最后
func compare(a, b, f, s int) int {
    ma := a % 3
    mb := b % 3
    if ma == mb {
        return b - a
    } else {
        if ma == 0 || mb == 0 {
            return twoSelectOne(ma == 0, -1, 1)
        } else {
            return twoSelectOne(ma == s, -1, 1)
        }
    }
}

func twoSelectOne(c bool, a, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

执行结果如下： 图片

左神java代码