复杂度O(1),利用简单数学定理实现

剪绳子

http://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8

复杂度基本是O(1)级别。
对于相乘最大问题,数学上可以这么理解:如果两个数,那么理解为周长相等的矩形,正方形面积比长方形的大;如果三个数,那么理解为立方体的体积比长方体的大……以此类推。
也就是说,m个数相加等于n,找到一个数curr,curr的m次方大于等于n,那么curr就是我们要找的绳子的段数,当然最后会有一段绳子小于等于curr。具体算法如下

public class Solution {
    public int cutRope(int target) {
        if(target == 2) return 1;
        int curr = 1;
        while(true){
            if(curr * curr >= target) break;
            curr++;
        }
        int res = 1;
        while(target > curr){
            res *= curr;
            target -= curr;
        }
        res *= target;
        return res;
    }
}
全部评论
好牛啊 这思想简直了 我觉得你写的相当好!
点赞
送花
回复
分享
发布于 2020-06-22 17:09
这个代码是错的 15的时候你这输出是4*4*4*3 实际情况是3的5次方
点赞
送花
回复
分享
发布于 2021-02-09 10:14
滴滴
校招火热招聘中
官网直投
而且时间复杂度也不是O(1) 你这有循环 时间复杂度是O(根号n)
点赞
送花
回复
分享
发布于 2021-02-09 10:21

相关推荐

点赞 1 评论
分享
牛客网
牛客企业服务