【剑指offer】剪绳子(两种思路)

剪绳子

https://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8?answerType=1&f=discussion

class Solution {
public:
    int cutRope(int number) {
        if(number == 2) return 1;
        if(number == 3) return 2;
       //动态规划, O(n)
        vector<int> res = {0, 1, 2, 3};//数组这里记录的长度是不考虑继续再剪的最长长度,和前面的返回值稍有区别。
        for(int i = 4; i <= number; i++){
            int j = i / 2;
            res.push_back(res[j] * res[i - j]);
        }
        return res[number];
        /*
        找到规律发现,最大乘绩的分法一般就是一堆3和一个2或者两个2的组合
        O(logn)
        int x = number % 3;
        int y = number / 3;
        if(x == 0)
            return (long long) pow(3, y);
        else if(x == 1)
            return 2 * 2 (long long) pow(3, y - 1);
        else
            return 2 * (long long) pow(3, y);
        */
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 12:10
点赞 评论 收藏
分享
码农索隆:单休一个月少休息4天,一年就是48天,平时节假日,别人3天假期,单休的两天
点赞 评论 收藏
分享
醉蟀:你不干有的是人干
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 18:06
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务