国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

LeetCode 343. Integer Break

ckllj / 2792人閱讀

摘要:思路動態規劃,前五個數的最大乘積為,后面的第個數的最大乘積,由從后往前數包括本身的第三個數乘以得到。何睿何睿前個數的最大乘積動態規劃第個數的最大乘積為往前數第三個數思路與上面的思路一致,優化了空間源代碼文件在這里。

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]

源代碼文件在 這里 。
?本文首發于 何睿的博客 ,歡迎轉載,轉載需保留 文章來源 ,作者信息和本聲明.

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

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

相關文章

  • leetcode 343. Integer Break

    摘要:題目要求將一個正整數分解為兩個或兩個以上的正整數,要求這些正整數的乘積最大。思路和代碼這里應用了一個數學的思路。假設我們有一個數字,該數組可以隨機分解為和。因此取時可以得到最好的結果。至于為什么我們需要盡可能用分解,因為。 題目要求 Given a positive integer n, break it into the sum of at least two positive in...

    233jl 評論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 評論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 評論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 評論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 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<