变强日记5

主要内容

1. Java接口和抽象类的区别是什么？
2. 快速幂算法

Java接口和抽象类的区别是什么？

什么是接口？

接口是方法的集合。接口不是类。接口不能用于实例化对象，接口也没有构造方法，接口中的所有方法必须是抽象方法，接口不能包含成员变量，除了static和final修饰的变量。

什么是抽象类？

如果一个类中没有包含足够的信息来描绘一个具体的对象，这样的类就是抽象类。抽象类除了没法直接被实例化之外，与普通的类没有什么区别，它依然有构造器*，成员变量，成员方法。抽象类因为不能被直接实例化，因此抽象类是用来继承的。

它们的区别

1. 接口中的所有方法都必须是抽象方法，但是抽象类可以同时包含抽象和非抽象的方法。
2. 类可以实现多个接口，但是只能继承一个抽象类。
3. 接口中声明的成员变量默认都是final的，而抽象类没有这个限制。
4. 接口中的方法默认是public的，而抽象类中的方法可以任意指定。
5. 抽象类可以在不实现接口方法的情况下实现接口。

快速幂算法

题目描述：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    public double Power(double base, int exponent) {
       double result=1;
       boolean flag=true;
       if(exponent<0){
           flag=false;
           exponent*=-1;
       }
       while (exponent>0){
           if(exponent%2==0){
               exponent=exponent/2; //指数缩小为原来的一半
               base*=base; //底数扩大为原来的平方
           }else {
               //指数为奇数的情况
               exponent--;//将指数化为(偶数+1)的形式
               result=result*base;//计算分离上面出来的那个一次方
               exponent/=2;
               base*=base;
           }
       }
        return flag?result:1/result;
  }
}

分析：
在进行幂运算的时候，最简单的方式就是利用循环。想要实现“快速”就得从减少循环的次数入手。首先看一组举例：

1
2
3
4
5
6
7
8

//计算2的8次方，需要循环8次，而其等价写法
//4的4次方只需要4次循环，这就是减少循环次数优化
//幂计算的基本思路。我们通过变化，不断减小幂，增加第
//从而使得循环次数不断减少
2^8=(2^2)^(4)

//当不是所有的幂都能被2整除的，这个时候我们需要一点小小的变换技巧
2^7=(2^2)^(3)*2

这些变换的技巧基本属于初中数学的范畴，我们只需要注意幂为偶数，和奇数的两种情况即可。