面试题14- II. 剪绳子 II

水深无声 2023-03-13 06:49 48阅读 0赞

# 题目： #

[面试题14- II. 剪绳子 II][14- II. _ II]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解： #

![在这里插入图片描述][20200512172125521.png]  
参考代码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
还需要注意的是，不能用[面试题14- I. 剪绳子][14- I.]中的方法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]

# 代码： #

import java.util.*;
    
    public class 面试题14_2 { 
    
        public static int cuttingRope(int n) { 
            if(n <= 3)
            { 
                return n - 1;
            }
            if(n == 4)
            { 
                return 4;
            }
            int mod = 1000000007;
            long res = 1;
            while(n > 4)
            { 
                res = res * 3;
                res = res % mod; // 避免取余出错建议每部取余
                n = n - 3;
            }
            return (int)(res * n % mod); // 这里必须取括号，否则会优先计算res*n的值，报错会超出范围
        }
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while(sc.hasNextInt())
            { 
                int n = sc.nextInt();
                int res = cuttingRope(n);
                System.out.println(res);
            }
        }
    }

# 参考： #

1.  [面试题14- II. 剪绳子 II（数学推导 / 贪心思想 + 快速幂求余，清晰图解）][14- II. _ II_ _ _ _]
2.  [剪绳子2][2]
3.  [Java贪心 思路讲解][Java_]
4.  [找这道题的本质][Link 1]

[14- II. _ II]: https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: /images/20230312/7111491ae3b84e3cb14e188e7f04f2f4.png
[20200512172125521.png]: /images/20230312/9d7f25e04bd34c7e8cc07ba12a2d7a8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200512173808238.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020051217384379.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[14- I.]: https://zhangyx.blog.csdn.net/article/details/106073725
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200512171434741.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200512171744597.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[14- II. _ II_ _ _ _]: https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/mian-shi-ti-14-ii-jian-sheng-zi-iitan-xin-er-fen-f/
[2]: https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/jian-sheng-zi-2-by-asjdklfjfklsadh/
[Java_]: https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/javatan-xin-si-lu-jiang-jie-by-henrylee4/
[Link 1]: https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/zhao-zhe-dao-ti-de-ben-zhi-by-lui-6/