Description
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 :
AandBare 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: A = 1, B = 1. A + B = n and both A and B do not contain any 0 in their decimal representation. Example 2:
Input: n = 11 Output: [2,9] Constraints:
2 <= n <= 10^4
这道题说是要把给定的正整数转化为两个不含零位的正整数之和，不含零位是指数字的个十百千位等都不是零。既然是 Easy 的题目，一般来说不会有太复杂的解法，通常来说暴力搜索的方法就可以。这道题也不例外，既然让返回任意一组解，就可以按遍历 {1, n-1}, {2, n-2}, {3, n-3} 等等的顺序来检验是否符合题意。检验是否含有零位可以放到一个子函数中，方法也非常直接，每次通过对 10 取余来获得最低位，判断其是否为0，然后原数字再自除以 10。这样就可以找到符合题意的组合了，参见代码如下：
解法一：
class Solution { public: vector<int> getNoZeroIntegers(int n) { for (int i = 1; i < n; ++i) { if (!hasZero(i) && !hasZero(n - i)) { return {i, n - i}; } } return {-1, -1}; } bool hasZero(int n) { while (n > 0) { if (n % 10 == 0) return true; n /= 10; } return false; } }; 再来看一种非暴力搜索的解法，这种方法有点巧妙，貌似用到了些数学方面的知识。这里还是每次取出最低位上的数字，假设为d，同时n自除以 10，若最低位d是0或者1的话，且此时n不是0的话，那么要从高位取个1，变成 10 或者 11 来拆，分别拆成 {1, 9} 或者 {2, 9}，同时n要自减1。对于其他的情况，拆成 {1, d-1}，注意为了跟原数字保持相同的为，这里拆成的数都要乘以 step，这里的 step 就是此时n缩小的倍数，参见代码如下：
解法二：
class Solution { public: vector<int> getNoZeroIntegers(int n) { int a = 0, b = 0, step = 1; while (n > 0) { int d = n % 10; n /= 10; if ((d == 0 || d == 1) && n > 0) { a += step * (1 + d); b += step * 9; --n; } else { a += step * 1; b += step * (d - 1); } step *= 10; } return {a, b}; } }; Github 同步地址:
参考资料：
https://leetcode.com/problems/convert-integer-to-the-sum-of-two-no-zero-integers/
LeetCode All in One 题目讲解汇总(持续更新中...)
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）
喜欢请点赞，疼爱请打赏❤️~.~
微信打赏
|
Venmo 打赏
---|---