1317. Convert Integer to the Sum of Two No-Zero Integers

置顶

Created At : 2023-10-28 15:14

Count:765 Views 👀 :

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 and B 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: 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://github.com/grandyang/leetcode/issues/1317

参考资料：

https://leetcode.com/problems/convert-integer-to-the-sum-of-two-no-zero-integers/

https://leetcode.com/problems/convert-integer-to-the-sum-of-two-no-zero-integers/solutions/478216/java-intuitive-non-brute-force/

https://leetcode.com/problems/convert-integer-to-the-sum-of-two-no-zero-integers/solutions/478189/java-simple-solution-beats-100/

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️.