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

ideaa 发布于2019-08-14 15:15 / 3430人阅读

摘要：无须考虑为的情况，直接转化成正数计算倒数。需要注意的情况，取负数之后会溢出。

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);
    }
}

云服务器 GPU云服务器 binary-search binary-search-tree LintCode POW

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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...

陈江龙 2019-08-14 15:33 评论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 2019-08-14 15:12 评论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 2019-08-14 15:41 评论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 2019-08-14 15:33 评论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 2019-08-14 15:33 评论0 收藏0