推 SecondRun: 大師 07/24 22:46
推 scmono: 大師 07/24 22:46
推 Che31128: 太狠@@ 07/24 22:47
推 ririoshi: 大師 07/24 22:48
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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1690209865.A.BAF.html