题目

「无零整数」是十进制表示中 不含任何 0 的正整数。

给你一个整数 n，请你返回一个 由两个整数组成的列表 [a, b]，满足：

• a 和 b 都是无零整数
• a + b = n

题目数据保证至少有一个有效的解决方案。

如果存在多个有效解决方案，你可以返回其中任意一个。

示例 1：

输入：n = 2 输出：[1,1] 解释：a = 1, b = 1。a + b = n 并且 a 和 b 的十进制表示形式都不包含任何 0。

示例 2：

输入：n = 11 输出：[2,9]

示例 3：

输入：n = 10000 输出：[1,9999]

示例 4：

输入：n = 69 输出：[1,68]

示例 5：

输入：n = 1010 输出：[11,999]

提示：

• 2 <= n <= 10^4

解题思路

如何判断一个数是不是“无零整数”

我们需要一个方法来检查一个正整数的十进制表示中是否含有数字 0。这里有两种常见的实现方式：

• 用 num % 10 可以得到 num 的最后一位数字。
• 如果最后一位是 0，那么这个数就不是“无零整数”，直接返回 false。
• 如果不是 0，就用 num / 10 去掉最后一位，继续检查剩下的部分。
• 如果循环结束（即 num 变成了 0）都没有发现 0，说明这个数是“无零整数”，返回 true。
• 方法二：字符串转换 这个方法更直观，但效率稍低。将整数转换为字符串，然后检查字符串中是否包含字符 '0' 即可。

方法一：数学方法（整数运算） 这是最高效的方法。通过循环，不断地取这个数的个位数，并判断它是否为 0。伪代码如下：

function containsZero(number):
    // 循环直到这个数的所有位都被检查过
    while number > 0:
        // 检查个位数是否为 0
        if number % 10 == 0:
            return true // 包含 0
        // 去掉个位数
        number = number / 10
    return false // 不包含 0

如何找到符合条件的 [a, b] 对？

简单法

题目要求我们找到两个无零整数 a 和 b，使得 a + b = n。

既然 a + b = n，那么只要我们确定了 a，b 的值也就随之确定了，即 b = n - a。

同时，题目要求 a 和 b 都是正整数，所以 a >= 1 且 b >= 1。由 b = n - a >= 1 可得 a <= n - 1。

因此，我们只需要在一个确定的范围内为 a 寻找一个合适的值即可。最简单的策略就是从 1 开始向上遍历。

按位构造法

我们可以不一个一个地去尝试 a 的值，而是直接根据 n 的每一位数字来构造出符合条件的 a 和 b 的每一位。这种方法的复杂度只和 n 的位数（即 log n）有关。

算法的核心思想是模拟小学学过的竖式加法，但是反过来——我们知道和 n，要去凑出两个加数 a 和 b。为了处理进位，我们从右到左（从个位到高位）处理 n 的每一位。

在构造 a 和 b 的每一位数字时，我们的目标是：

1. a 的当前位 da 不能是 0。
2. b 的当前位 db 不能是 0。
3. (da + db) 的个位数要等于 n 的当前位 dn (可能需要考虑来自更低位的进位)。

让我们来设计构造规则，假设我们正在处理 n 的某一位 dn：

• 情况一：dn >= 2 这是最简单的情况。我们可以直接把 dn 拆成两个非零数字。一个绝佳的选择是：
  • a 的当前位 da 设为 1。
  • b 的当前位 db 设为 dn - 1。 因为 dn >= 2，所以 dn - 1 >= 1，保证了 db 也不是 0。这样 da + db = dn，不会产生向高位的进位。
• 情况二：dn <= 1 (即 dn 是 0 或 1) 这时我们无法将 dn 拆成两个非零的数字（例如 1+0 或 0+1 都不行）。唯一的办法就是让 da + db 的和产生一个进位，也就是让它们的和等于 10 + dn。这个过程相当于向 n的更高位“借位”。
  • 我们可以选择 da = 2 和 db = 9。它们的和是 11。11 的个位数是 1，正好对应 dn=1 的情况。
  • 或者选择 da = 1 和 db = 9。它们的和是 10。10 的个位数是 0，正好对应 dn=0 的情况。
  • 为了统一处理，我们可以选择一个固定的组合，比如 da=2, db=8 (2+8=10) 或者 da=2, db=9(2+9=11)。
  • 关键一步：因为我们向高位借了 1，所以在处理 n 的下一位（更高位）之前，需要先将 n 减 1。

算法流程：

1. 初始化 a = 0, b = 0, powerOf10 = 1 (表示当前处理的是个位、十位、百位...)。
2. 当 n > 0 时，循环执行： a. 取出 n 的个位：dn = n % 10。 b. n = n / 10。 c. 如果 dn >= 2 (并且这不是 n的最高位且n不为0，或者 dn >= 1 且这是最高位)： * a += 1 * powerOf10。 * b += (dn - 1) * powerOf10。 d. 如果 dn <= 1： * a += 2 * powerOf10。 * b += (dn + 10 - 2) * powerOf10 (即 (dn+8)*powerOf10)。 * 因为借位了，所以 n 需要减 1：n--。 e. 更新 powerOf10 *= 10。
3. 循环结束后，a 和 b 就是最终答案。

具体代码

直接法

class Solution {
public:
    // 主函数，用于寻找两个无零整数
    std::vector<int> getNoZeroIntegers(int n) {
        // 从 a=1 开始遍历所有可能的组合
        for (int a = 1; a < n; ++a) {
            int b = n - a; // 计算 b

            // 检查 a 和 b 是否都不含 0
            if (!containsZero(a) && !containsZero(b)) {
                // 如果都不含 0，就找到了答案，直接返回
                return {a, b};
            }
        }
        
        // 根据题目保证，程序总会找到解，所以理论上不会执行到这里。
        // 但为了 C++ 函数定义的完整性，需要一个返回值。
        return {}; 
    }

private:
    // 辅助函数，检查一个数字是否包含 0
    bool containsZero(int num) {
        // 循环直到检查完所有位数
        while (num > 0) {
            // 如果个位数是 0，则包含 0
            if (num % 10 == 0) {
                return true;
            }
            // 去掉个位数，继续检查下一位
            num /= 10;
        }
        // 如果循环结束都没找到 0，则不包含 0
        return false;
    }
};

按位构造法

class Solution {
public:
    std::vector<int> getNoZeroIntegers(int n) {
        // O(log n) 高效解法
        int a = 0;
        int b = 0;
        long long powerOf10 = 1; // 使用 long long 防止 powerOf10 溢出

        while (n > 0) {
            int digit = n % 10;
            n /= 10;

            // 如果是最高位且为1，则不能拆分，也必须借位
            if ((digit <= 1) && n > 0) {
                // 需要向高位借位
                // 将当前位拆分为 2 和 9 (和为11) 或 2 和 8 (和为10)
                // 比如拆成 2 和 (digit + 10 - 2)
                a += 2 * powerOf10;
                b += (digit + 10 - 2) * powerOf10;
                n--; // 向高位借了1，所以n要减1
            } else {
                // 不需要借位
                // 将当前位拆分为 1 和 digit - 1
                a += 1 * powerOf10;
                b += (digit - 1) * powerOf10;
            }

            powerOf10 *= 10;
        }

        return {a, b};
    }
};