Re: [閒聊] 每日LeetCode

: 思路： : 1.一開始直接遞迴乘/除結果吃TLE，所以這題很明顯要用分治去處理。 一開始吃overflow的： class Solution { public: double myPow(double x, int n) { if (n == 0) return 1; if (n > 0) return x * myPow(x, n - 1); if (n < 0) return 1 / (x * myPow(x, -(n + 1))); return x; } }; : 2.指數的特性，3^11 可以被表示為 3 * 3^2 * 3^8，其中因為拆分完的指數欄位 : 必定能被二進位表示，上式可被轉為：3 * (3^1)^2 * (3^4)^2 : 也就是說我們如果有一個快速的方法可以求出 3 的 2^k 次方，本來需要 n 次乘法 : 才能完成的運算可以被簡化為 O(logn) 次。 後面改成處理奇數偶數 class Solution { public: double myPow(double x, int n) { if (n == 0) return 1; if (n < 0) return 1 / (x * myPow(x, -(n + 1))); if (n % 2 != 0) return x * myPow(x, n - 1); return myPow(x * x, n / 2); } }; 變成每次計算一半 n偶數就兩個一半相乘 (x * x, n / 2) n奇數就是這次的次方減一去算偶數結果 再乘一個自己 (x * (x * x, n-1 / 2)) --
※ 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1690210509.A.D60.html

推 Rushia: 大師 07/24 23:04