14.剪绳子，快速幂

linwt · linwt · commit 630aa856de7e · 2022-05-01T18:12:39.000+08:00
diff --git a/剑指Offer_新版_java/JZ14.java b/剑指Offer_新版_java/JZ14.java
@@ -82,4 +82,37 @@ public int cutRope(int target) {
             return (int) Math.pow(3, y);
         }
     }
+}
+
+
+/*
+快速幂
+ */
+public class Solution {
+    public int cutRope(int target) {
+        if (target == 2 || target == 3) {
+            return target - 1;
+        }
+        int x = target % 3;
+        int y = target / 3;
+        if (x == 1) {
+            return pow(3, y - 1) * 4;
+        } else if (x == 2) {
+            return pow(3, y) * 2;
+        } else {
+            return pow(3, y);
+        }
+    }
+
+    private int pow(int base, int num) {
+        int res = 1;
+        while (num > 0) {
+            if ((num & 1) == 1) {
+                res *= base;
+            }
+            base *= base;
+            num >>= 1;
+        }
+        return res;
+    }
 }
