Mlog1-x的平方根 & x 的 n次幂

Author Avatar
Emily Chen 7月 03, 2019

2019-4-1

文章目录：

  1. 题目要求–分析
  2. 具体实现–动手
  3. 源码分析–知其然，知其所以然
  4. 算法质量
  5. 总结

1. 题目要求–分析

第一题：实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

第二题：实现 pow(x, n) ，即计算 x 的 n 次幂函数。
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

2. 具体实现–动手

第一题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int mySqrt(int x) {
         int result = 0;
		 if (x < 0) {
			 return x;
		 }
		 else if(x == 0) {
			 return 0;
		 }
		 else {
			 result = (int) Math.sqrt(x);
			 return result;
		 } 
    }
}

第二题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
	   	  public static double myPow(double x, int n) {
	        if(n < 0){
	            return 1/pow(x, -n);
	        } else {
	            return pow(x, n);
	        }
	    }
	    
	    private static double pow(double x, int n){
	       
	        if(n == 0){
	            return 1.0;
	        } 
	        if(n == 1){
	            return x;
	        }
	        double val = pow(x, n/2);
	        
	        if(n % 2 == 0){
	            return val * val;
	        } else {
	            return val * val * x;
	        }
	    }
}

3. 源码分析–知其然，知其所以然

思想上入门：先从简单的做起，给自己一点信心和做出来后的成就感。
行动上入门：拿到题目，先理清自己计算时的思路。然后按照思路把程序写出来。
第一题：

1
2
3
1、 x 是非负整数--出现分类讨论
2、计算 x 的平方根--Math.sqrt（）
3、返回类型是整数--int

第二题：
如果n是偶数，xn xn= x2n；
如果n是奇数，xn xnx=x2n+1；

4. 算法质量

时间 O(logN) ；空间 O(logN)。

5. 总结

  • 在这个世界上，不是每个国家、每个时代、每个人都有权利去追求自己所喜欢的未来。所以如果你侥幸可以，请不要错过。–吴晓波