原文链接: https://leetcode-cn.com/problems/convert-integer-to-the-sum-of-two-no-zero-integers

英文原文

Given an integer n. No-Zero integer is a positive integer which doesn't contain any 0 in its decimal representation.

Return a list of two integers [A, B] where:

• A and B are No-Zero integers.
• A + B = n

It's guarateed that there is at least one valid solution. If there are many valid solutions you can return any of them.

 

Example 1:

Input: n = 2
Output: [1,1]
Explanation: A = 1, B = 1. A + B = n and both A and B don't contain any 0 in their decimal representation.

Example 2:

Input: n = 11
Output: [2,9]

Example 3:

Input: n = 10000
Output: [1,9999]

Example 4:

Input: n = 69
Output: [1,68]

Example 5:

Input: n = 1010
Output: [11,999]

 

Constraints:

• 2 <= n <= 10^4

中文题目

「无零整数」是十进制表示中 不含任何 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

通过代码

高赞题解

随机大法好！

（大雾）
思路：当正确答案比错误答案还多时，不妨随便蒙一个。

[]
class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        while(True):
            L = random.randint(1,n)
            R = n-L
            if '0' not in str(L) and '0' not in str(R):
                return [L,R]

时间复杂度：O(n^0.046 * lg(n))，两个部分：

· While循环：O(n^0.046)。
平均循环次数 == 命中无零整数的期望。生成数字每增加一位，就会有1/10的几率命中0，使得命中期望变为原来的10/9。
因此，平均循环次数为 (10/9) ^ lg(n)，整理得n ^ lg(10/9)，约为n的0.046次幂。
考虑到2147483647 ^ 0.046 = 2.673,在Int范围和O(1)几乎没啥区别。

· If校验：O(lg(n))
'0' not in dec(int)需要lg(n)的时间复杂度。

统计信息

通过次数	提交次数	AC比率
10553	17145	61.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言