[LeetCode] Integer Break

leonardofed 发布于2019-08-14 16:29 / 915人阅读

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, 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.

Hint

There is a simple O(n) solution to this problem.
You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

Solution

1. beat 40.83% O(log(n))

public class Solution {
    public int integerBreak(int n) {
        if (n < 4) return n-1;
        else if(n%3 == 0)
            return (int)Math.pow(3, n/3);
        else if(n%3 == 1)
            return 4*(int)Math.pow(3, (n-4)/3);
        else 
            return 2*(int)Math.pow(3, n/3);
    }
}

2. beat 40.83% O(n)

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

3. DP beat 40.83% O(n)

public class Solution {
    public int integerBreak(int n) {
        if (n < 4) return n-1;
        int[] dp = new int[n+1];
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            dp[i] = Math.max(3*dp[i-3], 2*dp[i-2]);
        }
        return dp[n];
    }
}

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

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

转载请注明本文地址：https://www.ucloud.cn/yun/66206.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 343. Integer Break

摘要：题目要求将一个正整数分解为两个或两个以上的正整数，要求这些正整数的乘积最大。思路和代码这里应用了一个数学的思路。假设我们有一个数字，该数组可以随机分解为和。因此取时可以得到最好的结果。至于为什么我们需要尽可能用分解，因为。题目要求 Given a positive integer n, break it into the sum of at least two positive in...

233jl 2019-08-15 14:44 评论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