难度: Medium
给你两个整数 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 <= 30000 <= k <= 9运行时间: 24 ms
内存: 15.9 MB
class Solution:
def minimumNumbers(self, num: int, k: int) -> int:
if num == 0: return 0
if num%10 == k: return 1
for i in range(1,11):
c = num - k*i
if c > 0 and c% 10 == k:
return i+1
return -1
此题目要求找到一个整数多重集的最小大小，其中每个整数的个位都是 k，且它们的和为 num。首先，如果 num 为 0，则结果直接为 0，因为空集的和为 0。如果 num 的个位就是 k，那么一个整数即可满足条件，返回 1。接下来，对于一般情况，算法尝试通过添加形如 10n + k 的整数来组合出 num。通过迭代 i 从 1 到 10，并计算 c = num - k*i，若 c 是正数且 c 的个位也是 k，那么总共需要 i+1 个数字（i 个 k 和一个 c）。如果在迭代过程中无法找到满足条件的组合，返回 -1。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def minimumNumbers(self, num: int, k: int) -> int:
if num == 0: return 0 # 如果 num 为0，返回0
if num % 10 == k: return 1 # 如果 num 的个位就是 k，返回1
for i in range(1, 11): # 迭代 i 从 1 到 10
c = num - k * i # 计算 num 减去 i 个 k 后的值
if c > 0 and c % 10 == k: # 检查是否能由 i+1 个数字组成 num
return i + 1
return -1 # 如果无法找到合适的组合，返回-1
选择迭代范围为 1 到 10 的原因在于数字的个位数字只有十种可能（0 到 9）。因此，当我们尝试通过增加 k 的倍数来接近 num 时，我们只需要考虑最多 10 个增量（1k 到 10k），这样可以覆盖所有可能的个位数字的变化。这个范围确保我们不会错过任何可能的解决方案，因为超过 10 倍后，个位数字的变化会开始重复。
当 `c` 计算为负数时，这意味着从 num 中减去的 k 的倍数已经超过了 num 本身，即我们已经尝试从 num 中减去过多的 k。在这种情况下，由于不能使用负数整数来满足题目要求，因此这种情况被忽略。继续迭代也不会产生有效的解，因为增加更多的 k 只会使 `c` 的值更负。
在这种特定算法中，检查 `c > 0 and c % 10 == k` 时不包括 `c == 0` 是因为如果 `c == 0`，这意味着已经可以用前面的 k 的倍数完全构成 num，无需其他数字。此外，如果 `c == 0` 且 `i` 的迭代已经开始（即 i > 0），则意味着我们不需要额外的数字来达到 num，这与我们的目标（使用尽可能少的数字）相悖。因此，这种情况下 `c == 0` 被视为一个不需要处理的特殊情况。
虽然算法在理论上对于任何大小的 `num` 和任何值的 `k` 都是有效的，但如果 `num` 非常大而 `k` 较小，迭代的过程中可能会存在性能问题。原因是尽管迭代的次数上限固定为 10，但大数的运算（特别是在 `num - k * i` 的计算中）可能会增加运算的时间和复杂度。然而，由于迭代次数固定，这种方法的时间复杂度仍被保持在一个可控的水平上。