标签: 数学
难度: Easy
「无零整数」是十进制表示中 不含任何 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运行时间: 21 ms
内存: 16.1 MB
class Solution:
def getNoZeroIntegers(self, n: int) -> List[int]:
for i in range(1,n):
s = n-i
if '0' not in str(s) and '0' not in str(i):
return [i,s]
该题解采取了一种直接的扫描方法。从1开始逐个尝试整数i作为A，计算B为n-i，然后检查这两个数是否包含数字0。如果这两个数中都没有0，那么这一对就是可行的答案。此方法保证了找到的第一对满足条件的A和B就是解，因为它从最小的可能值开始检查，从而尽快找到满足条件的一对数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def getNoZeroIntegers(self, n: int) -> List[int]:
for i in range(1, n): # 从1开始尝试每个可能的A
s = n - i # 计算对应的B
if '0' not in str(s) and '0' not in str(i): # 检查A和B是否包含数字0
return [i, s] # 如果都不包含0，返回这一对数
将数字转换为字符串来检查是否含有'0'是一种简单直观的方法。这种方法通过转换数字为字符串，然后检查字符串中是否存在字符'0'来实现。相比之下，使用取余操作进行检查虽然避免了字符串的额外空间消耗，但逻辑更复杂，需要循环除以10并检查每次的余数直到数字变为0。因此，字符串方法在代码可读性和简洁性上有优势，尽管在性能上略逊一筹，特别是对于大数字。
这种从1开始逐个尝试的策略基于的是简单和直接的思路，确保了从最小的数字开始寻找，逐步增加，直到找到满足条件的一对整数。这种方法确保了解的正确性，但不一定是最高效的。例如，可以考虑从中间值开始向两边扩展搜索，或者使用二分查找的策略来减少检查的次数。然而，这些方法可能需要更复杂的逻辑来处理边界条件和中间计算，因此在实现上可能不如直接逐个尝试来得简单明了。
当n非常大时，该算法的性能确实会受到影响。因为随着n的增加，数字转换成字符串的操作会涉及更长的字符串，这会导致内存使用增加和处理速度下降。此外，随着i的逐渐增大，检查每个数字是否包含'0'的操作次数也会增加，因此整体性能会有所下降。这种情况下，优化算法以减少不必要的检查或改进检查方法可能会有帮助，比如预先排除一些显然不合条件的数字范围。
从n的一半开始遍历是一个有趣的思路，可以减少检查的次数，特别是当n较大时。这种方法意味着我们从中间开始，同时向上和向下寻找不包含'0'的整数对。这可能会更快地接近满足条件的解，尤其是在n的值较为集中时。然而，这种方法需要额外的逻辑来同时向两边检查，并处理可能的边界条件，例如确保不会错过任何可能的解。尽管这种方法在理论上可能更高效，但实际上可能因为实现复杂度较高而不被采用。