《剑指 Offer （第 2 版）》第 14 题：剪绳子

第 14 题：剪绳子

说明：同 LeetCode 343 题。

传送门：AcWing 25. 剪绳子，牛客网 online judge 地址。

给你一根长度为 的绳子，请把绳子剪成 段（、 都是整数， 并且 ）。

每段的绳子的长度记为 k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少？

例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。

样例：

输入：8

输出：18

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

分析：这道题在牛客网上没有 online judge ，我们可以去完成 LeetCode 上第 343 题检验自己的代码是否编写正确。

动态规划。关键在于画出树形结构图。

状态：dp[i]，这个状态就是题目中要我们求的。把整数 i 至少分割成 个部分，各个部分都大于 ，它们的乘积。

状态转移方程：用 j 遍历 1，2，…, i -1 ，要么分割成两部分：i - j 和 j，要么是 j 和 dp[i-j]，取最大者。

Python 代码：dp[0] 这个位置没有使用

class Solution(object):
    def maxProductAfterCutting(self, length):
        """
        :type length: int
        :rtype: int
        """

        assert length > 1

        dp = [0 for _ in range(length + 1)]

        dp[1] = 1

        for i in range(2, length + 1):
            for j in range(1, i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return dp[length]

Java 代码：使用动态规划

class Solution {
    public int integerBreak(int n) {
        if (n <= 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int max = 0;
            for (int j = 1; j < i; j++) {
                max = max3(max, j * (i - j), j * dp[i - j]);
            }
            dp[i] = max;
        }
        return dp[n];
    }

    private int max3(int num1, int num2, int num3) {
        return Integer.max(Integer.max(num1, num2), num3);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int integerBreak = solution.integerBreak(8);
        System.out.println(integerBreak);
    }
}

Java 代码：使用贪心算法

class Solution2 {
    public int integerBreak(int n) {
        if (n <= 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        if (n == 4) {
            return 4;
        }
        // 接下来就是 n >= 5 的时候的逻辑了
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        res *= n;
        return res;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int integerBreak = solution2.integerBreak(8);
        System.out.println(integerBreak);
    }
}

LeetCode 343 题：整数拆分

传送门：343. 整数拆分

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

示例 1:

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

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

分析：这是一个很经典的问题。可以使用贪心算法。

贪心算法： 得到 ， ，得到 ，即 大于等于 的时候。

结论：不能包含 ，所有的加法因子只能有 和 ，最多只有 个 ，因此加法因子里没有 。

image-20190108000201883

Java 代码：

class Solution2 {
    public int integerBreak(int n) {
        if (n <= 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        if (n == 4) {
            return 4;
        }
        // 接下来就是 n >= 5 的时候的逻辑了
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        res *= n;
        return res;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int integerBreak = solution2.integerBreak(8);
        System.out.println(integerBreak);
    }
}

C++ 代码：

image-20190108000417713