这周的题目相对比较简单了，基本上没有考察算法的内容，数学考察了 2 道，整体上做下来难度不大，就是第三道题因为题目的时间似乎卡得还比较小，所以费了一些时间在优化上，最终换了一种算法才通过。

Q1：日期之间隔几天

• 日期之间隔几天

这道题就很简单了，我直接用标准库计算，如果非要自己算的话，估计有很多边边角角需要考虑，很容易出错，不适合在这里使用，所以代码也很简单了：

[[email protected]]# cat Q1.go
func daysBetweenDates(date1 string, date2 string) int {
    d1, _ := time.Parse("2006-01-02", date1)
    d2, _ := time.Parse("2006-01-02", date2)
    delta := d1.Sub(d2)
    return abs(int(delta.Hours()) / 24)
}

Q2：验证二叉树

• 验证二叉树

这道题也是属于看上去很难，但实际上仔细一想也是很简单的那种，要想成功构建二叉树，而且给定了 0-n 都是有效的节点，那么只需要判断是不是所有的节点都有正确的父节点即可。这里有两个例子要解决：

• 循环依赖和一个节点拥有两个以上父节点：这种情况都很好判断，设置父节点的时候直接判断一遍是否已经存在父节点即可
• 森林：这个也容易判断，只要存在森林，那么肯定有非 0 节点没有父节点，那么直接判断节点有没有父节点即可发现是否存在森林

所以代码就可以这么写：

[[email protected]]# cat Q2.go
func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
    var (
        i      int
        parent = make([]int, 2*n)
    )

    parent[0] = -1
    if leftChild[0] != -1 {
        parent[leftChild[0]] = -1
    }
    if rightChild[0] != -1 {
        parent[rightChild[0]] = -1
    }
    for i = 1; i < n; i++ {
        if parent[i] == 0 {
            return false
        }
        if leftChild[i] != -1 {
            if parent[leftChild[i]] != 0 {
                return false
            }
            parent[leftChild[i]] = i
        }
        if rightChild[i] != -1 {
            if parent[rightChild[i]] != 0 {
                return false
            }
            parent[rightChild[i]] = i
        }
    }
    return true
}

Q3：最接近的因数

• 最接近的因数

这道题我错了 3 次，3 次都是超时，在本地验证了一下，发现 200ms 的时间就算超时了。第一次我是通过从平方根开始找，分别找到 sum + 1 和 sum +2 的最小因数对，然后再返回，结果就超时了。

在调试了 3 次之后，我决定换种方式进行，就是找出 sum + 1 和 sum+2 的所有因数，然后排个序，再返回，居然就通过了：

[[email protected]]# cat Q3.go
import (
    "math"
    "sort"
)

func closestDivisors(num int) []int {
    var (
        all1 = all(num + 1)
        all2 = all(num + 2)
    )
    sort.Slice(all1, func(i, j int) bool {
        return (all1[i][1] - all1[i][0]) < (all1[j][1] - all1[j][0])
    })
    sort.Slice(all2, func(i, j int) bool {
        return (all2[i][1] - all2[i][0]) < (all2[j][1] - all2[j][0])
    })

    if all2[0][1]-all2[0][0] > all1[0][1]-all1[0][0] {
        return all1[0]
    } else {
        return all2[0]
    }
}
func all(num int) (rtn [][]int) {
    for i := 1; i <= int(math.Sqrt(float64(num))); i++ {
        other := num / i
        if i*other == num {
            rtn = append(rtn, []int{i, other})
        }
    }
    return
}

Q4：形成三的最大倍数

• 形成三的最大倍数

这道题是披着困难外皮的中等题，我们都知道，如果一个数能够被 3 整除，那么各个位上的数字总和就是 3 的倍数，所以这里第一步就是将所有的数字加起来，让他们的和是 3 的倍数。这里有两个问题：

• 怎么保证最终的数字是最大的
• 如果所有的数字的总和不是 3 的倍数要怎么处理

第一个问题很简单，根据各个位上的数字按照降序排个序，然后就是最大的值了，例如 9876543210。
第二个问题稍微复杂一些，如果和不是 3 的倍数，那么就需要减掉一些数字让他满足 3 的倍数，那么这里就存在两种情况：

1. 所有数字总和除以 3 的余数是1：那么就从所有的数字中去掉一个 1 就可以了
2. 所有数字总和除以 3 的余数是2：那么就从所有的数字中去掉一个 2 就可以了

这里情况要复杂一些，就拿情况 1 来说，如果不存在数字1，那该如何选，有两个选择，分别是选出一个 4 或者 7，也可以选出 2 个 2，这里肯定是优先挑选一个数，因为最终数字的大小肯定是优先长度，长度越长，数字越大，所以只有在没有单个数字除以 3 余 1 的情况下时，我们才会考虑 2 个 2 这样的方案。

最终的代码这样写：

[[email protected]]# cat Q4.go
import (
    "sort"
    "strings"
)

func largestMultipleOfThree(digits []int) string {
    var (
        i, mod, sum int
        skipMap     = map[int]bool{}
        final       = []byte{}
        length      = len(digits)
        modIndex    = [][]int{
            nil,
            []int{-1, -1},
            []int{-1, -1}} // 0, 1, 2
    )

    sort.Ints(digits)
    for i = 0; i < length; i++ {
        sum += digits[length-1-i]
        mod = digits[length-1-i] % 3
        switch mod {
        case 1:
            modIndex[1][1] = modIndex[1][0]
            modIndex[1][0] = length - 1 - i
        case 2:
            modIndex[2][1] = modIndex[2][0]
            modIndex[2][0] = length - 1 - i
        }
    }

    switch sum % 3 {
    case 0:
        break
    case 1:
        if modIndex[1][0] == -1 && modIndex[2][1] == -1 {
            return ""
        }
        if modIndex[1][0] != -1 {
            skipMap[modIndex[1][0]] = true
        } else {
            skipMap[modIndex[2][0]] = true
            skipMap[modIndex[2][1]] = true
        }
    case 2:
        if modIndex[1][1] == -1 && modIndex[2][0] == -1 {
            return ""
        }
        if modIndex[2][0] != -1 {
            skipMap[modIndex[2][0]] = true
        } else {
            skipMap[modIndex[1][0]] = true
            skipMap[modIndex[1][1]] = true
        }
    }
    for i = 0; i < length; i++ {
        if skipMap[length-1-i] {
            continue
        }
        final = append(final, '0'+uint8(digits[length-1-i]))
    }
    rtn := strings.TrimLeft(string(final), "0")
    if len(rtn) == 0 && len(final) != 0 {
        return "0"
    }
    return rtn
}