剑指 Offer14- I.剪绳子(基于贪心思想)

﹏ヽ暗。殇╰゛Y 2022-12-01 01:14 110阅读 0赞

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/jian-sheng-zi-lcof][https_leetcode-cn.com_problems_jian-sheng-zi-lcof]

原题描述：  
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m-1\] 。请问 k\[0\]*k\[1\]*…\*k\[m-1\] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。  
**示例 1：**  
输入: 2  
输出: 1  
解释: 2 = 1 + 1, 1 × 1 = 1

**示例 2:**  
输入: 10  
输出: 36  
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36  
**提示：**  
**2 <= n <= 58**

**解题思路：**  
设将长度为 n 的绳子切为 a段：   n = n 1 + n 2 + n 3 + . . . + n a \\ n = n\_1 + n\_2 + n\_3 + ...+ n\_a  n=n1\+n2\+n3\+...\+na

本题等价于求解：   M a x ( n 1 × n 2 × n 3 × . . . × n a ) \\ Max(n\_1 × n\_2 × n\_3 × ...× n\_a)  Max(n1×n2×n3×...×na)

两个重要推论：① 当所有绳段长度相等时，乘积最大。② 最优的绳段长度为 3 。  
最优： 3 。把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,2 三种情况。  
次优： 2 。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。  
最差： 1 。若最后一段绳子长度为 1 ；则应把一份 3 +1 替换为 2+2，因为 2×2 > 3 ×1。

**算法流程:**  
当2≤n≤3时，理应不切分，但是题目要求至少切一刀，所以。由n== 2时，只有1 × 1一种情况，n == 3时，只有 1×2。所以返回n-1即可。  
当n > 3时候，求n除以3的整数部分a和余数部分b，分一下三种情况讨论：  
1、b = 0 时，直接返回   3 a \\ 3^a  3a  
2、b = 1 时，返回    3 a − 1 × 4 \\ 3^\{a-1\} ×4  3a−1×4  
2、b = 2 时，返回   3 a × 2 \\ 3^a × 2  3a×2

C++源码

class Solution { 
    public:
        int pows(int x,int y )
        { 
            int ans = 1;
            for (int i = 0; i < y; ++i)
                ans *= x;
            return ans;
        }
        
        int cuttingRope(int n) { 
            if (n <= 3)
                return n -1 ;
            else
            { 
                int a = n / 3;
                int b = n % 3;
                if (b == 0)
                    return pows(3,a);
                else if (b == 1)
                    return pows(3,a-1) * 4;
                else
                    return pows(3,a) * 2;
            }
        }
    };

博客重点是纪念一下开始用LaTex编辑公式，以及之后坚定地使用LaTex。

[https_leetcode-cn.com_problems_jian-sheng-zi-lcof]: https://leetcode-cn.com/problems/jian-sheng-zi-lcof