给你两个整数 num 和 k ,考虑具有以下属性的正整数多重集:
每个整数个位数字都是 k 。
所有整数之和是 num 。
返回该多重集的最小大小,如果不存在这样的多重集,返回 -1 。
注意:多重集与集合类似,但多重集可以包含多个同一整数,空多重集的和为 0 。
个位数字 是数字最右边的数位。
示例 1:输入:num = 58, k = 9 输出:2
解释:多重集 [9,49] 满足题目条件,和为 58 且每个整数的个位数字是 9 。
另一个满足条件的多重集是 [19,39] 。
可以证明 2 是满足题目条件的多重集的最小长度。
示例 2:输入:num = 37, k = 2 输出:-1
解释:个位数字为 2 的整数无法相加得到 37 。
示例 3:输入:num = 0, k = 7 输出:0
解释:空多重集的和为 0 。
提示:0 <= num <= 3000
0 <= k <= 9
1、枚举;时间复杂度O(n),空间复杂度O(1)
func minimumNumbers(num int, k int) int {
if num == 0 {
return 0
}
if k == 0 {
if num%10 == 0 {
return 1
}
return -1
}
if num%2 == 1 && k%2 == 0 {
return -1
}
for i := 1; i <= num; i++ {
sum := i * k
left := num - sum
if left%10 == 0 {
return i
}
if left < 0 {
return -1
}
}
return -1
}
2、枚举;时间复杂度O(1),空间复杂度O(1)
func minimumNumbers(num int, k int) int {
if num == 0 {
return 0
}
for i := 1; i <= 10; i++ {
// 只考虑个位数
if i*k <= num && (i*k)%10 == num%10 {
return i
}
}
return -1
}
Medium题目,找到规律枚举即可
留言与评论(共有 0 条评论) “” |