1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 14 题] “剪绳子”做题记录

[剑指 Offer 第 2 版第 14 题] “剪绳子”做题记录

第 14 题:剪绳子

说明:同 LeetCode 343 题。

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

给你一根长度为 n 的绳子,请把绳子剪成 m 段(mn 都是整数,2 \\le n \\le 58^2 并且 m \\ge2)。

每段的绳子的长度记为 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 至少分割成 2 个部分,各个部分都大于 0,它们的乘积。

状态转移方程:用 j 遍历 1,2,…, i -1 ,要么分割成两部分:i - jj,要么是 jdp[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。

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

贪心算法:2(n-2)>n 得到 n > 43(n-3)>n ,得到 n>4.5,即 n 大于等于 5 的时候。

结论:不能包含 1 ,所有的加法因子只能有 23,最多只有 22,因此加法因子里没有 4

贪心选择的证明,可以参考这里:https://leetcode-cn.com/problems/integer-break/solution/tan-xin-xuan-ze-xing-zhi-de-jian-dan-zheng-ming-py/。

liwei20191019_1.png

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++ 代码:

14-2

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 14 题] “剪绳子”做题记录

链接:https://www.javajike.com/article/3265.html

« [剑指 Offer 第 2 版第 13 题] “机器人的运动范围”做题记录
[剑指 Offer 第 2 版第 16 题] “数值的整数次方”做题记录»

相关推荐

QR code