🌕🌗 剑指 Offer 14- II. 剪绳子 II

难度: 🌕🌗

🌗 🌕

问题描述

---

解法

class Solution {
    public int cuttingRope(int n) {
        // 思路：
        // 经验公式
        if(n == 2) {
            return 1;
        }
        if(n == 3) {
            return 2;
        }
        int count = n / 3;
        int lef = n % 3;
        if(lef == 0) {
            return mySol(count, 1);
        } else if(lef == 1) {
            return mySol(count - 1, 4);
        } else {
            return mySol(count, 2);
        }
    }

    // 快速幂求 3^n
    private int mySol(int n, int ext) {
        long res = 1;
        long cur = 3; // 初始值，值 == 3^x 当前轮
        while(n != 0) {
            if(n % 2 == 1) {
                res = (res * cur) % 1000000007;
            }
            cur = (cur * cur) % 1000000007;
            n /= 2;
        }
        res = (res * ext) % 1000000007;
        return (int)res;
    }
}

---

输出