给定一个arr，里面的数字都是0~9，
你可以随意使用arr中的数字，哪怕打乱顺序也行，
请拼出一个能被3整除的，最大的数字，用str形式返回。
递归。从左往右遍历，要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
}
}执行结果如下：
