Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。
这里是第 171 期的第 1 题，也是题目列表中的第 1317 题 -- 『将整数转换为两个无零整数的和』
「无零整数」是十进制表示中 不含任何 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
EASY
题目的要求为，给定一个整数，需要返回把它当作和的一对不包含 0 的整数加数。
读完题目后，我的第一反应是，是不是有什么数学方法可以找到答案。摸摸猪鼻子，想了一会，没想到什么靠谱的方法。一定是小猪太苯了，蓝瘦 T_T
接下来把思路转向了偏计算机的方式。那么第一反应就是，暴力枚举。时间复杂度 O(n)，应该能 AC，那就先试试吧。
这种思路其实非常直接，就是遍历一边所有可能的加数，然后判断它们是否包含 0 即可。由于题目对于返回的解没有要求，所以我们直接返回第一组遇到的解即可。具体流程如下：
- 从 1 开始遍历所有的加数。
- 判断该加数和对应的被加数是否包含 0。
- 返回遇到的第一个解。
不过这里可以做一点小小的优化。一方面是，在判断 0 的过程中，我们在除以 10 之后的取整操作可以直接用位运算实现。另一方面是，对于每一个整数，它是否包含 0 是一个客观的事实。所以我们可以针对所有的测试用例进行全局的缓存，避免不必要的计算。并且由于题目限制了范围是 [2, 10^4]，所以我们可以用一个固定长度的数组来进行记录。
具体代码如下：
const memo = new Uint8Array(10000);
const helper = x => {
if (memo[x] !== 0) return memo[x] === 1;
while (x > 0) {
if (x % 10 === 0) { memo[x] = 2; return false; }
x = x / 10 << 0;
}
memo[x] = 1;
return true;
};
const getNoZeroIntegers = n => {
let m = 0;
while (n--) {
if (helper(++m) && helper(n)) return [m, n];
}
};熟悉小猪的小伙伴可能会猜到，如果只给一个 brute force 方案，小猪一定不会满足哒 >.<
于是在一番绞尽脑汁之后，小猪决定先去玩几盘吃鸡， 小猪把思路从新放回了题目条件本身。如果想把一个整数变成一个不包含 0 的整数，那么可能有两种情况。第一种，这个数本身就不包含 0，那么我们祝它新年快乐。第二种，其中某一位数字是 0，对于这种情况，我们详细分析一下。
首先，这个 0 不可能是最高位，因为题目给定的是普通的整数。那么我们如果想要把它变成别的数字的话，要么是增，要么是减。由于我们是在寻找加数，所以只能选择减。并且由于不是先导 0，所以减是安全的。减的数值基于当前位置来确定，例如百位的话就减 100，十位的话就减 10。这样我们就把当前位置的 0 替换成了非 0。
不过这里需要注意的是，我们的一对加数都需要进行同步的加减运算，并且都需要反复进行是否包含 0 的验证。具体流程如下：
- 把 1 和
n - 1作为初始值。 - 判断它们是否包含 0：
- 如果包含的话，找到 0 的位置，并减去对应位置的基数，回到步骤 2。
- 如果不包含，祝它新年快乐。
- 输出结果。
基于这个流程，我们可以实现类似这样的代码：
const helper = x => {
let digit = 0;
while (x > 0) {
if (x % 10 === 0) break;
x = x / 10 << 0;
++digit;
}
return 10 ** digit;
};
const getNoZeroIntegers = n => {
let x = 1, y = n - 1;
while (true) {
let num = helper(y);
if (num < y) {
y -= num;
x += num;
continue;
}
num = helper(x);
if (num > x) break;
y -= num;
x += num;
}
return [x, y];
};这段代码暂时 beats 100%。
周赛第一题，惯例送保底分。不过这道题我觉得用枚举的方式已经 OK 了，后面提供的非枚举的思路只是供小伙伴们娱乐一下。因为虽然不知道为什么，不过我总觉得这样去处理问题有点怪怪的。
嘛，可能有很多小伙伴已经回家啦，或者被堵在了回家的路上。这里还是提前送上小猪诚挚的祝福，希望大家在新的一年里，发际线一定要平安哦。么么哒 >.<
