LeetCode Weekly Contest 177

算法

字数统计: 1.2k阅读时长: 5 min

 2020/02/23   Share

日期之间隔几天

题目描述

请你编写一个程序来计算两个日期之间隔了多少天。

日期以字符串形式给出，格式为 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^4
leftChild.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^4
0 <= 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
}

原文作者：wywwzjj

原文链接：https://wywwzjj.top/2020/02/23/LeetCode-Weekly-Contest-177/

发表日期：February 23rd 2020, 12:34:38 pm

更新日期：May 25th 2021, 6:50:50 pm

Next Post

LeetCode Weekly Contest 21（双周赛）
Previous Post

ThinkPHP 3.X / 5.X order by 注入

CATALOG

1. 日期之间隔几天
1. 1.1. 题目描述
2. 1.2. 解法
2. 验证二叉树
1. 2.1. 题目描述
2. 2.2. 解法
3. 最接近的因数
1. 3.1. 题目描述
2. 3.2. 解法
4. 形成三的最大倍数
1. 4.1. 题目描述
2. 4.2. 解法

