leetcode 343. Integer Break

233jl 发布于2019-08-15 14:44 / 1973人阅读

摘要：题目要求将一个正整数分解为两个或两个以上的正整数，要求这些正整数的乘积最大。思路和代码这里应用了一个数学的思路。假设我们有一个数字，该数组可以随机分解为和。因此取时可以得到最好的结果。至于为什么我们需要尽可能用分解，因为。

题目要求

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. 
Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume that n is not less than 2 and not larger than 58.

将一个正整数分解为两个或两个以上的正整数，要求这些正整数的乘积最大。

思路和代码

这里应用了一个数学的思路。假设我们有一个数字n，该数组可以随机分解为t和n-t。当分解为n/2时可以获得最大的乘积。因此t取n/2时可以得到最好的结果。但是这里我们明显还可以继续对t分解（如果t大于1），这样逐个分解之后终归会分解为2或者1为质因数

假设N为偶数，(N/2)*(N/2)>=N, 则 N>=4
假设N为奇数，(N-1)/2 *(N+1)/2, 则 N>=5

因此分解的数小于4。

至于为什么我们需要尽可能用3分解，因为3*3>2*2*2。

    public int integerBreak(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        
        int product = 1;
        while(n >4){
            product *= 3;
            n -= 3;
        }
        
        product *= n;
        return product;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 integer Leetcod LeetCode integer类型

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68790.html

LeetCode 343. Integer Break

摘要：思路动态规划，前五个数的最大乘积为，后面的第个数的最大乘积，由从后往前数包括本身的第三个数乘以得到。何睿何睿前个数的最大乘积动态规划第个数的最大乘积为往前数第三个数思路与上面的思路一致，优化了空间源代码文件在这里。 Description Given a positive integer n, break it into the sum of at least two positive...

ckllj 2019-07-31 10:17 评论0 收藏0
[LeetCode] Integer Break

Problem Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get. For example, given n = 2...

leonardofed 2019-08-14 16:29 评论0 收藏0
[LeetCode] 811. Subdomain Visit Count

Problem A website domain like discuss.leetcode.com consists of various subdomains. At the top level, we have com, at the next level, we have leetcode.com, and at the lowest level, discuss.leetcode.com...

jzman 2019-08-19 11:11 评论0 收藏0
[Leetcode] Evaluate Reverse Polish Notation 计算逆波兰表

摘要：栈法复杂度时间空间思路逆波兰表达式的计算十分方便，对于运算符，其运算的两个数就是这个运算符前面的两个数。注意对于减法，先弹出的是减号后面的数。 Evaluate Reverse Polish Notation Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operato...

ephererid 2019-08-14 12:40 评论0 收藏0
[LeetCode] 8. String to Integer (atoi)

Problem Implement function atoi to convert a string to an integer. If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values...

cuieney 2019-08-14 15:43 评论0 收藏0