[LeetCode]Minimum Factorization

栏目: 编程工具 · 发布时间: 7年前

内容简介:[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 <= a; x++) {
                if (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 < cnt[i]; j++) {
                sb.append(Integer.toString(i));
            }
        }
        String ans = sb.toString();
        if (new BigInteger(ans).compareTo(BigInteger.valueOf(Integer.MAX_VALUE)) > 0)
            return 0;
        return Integer.parseInt(ans);
    }
    
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

用户故事地图

用户故事地图

Jeff Patton / 李涛、向振东 / 清华大学出版社 / 2016-4-1 / 59.00元

用户故事地图作为一种有效的需求工具,越来越广泛地应用于开发实践中。本书以用户故事地图为主题,强调以合作沟通的方式来全面理解用户需求,涉及的主题包括怎么以故事地图的方式来讲用户需求,如何分解和优化需求,如果通过团队协同工作的方式来积极吸取经验教训,从中洞察用户的需求,开发真正有价值的、小而美的产品和服务。本书适合产品经理、用户体验设计师、产品负责人、业务分析师、IT项目经理、敏捷教练和精益教练阅读和......一起来看看 《用户故事地图》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

html转js在线工具
html转js在线工具

html转js在线工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具