資訊專欄INFORMATION COLUMN
摘要：無(wú)須考慮為的情況，直接轉(zhuǎn)化成正數(shù)計(jì)算倒數(shù)。需要注意的情況，取負(fù)數(shù)之后會(huì)溢出。
Problem
Implement pow(x, n).
ExamplePow(2.1, 3) = 9.261
Pow(0, 1) = 0
Pow(1, 0) = 1
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.
ChallengeO(logn) time
Solution Update 2018-9class 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()無(wú)須考慮n為Integer.MIN_VALUE的情況，直接轉(zhuǎn)化成正數(shù)計(jì)算倒數(shù)。
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的情況，取負(fù)數(shù)之后會(huì)溢出。
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);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65503.html
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...
摘要：重點(diǎn)是根據(jù)的性質(zhì)，先左后根最后右。另一重點(diǎn)是，函數(shù)和函數(shù)都要用的的參數(shù)，記得在函數(shù)外層定義。 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...
摘要：首先，建立二元結(jié)果數(shù)組，起點(diǎn)，終點(diǎn)。二分法求左邊界當(dāng)中點(diǎn)小于，移向中點(diǎn)，否則移向中點(diǎn)先判斷起點(diǎn)，再判斷終點(diǎn)是否等于，如果是，賦值給。 Problem Given a sorted array of n integers, find the starting and ending position of a given target value. If the target is not...
摘要：建立兩個(gè)樹(shù)結(jié)點(diǎn)，先用找到在的位置，讓作為的根節(jié)點(diǎn)找到的位置后，指向。此時(shí)，用代替與連接就可以了。 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...
摘要：建立一個(gè)堆棧，先將最左邊的結(jié)點(diǎn)從大到小壓入棧，這樣的話，為了實(shí)現(xiàn)迭代即返回下一個(gè)的函數(shù)就要考慮右邊的結(jié)點(diǎn)。如此，實(shí)現(xiàn)函數(shù)。 Problem Design an iterator over a binary search tree with the following rules: Elements are visited in ascending order (i.e. an in-o...
閱讀 2410·2021-11-23 09:51
閱讀 1221·2021-11-22 13:54
閱讀 3433·2021-09-24 10:31
閱讀 1100·2021-08-16 10:46
閱讀 3632·2019-08-30 15:54
閱讀 713·2019-08-30 15:54
閱讀 2896·2019-08-29 17:17
閱讀 3172·2019-08-29 15:08
