Java 中个位数是 K 的数字之和

在Java中找出各位数字为k且其和为给定num的数的任务是一个有趣的计算问题，可以使用不同的方法来解决。

示例 1

输入

输出

 
2    

解释

我们需要确定各位数字为9且总和为58的整数集合的最小尺寸。有效集合的例子是集合 [9, 49] 和 [19, 39] 等。可以达到的最小尺寸是2。

示例 2

输入

输出

 
-1    

解释

我们需要找到一个各位数字为2的整数集合的最小尺寸，该集合的总和为37。仅使用各位数字为2的整数无法达到37的总和。因此，输出为-1。

方法1：使用动态规划

动态规划（DP）是一种强大的技术，通过将问题分解为更小的重叠子问题并存储这些子问题的结果以避免重复计算来解决问题。

算法

步骤1：我们创建一个大小为num + 1的数组dp，用于存储求和到num的每个值所需的最小整数数量。我们将dp[0]设置为0，因为求和到0不需要任何数字。

步骤2：dp中的所有其他值都初始化为Integer.MAX_VALUE，表示那些总和最初是不可达的。

步骤3：填充DP数组：我们迭代遍历从1到num的每个可能总和j。对于每个总和j，我们检查是否可以通过添加各位数字为k的整数来达到j。

步骤4：各位数字为k的整数形式为 k, k+10, k+20，依此类推。对于每个这样的整数i，如果dp[j - i]不等于Integer.MAX_VALUE，则意味着我们可以通过将i加到总和j - i来形成总和j。我们将dp[j]更新为所需的最小整数数量。

步骤5：处理完所有总和后，dp[num]将保存使用各位数字为k的整数求和到num所需的最小整数数量。

步骤6：如果dp[num]仍然是Integer.MAX_VALUE，则表示无法使用各位数字为k的整数形成总和num，因此我们返回-1。

文件名： SumofNumbers.java

输出

 
num = 58, k = 9: 2
num = 37, k = 2: -1
num = 0, k = 7: 0   

时间复杂度

外层循环迭代所有可能的总和从1到num，这给了我们O(num)次迭代。内层循环迭代所有各位数字为k的整数，这是一个常数次的迭代（最多10次，因为个位数从0到9）。因此，总时间复杂度为O(num×10) = O(num)。

空间复杂度

我们使用一个大小为num + 1的数组dp来存储达到从0到num的每个总和所需的最小整数数量。因此，空间复杂度为O(num)。

方法2：优化方法

优化方法用于系统地检查所有可能的解决方案。它涉及迭代所有可能的组合并检查每个组合是否满足问题条件。问题要求找到各位数字为k且总和为num的整数的最小数量。数字的个位数可以从0到9。

算法

步骤1：初始化minimumNumbers方法以检查num是否为0。如果是，则立即返回0，因为空集求和为0。

步骤2：迭代检查：迭代可能的计数i从1到10（因为个位数只能是0到9）。

步骤3：对于每个i，计算i * k，并使用i * k % 10 == num % 10检查i * k的个位数是否与num的个位数匹配。

步骤4：如果找到匹配项，则返回i作为求和到num所需的最小整数数量。

步骤5：如果在迭代所有可能性（1到10）后未找到有效的i，则返回-1，表示无法使用各位数字为k的整数形成num。

文件名： SumofNumbers1.java

输出

 
num = 58, k = 9: 2
num = 37, k = 2: -1
num = 0, k = 7: 0   

时间复杂度

minimumNumbers方法迭代固定次数（10次迭代），而与num或k的大小无关。这是因为它从1循环到10来检查所有可能的各位数字为k的整数计数。这些操作是常数时间O(1)。因此，总时间复杂度是常数O(1)。

空间复杂度

该解决方案仅使用几个常数空间变量（num, k, i, count, and remaining），每个变量都需要常数空间，而与输入值无关。这些变量使用的空间不会随输入大小而变化，因此空间复杂度为O(1)。