LeetCode 343. Integer Break

ckllj 发布于2019-07-31 10:17 / 2791人阅读

摘要：思路动态规划，前五个数的最大乘积为，后面的第个数的最大乘积，由从后往前数包括本身的第三个数乘以得到。何睿何睿前个数的最大乘积动态规划第个数的最大乘积为往前数第三个数思路与上面的思路一致，优化了空间源代码文件在这里。

Description

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.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.

描述

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

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

思路

动态规划，前五个数的最大乘积为 1, 2, 4, 6, 9，后面的第 i 个数的最大乘积，由从后往前数（包括 i 本身）的第三个数乘以 3 得到。

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-04-08 17:35:39
# @Last Modified by:   何睿
# @Last Modified time: 2019-04-08 18:15:43


class Solution:
    def integerBreak(self, n: int) -> int:
        # 前 5 个数的最大乘积
        tmp = [1, 2, 4, 6, 9]
        for i in range(5, n - 1):
            # 动态规划：第 i 个数 的最大乘积为 3 * 往前数第三个数
            tmp.append(3 * tmp[i - 3])
        return tmp[n - 2]

    def integerBreak2(self, n: int) -> int:
        # 思路与上面的思路一致，优化了空间
        if n == 2: return 1
        if n == 3: return 2
        tmp = [4, 6, 9]
        for i in range(n - 6):
            tmp[i % 3] *= 3
        return tmp[(n - 1) % 3]

源代码文件在这里。
©本文首发于何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明.

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

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

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

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] 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