[LeetCode] Integer Break

leonardofed 發(fā)布于2019-08-14 16:29 / 932人閱讀

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

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66206.html

LeetCode 343. Integer Break

摘要：思路動態(tài)規(guī)劃，前五個數(shù)的最大乘積為，后面的第個數(shù)的最大乘積，由從后往前數(shù)包括本身的第三個數(shù)乘以得到。何睿何睿前個數(shù)的最大乘積動態(tài)規(guī)劃第個數(shù)的最大乘積為往前數(shù)第三個數(shù)思路與上面的思路一致，優(yōu)化了空間源代碼文件在這里。 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

摘要：題目要求將一個正整數(shù)分解為兩個或兩個以上的正整數(shù)，要求這些正整數(shù)的乘積最大。思路和代碼這里應用了一個數(shù)學的思路。假設我們有一個數(shù)字，該數(shù)組可以隨機分解為和。因此取時可以得到最好的結果。至于為什么我們需要盡可能用分解，因為。題目要求 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 計算逆波蘭表

摘要：棧法復雜度時間空間思路逆波蘭表達式的計算十分方便，對于運算符，其運算的兩個數(shù)就是這個運算符前面的兩個數(shù)。注意對于減法，先彈出的是減號后面的數(shù)。 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