[LeetCode]Minimum Factorization

题目描述:


LeetCode 625. Minimum Factorization

Given a positive integer a
, find the smallest positive integer b
whose multiplication of each digit equals to a
.

If there is no answer or the answer is not fit in 32-bit signed integer, then return 0.

Example 1

Input:

Output:

Example 2

Input:

Output:

题目大意:

给定正整数a,求各位相乘等于a的最小整数。

若不存在这样的整数,或者超过32位带符号整数范围,则返回0。

解题思路:

解法I 从9到2试除

Python代码:

class Solution(object):
    def smallestFactorization(self, a):
        """
        :type a: int
        :rtype: int
        """
        if a == 1: return 1
        cnt = [0] * 10
        for x in range(9, 1, -1):
            while a % x == 0:
                cnt[x] += 1
                a /= x
        if a > 1: return 0
        ans = int(''.join(str(n) * cnt[n] for n in range(2, 10)))
        return ans <= 0x7FFFFFFF and ans or 0

解法II 因式分解

将a因式分解,若存在大于9的因子,则直接返回0

a的因子包括2, 3, 5, 7四种类型

优先用3构造因子9,然后用2和3构造因子6,最后用2构造因子4

将各因子递增输出

Java代码:

import java.math.BigInteger;

public class Solution {
    public int smallestFactorization(int a) {
        if (a == 1) return 1;
        int cnt[] = new int[10];
        while (a > 1) {
            for (int x = 2; x  9) return 0;
                if (a % x == 0) {
                    cnt[x]++;
                    a /= x;
                    break;
                }
            }
        }
        cnt[9] = cnt[3] / 2;
        cnt[3] %= 2;
        cnt[8] = cnt[2] / 3;
        cnt[2] %= 3;
        if (cnt[2] > 0 && cnt[3] > 0) {
            cnt[2]--;
            cnt[3] = 0;
            cnt[6] = 1;
        }
        if (cnt[2] == 2) {
            cnt[2] = 0;
            cnt[4] = 1;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= 9; i++) {
            for (int j = 0; j  0)
            return 0;
        return Integer.parseInt(ans);
    }
    
}
书影责编内容来自:书影 (源链) | 更多关于

阅读提示:酷辣虫无法对本内容的真实性提供任何保证,请自行验证并承担相关的风险与后果!
本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合技术 » [LeetCode]Minimum Factorization

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录