Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
想請問leetcode上,請問是有宣告變數效能就會降低嗎?
解法1:
var mySqrt = function(x) {
return Math.pow(x,1/2).length>1?Math.pow(x,1/2):Math.floor(Math.pow(x,1/2));
};
Runtime: 92 ms
Memory Usage: 38.1 MB
解法2:
var mySqrt = function(x) {
var a= Math.pow(x,1/2);
return a.length>1?a:Math.floor(a);
};
Runtime: 104 ms
Memory Usage: 38.3 MB
已邀請的邦友 {{ invite_list.length }}/5
2020/09/14 更新
以 V8 引擎而言，當你宣告變數並存入值時，他會做兩件事情：
所以理論上來說自然會占用到記憶體的部分。
至於更加詳細解釋的部分，這裡推薦你閱讀這份系列文章，這系列文章透過 Node.js 中 --print-bytecode 指令來去查看最後產出的 Bytecode 藉以探討更底層的運作，但我想這可能會依不同引擎背後的實作而論。
但從實作上來說，JavaScript 比較要在意的應該會是物件上的 Memory Leak，因為記憶體如何分配並不是我們能控的，而基於瀏覽器的運作的話，瀏覽器也會幫忙做 Garbage Collection，所以比起這部分的 Memory Usage、Runtime，我會覺得可讀性會更重要 XD
原文這題其實要考慮到的點有很多，第一個是在很多 OJ 的系統上，那些時間如果沒有差太多（例如說 100ms 跟 200ms 的差距），可以視為是系統的計算誤差，有可能你多試幾次，秒數就變快或是變慢了
第二個是要考慮到 compiler，有些程式碼經過 compiler 優化以後會跟你想的不一樣，並不是光看程式碼本身就能夠推出來的。以原文的解法來說，第一種 Math.pow(x,1/2) 算了兩次，解法 2 只算了 1 次，我以常識去推論會認為第二種比較快，因為計算量較少
但結果秒數上面是第一種比較快，所以可以合理猜測可能是
(1) 系統誤差，差距太小可以視為一樣，可以把測資變大，看看差距是否一樣
(2) 編譯器做了一些神奇的事
huli謝謝尼的解說
如果可以使用 Math 的 function 的話
不如直接給他 sqrt 算了
var mySqrt = function(x) {
return parseInt(Math.sqrt(x)+"");
}
如果不使用內建函式
整數開方可以用二進位版本的直式開根號來做
人在外面，回家有空再補上
補上code
var mySqrt = function(x) {
let r=0,
q=0;
for(let k=30;k>=0;k-=2) {
r=r<<2|x>>>k&3;
if((q<<2)<r) {
r-=(q<<2|1);
q=q<<1|1;
} else {
q=q<<1;
}
}
return q;
};
Runtime: 84 ms, Memory Usage: 38.2 MB
iThome鐵人賽
看影片追技術