X

LEETCODE 1317. Convert Integer to the Sum of Two No-Zero Integers 解题思路分析

题目大意:

将整数转换为两个无零整数的和

「无零整数」是十进制表示中 不含任何 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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1317

解题思路分析:

初始时,我们将给定的整数n分解成1和n-1两个数字,分别判断两个数字中是否包含0,如果不包含,直接返回这两个数字即可。如果包含的话,较小的数字加一,较大的数字减一,循环此步骤,直到找到结果。

另外,判断一个数字中是否包含0的方法很多,这里分享其中一种。对于一个十进制数字求其每一位的方法之前文章多次介绍过,即使用当前数字与10求余数,该余数即是10进制数的最低位,然后将该十进制数字除以10,继续与10求余数即可得到次低位上的数字,以此类推。解题时,查看每一位上的数字是否为0即可。

实现代码:

public int[] getNoZeroIntegers(int n) {
    // 将n差分成2个数字
    int a = 1, b= n-1;
    // 当a小于等于n时
    while(a<=n){
        // 如果a和b两个数字都不包含0,返回这两个数字
        if(isValid(a)&&isValid(b)){
            return new int[]{a,b};
        }
        // 反之a加一,b减一
        a++;
        b--;
    }
    return new int[]{a,b};
}
// 判断数字中是否包含0
boolean isValid(int num){
    while(num>0){
        if(num%10==0) return false;
        num/=10;
    }
    return true;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 97.11% of Java online submissions for Convert Integer to the Sum of Two No-Zero Integers.

Memory Usage: 34.7 MB, less than 100.00% of Java online submissions for Convert Integer to the Sum of Two No-Zero Integers.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1317-convert-integer-to-the-sum-of-two-no-zero-integers-解题思路分析/
Categories: leetcode
kwantong: