Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/07/24 22:44)推噓4(4推 0噓 0→)

留言4則, 4人參與討論串381/719 (看更多)

https://leetcode.com/problems/powx-n/description/ 50. Pow(x, n) 實現一個計算 x 的 n 次方的函數。 Example 1: Input: x = 2.00000, n = 10 Output: 1024.00000 Example 2: Input: x = 2.10000, n = 3 Output: 9.26100 Example 3: Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 思路： 1.有輪子了直接拿來用。 Java Code： --------------------------------------------- class Solution { public double myPow(double x, int n) { return Math.pow(x, n); } } --------------------------------------------- 面試官：你可以回去等通知了。 -- https://i.imgur.com/DANRJFR.jpg

-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1690088536.A.A3B.html ：（思路： 1.一開始直接遞迴乘/除結果吃TLE，所以這題很明顯要用分治去處理。 2.指數的特性，3^11 可以被表示為 3 * 3^2 * 3^8，其中因為拆分完的指數欄位必定能被二進位表示，上式可被轉為：3 * (3^1)^2 * (3^4)^2 也就是說我們如果有一個快速的方法可以求出 3 的 2^k 次方，本來需要 n 次乘法才能完成的運算可以被簡化為 O(logn) 次。 3.觀察上式我們可以發現平方裡面的元素都是上一個元素的平方，所以我們只需把指數欄位的值轉成二進制值，再把x從小到大不斷取平方，並和二進位值匹配即可。 4.取負的次方只要把 x 倒數就好，然後因為 n 超大直接取負數會溢位我兔了== ---------------------------------------------------------------- class Solution { public double myPow(double x, int n) { if (n == 0) { return 1; } long exp = n; if (n < 0) { x = 1 / x; exp *= -1; } double res = 1; while (exp > 0) { if (exp % 2 == 1) { res *= x; } x *= x; exp /= 2; } return res; } } ---------------------------------------------------------------- -- https://i.imgur.com/bFRiqA3.jpg