[数据结构与算法]每日算法Leetcode --- 剪绳子

每日算法Leetcode — 剪绳子

本文中的题都来自leetcode和剑指offer

1. 题目

给你一根长度为 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。

• 思路

因为这个主要就在于减多少合适？
最简单的肯定不减一米长的乘积不影响大小（除非只有两米）
这里我看过好多推导的公式，都是利用了数学公式的推导最后解到了 e 的大小，这就意味这剪成2.7 m最好，所以 3 米为最优解，2 m次之

• 贪心算法

    public int cuttingRope(int n) {
        // 根据推导，发现e~2.7 所以尽量将绳子分成3的长度最优，二次之
        // 应为当n = 1 时 0
        //  n = 2    --- 1
        // n=3  -- 2 
        if( n <= 3){
            return n-1;
        }
        
        // 当n > 3 时 ，就会有三分出来 ,num表示分出3的个数
        int num =  n / 3 ;
        
        // 为最后乘积
        double max =0;

        // 当余数为1 则最后两个数 3+1 ==2 +2 
        if( n % 3 == 1){
            max = Math.pow(3,num-1) * 4 ;
        }else if( n % 3 == 2 ){
            max = Math.pow(3,num) * 2 ;
        }else if( n % 3 == 0){
            max = Math.pow(3,num) ;
        }

        return (int)max ;

    }

• 动态规划
  动态规划的主要思路就是，将结果存入结果集合中，每次向前调用，就不会重复计算已经算过的东西。
  从3m开始往后割绳子，每次都调用前面的结果，将最大值存入数组。遍历结束之后，只需要返回对应的索引数组的值就行。

  public int cuttingRope(int n) {
        // 我们可以当做每个数组中就是以索引长度的最大值
        int[] dp =new  int[n+1];
        
        // 因为dp数组默认值为零，所以dp[1] = 0 , 但是在分割的时候要最少分割2m
        dp[2] = 1 ;
        for(int i = 3; i<= n ; i++){
            for(int j =2; j < i ; j++){
               dp[i] = Math.max(dp[i],Math.max(j*(i-j),j * dp[i-j]));
              // dp[i] = Math.max(dp[i],j * dp[i-j]);
            }
        }
        return dp[n];
    }

2.剪绳子II

题目和剪绳子 l 一样，就是判断数据大一点，当大于1000000007时需要取余。

• 思路还是贪心算法，但是这回不能调用java的库函数了，因为在算3的高次幂的时候，引用方法隐藏了细节，没法在中途进行取余，只能对结果取余。所以不调用库函数

  public int cuttingRope(int n) {
      // 当小于等于3的时候 和上边一样
         if(n <= 3) return n - 1;
     // 因为容易超int 的取值范围，所以long防止大数据时的丢失    
        long res=1L;
        int p=(int)1e9+7;
        //贪心算法，优先切三，其次切二
        while(n>4){
            res=res*3%p;
            n-=3;
        }
        //出来循环只有三种情况，分别是n=2、3、4
        return (int)(res*n%p);
    }