343. 整数拆分

青旅半醒 2022-10-07 00:50 119阅读 0赞

> 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
> 
> 示例 1:
> 
> 输入: 2  
> 输出: 1  
> 解释: 2 = 1 + 1, 1 × 1 = 1。  
> 示例 2:
> 
> 输入: 10  
> 输出: 36  
> 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
> 
>

> **思路:**
> 
>   根据贪心算法，就尽量将原数拆成更多的 3
> 
>  
> 
> 如果整数 n 的形式是 3k+1，例如 7。按照上面规则，会拆分成“3 + 3 + 1”。 1 是没作用的。此时，应该将 1 和 3 变成 4，也就是“3 + 3 + 1”变成“3 + 4”。此时乘积最大
> 
>    
> 
> 综上所述，算法的整体思路是：
> 
> **n 除 3 的结果为 a，余数是 b  
> 当 b 为 0，直接将 a 个 3 相乘  
> 当 b 为 1，将（a-1）个 3 相乘，再乘以 4  
> 当 b 为 2，将 a 个 3 相乘，再乘以 2**

class Solution {
        public int integerBreak(int n) {
            /**
            一直 n 不小于 2 且不大于 58。
            贪心: 尽量拆多个3 
                如果余数是1 ,就(n-1)个三,1个四
    
                n 除 3 的结果为 a，余数是 b
                    当 b 为 0，直接将 a 个 3 相乘
                    当 b 为 1，将（a-1）个 3 相乘，再乘以 4
                    当 b 为 2，将 a 个 3 相乘，再乘以 2 
             */
            if(n==2){
                return 1;
            }
            if(n==3){
                return 2;
            }
           
             int a=n/3;
             int b=n%3;
             if(b==0){
                   return (int)( Math.pow(3,a));
             }
             else if(b==1){
                 return (int)(4*Math.pow(3,a-1));
             }
    
             return (int)(b*Math.pow(3,a));
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，119人围观）

还没有评论，来说两句吧...

相关阅读

相关 343. 整数拆分

343. 整数拆分给定一个正整数 n ，将其拆分为 k 个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例 1

川长思鸟来/ 2024年03月26日 18:11/ 0 赞/ 66 阅读

相关 LeetCode-343. 整数拆分

目录递归动态规划题目来源 [343. 整数拆分][343.] 递归对于给定的一个整数 n，穷举它的每一种分解情况，然后对所

「爱情、让人受尽委屈。」/ 2024年03月26日 17:53/ 0 赞/ 61 阅读

相关 343. 整数拆分

343. 整数拆分题干描述解题思路动态规划 1. 确定dp数组（dp table）以及下标的含义

小咪咪/ 2023年10月16日 16:05/ 0 赞/ 16 阅读

相关 leetcode 343. Integer Break | 343. 整数拆分（Java）

题目 [https://leetcode.com/problems/integer-break/][https_leetcode.com_problems_integer

╰半夏微凉°/ 2023年01月24日 02:12/ 0 赞/ 11 阅读

相关 C语言重构【343】整数拆分

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

系统管理员/ 2022年11月09日 01:29/ 0 赞/ 175 阅读

相关 343. 整数拆分

> 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。 > > 示例 1: > > 输入: 2 > 输出: 1

青旅半醒/ 2022年10月07日 00:50/ 0 赞/ 120 阅读

相关 leetcode 343 整数拆分

前言题目：[343. 整数拆分][343.] 参考题解：[整数拆分-代码随想录][-] -------------------- 提交代码题目：给定一个正

灰太狼/ 2022年08月28日 05:48/ 0 赞/ 167 阅读

相关 Leetcode 343. 整数拆分(DP)

题目重述给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例 1: 输入: 2 输出:

秒速五厘米/ 2022年08月28日 02:50/ 0 赞/ 177 阅读

相关 190512 | 整数拆分

题目描述一个整数总可以拆分为2的幂的和，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1

淩亂°似流年/ 2022年01月31日 23:43/ 0 赞/ 210 阅读

相关 LeetCode:343. Integer Break 拆分整数保持乘积最大

试题： Given a positive integer n, break it into the sum of at least two positive integer

- 日理万妓/ 2021年06月24日 16:10/ 0 赞/ 344 阅读