[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);
    }
    
}

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

查看所有标签

猜你喜欢:

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

Scrum精髓

Scrum精髓

Kenneth Rubin / 姜信宝、米全喜、左洪斌、(审校)徐毅 / 清华大学出版社 / 2014-6-1 / CNY 79.00

短短几年时间,Scrum跃升为敏捷首选方法,在全球各地得以普遍应用。针对如何用好、用巧这个看似简单的框架,本书以通俗易懂的语言、条理清晰的脉络阐述和提炼出Scrum的精髓。全书共4部分23章,阐述了七大核心概念:Scrum框架,敏捷原则,冲刺,需求和用户故事,产品列表,估算与速率,技术债;三大角色:产品负责人,ScrumMaster,开发团队以及Scrum团队构成:Scrum规划原则及四大规划活动......一起来看看 《Scrum精髓》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具