LeetCode Weekly Contest 177
LeetCode Weekly Contest 177
日期之间隔几天
题目描述
请你编写一个程序来计算两个日期之间隔了多少天。
日期以字符串形式给出，格式为 YYYY-MM-DD，如示例所示。
示例 1：
输入：date1 = “2019-06-29”, date2 = “2019-06-30” 输出：1
示例 2：
输入：date1 = “2020-01-15”, date2 = “2019-12-31” 输出：15
提示：
给定的日期是 1971 年到 2100 年之间的有效日期。
解法
直接调用库函数了。
func daysBetweenDates(date1 string, date2 string) int {
t1, _ := time.Parse("2006-01-02", date1)
t2, _ := time.Parse("2006-01-02", date2)
ans := t1.Sub(t2).Hours()
if ans > 0 {
return int(ans) / 24
}
return -int(ans) / 24
}验证二叉树
题目描述
二叉树上有 n 个节点，按从 0 到 n - 1 编号，其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。
只有 所有 节点能够形成且 只 形成 一颗 有效的二叉树时，返回 true；否则返回 false。
如果节点 i 没有左子节点，那么 leftChild[i] 就等于 -1。右子节点也符合该规则。
注意：节点没有值，本问题中仅仅使用节点编号。
示例 1：
输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
输出：true示例 2：
输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
输出：false示例 3：
输入：n = 2, leftChild = [1,0], rightChild = [-1,-1]
输出：false示例 4：
输入：n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1]
输出：false提示：
1 <= n <= 10^4leftChild.length == rightChild.length == n-1 <= leftChild[i], rightChild[i] <= n - 1
解法
// TODO最接近的因数
题目描述
给你一个整数 num，请你找出同时满足下面全部要求的两个整数：
- 两数乘积等于
num + 1或num + 2 - 以绝对差进行度量，两数大小最接近
你可以按任意顺序返回这两个整数。
示例 1：
输入：num = 8 输出：[3,3] 解释：对于 num + 1 = 9，最接近的两个因数是 3 & 3；对于 num + 2 = 10, 最接近的两个因数是 2 & 5，因此返回 3 & 3 。
示例 2：
输入：num = 123 输出：[5,25]
示例 3：
输入：num = 999 输出：[40,25]
提示：
1 <= num <= 10^9
解法
最简单的思路，从平方根开始，两数之差一定是最小的。
func closestDivisors(num int) []int {
num1, num2 := num+1, num+2
for ans := int(math.Sqrt(float64(num2))); ans > 0; ans-- {
if (num1)%ans == 0 {
return []int{ans, num1 / ans}
} else if (num2)%ans == 0 {
return []int{ans, num2 / ans}
}
}
return []int{}
}形成三的最大倍数
题目描述
给你一个整数数组 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^40 <= digits[i] <= 9- 返回的结果不应包含不必要的前导零。
解法
一开始想了好久用 DP 做，后面发现只是个普通的数学题 。
如果一个数的各位数之和相加是 3 的倍数，则它本身就是 3 的倍数，然后从大到小排序即可。
剩下的问题就变成，在数组中找到尽可能多的数且数值最大。
数组中的所有数可分成三类：num % 3 == 0, 1, 2。
若和模 3 余 1，则去掉余数为 1 的那类数里最小的一个数即可，不行就删两个余 2 的。余 2 同理。
func largestMultipleOfThree(digits []int) string {
// 先处理特殊情况
s := sum(digits)
if s == 0 {
return "0"
} else if s%3 == 0 {
return genMaxString(digits)
}
// 余数分类
remainder := make([][]int, 3)
for i := range remainder {
remainder[i] = []int{}
}
for i := range digits {
mod := digits[i] % 3
remainder[mod] = append(remainder[mod], digits[i])
}
// 在可拿的情况下，保证拿的都是最大的
sort.Ints(remainder[1])
sort.Ints(remainder[2])
resDigits := remainder[0] // 以余 0 为基础
len1, len2 := len(remainder[1]), len(remainder[2])
// 尽可能的多拿，[1,1,1,2]
if s%3 == 1 {
if len1 > 0 {
remainder[1][0] = -1 // -1 代表删除
} else if len2 > 1 {
remainder[2][0] = -1
remainder[2][1] = -1
}
} else {
if len2 > 0 {
remainder[2][0] = -1
} else if len1 > 1 {
remainder[1][0] = -1
remainder[1][1] = -1
}
}
resDigits = append(resDigits, remainder[1]...)
resDigits = append(resDigits, remainder[2]...)
return genMaxString(resDigits)
}
func sum(nums []int) int {
ans := 0
for i := range nums {
ans += nums[i]
}
return ans
}
func genMaxString(nums []int) string {
ans := ""
sort.Sort(sort.IntSlice(nums))
for i := 0; i < len(nums); i++ {
if nums[i] == -1 { // -1 代表删除
continue
}
ans = strconv.Itoa(nums[i]) + ans
}
return ans
}