1317. 将整数转换为两个无零整数的和
1317. 将整数转换为两个无零整数的和
题目
No-Zero integer is a positive integer that does not contain any 0
in its decimal representation.
Given an integer n
, return a list of two integers [a, b]
where :
a
andb
are No-Zero integers.a + b = n
The test cases are generated so 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: Let a = 1 and b = 1.
Both a and b are no-zero integers, and a + b = 2 = n.
Example 2:
Input: n = 11
Output: [2,9]
Explanation: Let a = 2 and b = 9.
Both a and b are no-zero integers, and a + b = 9 = n.
Note that there are other valid answers as [8, 3] that can be accepted.
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
解题思路
判断数字是否包含
0
:- 通过一个辅助函数
isZeroInt
,判断一个数字是否包含数字0
。 - 对每个数字,我们逐位检查,直到没有
0
出现为止。
- 通过一个辅助函数
算法实现:
- 从
a = 1
开始,逐步增加a
,同时b = n - a
。 - 如果
a
和b
都不包含0
,则返回[a, b]
。 - 否则继续检查下一个
a
。
- 从
复杂度分析
- 时间复杂度:
O(n log n)
- 判断数字
n
是否包含0
的时间复杂度是O(log n)
。 - 最坏情况下,要判断
[1, n - 1]
中的所有数字,有n - 1
个。 - 因此整体时间复杂度为
O(n log n)
。
- 判断数字
- 空间复杂度:
O(1)
,只使用了常数空间。
代码
/**
* @param {number} n
* @return {number[]}
*/
var getNoZeroIntegers = function (n) {
const isZeroInt = (num) => {
while (num > 0) {
if (num % 10 == 0) return false;
num = Math.floor(num / 10);
}
return true;
};
let a = 1;
let b = n - 1;
while (true) {
if (isZeroInt(a) && isZeroInt(b)) {
return [a, b];
}
a++;
b--;
}
};