国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode] Pow(x, n) [Binary Search]

ideaa / 3431人閱讀

摘要:無須考慮為的情況,直接轉化成正數計算倒數。需要注意的情況,取負數之后會溢出。

Problem

Implement pow(x, n).

Example

Pow(2.1, 3) = 9.261
Pow(0, 1) = 0
Pow(1, 0) = 1

Note

You don"t need to care about the precision of your answer, it"s acceptable if the expected answer and your answer "s difference is smaller than 1e-3.

Challenge

O(logn) time

Solution Update 2018-9
class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        double half = myPow(x, n/2);
        if (n % 2 == 0) return half*half;
        else {
            if (n < 0) return 1/x*half*half;
            else return x*half*half;
        }
    }
}

When you see O(logn) time for a obvious O(n) time question, think about binary search and recursion.

Double myPow()

無須考慮n為Integer.MIN_VALUE的情況,直接轉化成正數計算倒數。

public class Solution {
    public double myPow(double x, int n) {
        if (n < 0) return 1/pow(x, -n);
        else return pow(x, n);
    }
    private double pow(double x, int n) {
        if (n == 0) return 1;
        double val = pow(x, n/2);
        if (n % 2 == 0) return val*val;
        else return val*val*x;
    }
}
Double x

需要注意n = Integer.MIN_VALUE的情況,取負數之后會溢出。

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n < 0) {
            if (n == Integer.MIN_VALUE) {
                n++;
                return 1/(myPow(x, Integer.MAX_VALUE)*x);
            }
            n = -n;
            x = 1/x;
        }
        return (n%2 == 0) ? myPow(x*x, n/2): x*myPow(x*x, n/2);
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65503.html

相關文章

  • [LintCode] Remove Node in Binary Search Tree [理解BS

    Problem Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You sho...

    陳江龍 評論0 收藏0
  • [LintCode] Search Range in Binary Search Tree

    摘要:重點是根據的性質,先左后根最后右。另一重點是,函數和函數都要用的的參數,記得在函數外層定義。 Problem Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. pr...

    draveness 評論0 收藏0
  • [LintCode/LeetCode] Search for a Range [左右邊界法/一次循環

    摘要:首先,建立二元結果數組,起點,終點。二分法求左邊界當中點小于,移向中點,否則移向中點先判斷起點,再判斷終點是否等于,如果是,賦值給。 Problem Given a sorted array of n integers, find the starting and ending position of a given target value. If the target is not...

    zhangrxiang 評論0 收藏0
  • [LintCode] Insert Node in a Binary Search Tree

    摘要:建立兩個樹結點,先用找到在的位置,讓作為的根節點找到的位置后,指向。此時,用代替與連接就可以了。 Problem Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tr...

    Taste 評論0 收藏0
  • [LintCode] Binary Search Tree Iterator

    摘要:建立一個堆棧,先將最左邊的結點從大到小壓入棧,這樣的話,為了實現迭代即返回下一個的函數就要考慮右邊的結點。如此,實現函數。 Problem Design an iterator over a binary search tree with the following rules: Elements are visited in ascending order (i.e. an in-o...

    silencezwm 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<