青训营刷题笔记09

问题描述

小M面对一组从 1 到 9 的数字，这些数字被分成多个小组，并从每个小组中选择一个数字组成一个新的数。目标是使得这个新数的各位数字之和为偶数。任务是计算出有多少种不同的分组和选择方法可以达到这一目标。

• numbers: 一个由多个整数字符串组成的列表，每个字符串可以视为一个数字组。小M需要从每个数字组中选择一个数字。

例如对于[123, 456, 789]，14个符合条件的数为：147 149 158 167 169 248 257 259 268 347 349 358 367 369。

测试样例

样例1：

输入：numbers = [123, 456, 789]
输出：14

样例2：

输入：numbers = [123456789]
输出：4

样例3：

输入：numbers = [14329, 7568]
输出：10

思路：

1. 数字的奇偶性：我们首先注意到，数字的奇偶性是一个很重要的特性。选择的数字的和的奇偶性只取决于每个选择的数字的奇偶性：

   • 如果选择的数字是偶数，它对和的奇偶性没有影响。
   • 如果选择的数字是奇数，它会改变和的奇偶性（如果当前和是偶数，选择一个奇数后变成奇数，反之亦然）。

2. 动态规划的思路：我们可以用一个动态规划的方法来解决这个问题。设 dp[0] 表示当前选择的数字之和的奇偶性为偶数的组合数，dp[1] 表示当前选择的数字之和的奇偶性为奇数的组合数。

3. 迭代每个数字组：对于每个数字组，计算出它中有多少个偶数和奇数：

   • 偶数不会改变和的奇偶性。
   • 奇数会改变和的奇偶性。

4. 更新状态：每遍历一个新的数字组时，我们用当前的 dp 状态来更新新的 dp 状态：

   • 如果当前和是偶数，选择偶数还是奇数都会影响下一个状态。
   • 如果当前和是奇数，选择偶数和选择奇数的情况也会分别更新。

解法步骤：

1. 初始化一个 dp 数组，其中 dp[0] 表示偶数和的组合数，dp[1] 表示奇数和的组合数，初始时 dp[0] = 1（表示没有数字时，和为偶数）。
2. 遍历每个数字组，统计其中奇数和偶数的数量。
3. 根据奇偶数的选择，更新 dp 数组。
4. 最后返回 dp[0]，即和为偶数的组合数。

代码：

解释：

1. dp[0] 和 dp[1]：分别代表当前选择的数字之和为偶数和为奇数的组合数。

   • 初始时，只有 dp[0] = 1，表示没有任何数字时，和为偶数。
   • 选择每个数字组时，我们根据数字是偶数还是奇数来更新 dp 数组。

2. 更新步骤：对于每个数字组，我们统计其中的偶数和奇数的数量，分别用 even_count 和 odd_count 来表示：

   • 选择偶数时，当前和不变，因此偶数的选择只会增加 dp[0] 和 dp[1] 中对应偶数的部分。
   • 选择奇数时，当前和会发生变化，奇数的选择会交换 dp[0] 和 dp[1] 中的值。

3. 返回结果：最终的结果就是 dp[0]，表示和为偶数的组合数。

复杂度分析：

• 时间复杂度：O(n * m)，其中 n 是数字组的数量，m 是每个数字组的长度。每个组的遍历操作是线性的。
• 空间复杂度：O(1)，我们只用了常量空间来存储 dp 状态。