数据结构与算法
剑指offer
JZ7 斐波那契数列
public int Fibonacci(int n) {
int one = 0;
int two = 1;
int result = 0;
if (n==0)
return 0;
if (n==1)
return 1;
for (int i=2;i<=n;i++)
{
result = one + two;
one = two;
two = result;
}
return result;
}
JZ8 跳台阶
//斐波那契思想
public int jumpFloor(int target) {
int one = 1;
int two = 2;
int result = 0;
if (target==1)
return 1;
if (target==2)
return 2;
for (int i=3;i<=target;i++)
{
result = one + two;
one = two;
two = result;
}
return result;
}
JZ9 跳台阶扩展问题
public int jumpFloorII(int target) {
return (int) Math.pow(2,target-1);
}
试题
1、构造器Constructor 是否可被override?
答：构造器Constructor 不能被继承，因此不能重写Overriding，但可以被重载Overloading。
2、两个对象值相同(x.equals(y) == true)，但却可有不同的hash code，这句话对不对?
答：不对，有相同的hash code。
3、是否可以继承String 类?
答：String 类是final 类，故不可以继承。
4、以下二条语句返回值为true 的有：
A：“beijing”==“beijing”；
B：“beijing”.equalsIgnoreCase（new String（“beijing”））；
答：A和B均为true。
5.下列哪一种叙述是正确的（ ）
A． abstract修饰符可修饰字段、方法和类
B． 抽象方法的body部分必须用一对大括号{ }包住
C． 声明抽象方法，大括号可有可无
D． 声明抽象方法不可写出大括号
答案：D
6、如下代码
public class Test {
public int aMethod() {
static int i = 0;
i++;
return i;
}
public static void main (String args[]) {
Test test = new Test();
test.aMethod();
int j = test.aMethod();
System.out.println(j);
}
}
输出结果是什么？
答案：编译失败。
7、equals与==的区别
答：==比较的变量（栈）内存中存放对象的堆内存地址，用来判断两个对象的地址是否相同，即是否指向同一个对象。
equals用来比较的两个对象的内容是否相等，由于所有的类都是继承自java.lang.Object类的，所以适用于所有对象，如果没有对该方法进行覆盖的华，调用的仍然是Object类中的方法，而Object中的equals方法返回的却是==的判断。
8、Hashcode的作用
答：java的集合有两类，一类是List，还有一类是Set。前者有序课重复，后者无序不重复。当我们在Set中2插入的时候怎么判断是否已经存在该元素呢，可以通过equals方法。但是如果元素太多，用这样的方法就会比较慢。
于是有人发明了哈希算法来提高集合中查找元素的效率，这种方式将集合分为若干个存储区域，每个对象可以计算出一个哈希码，可以将哈希码分组，每组分别对应某个存储区域，根据一个对象哈希码就可以确定该对象一个存储的那个区域。
hashCode方法可以这样理解：它返回的就是根据对象的内存地址换算出的一个值。这样一来，当集合要添加新的元素时，先调用这个元素的hashcode方法，就一下子能地位到它应该放置的物理位置上。如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存，不相同就散列其它的地址，这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。
9、String，StringBuffer和StringBuider的区别是什么？
答：String是只读字符串，它并不是基本数据类型，而是一个对象。从底层源码来看是一个ffinal类型的字符数组，所引用的字符串不能被改变，一经定义，无法再增删改。每次对String的操作都会生成新的String对象。
private final char values[];
每次+操作：隐式在堆上new了一个跟原字符串相同的StringBuilder对象，再调用append方法 拼 接+后面的字符。
StringBuffer和StringBuilder他们两都继承了AbstractStringBuilder抽象类，从
AbstractStringBuilder抽象类中我们可以看到
/**
* The value is used for character storage.
*/
char[] value;
他们的底层都是可变的字符数组，所以在进行频繁的字符串操作时，建议使用StringBuffer和StringBuilder来进行操作。 另外StringBuffer 对方法加了同步锁或者对调用的方法加了同步锁，所以是线程安全的。StringBuilder 并没有对方法进行加同步锁，所以是非线程安全的。
10、数组、ArrayList与LinkedList的区别
答：Array（数组）是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。Array获取数据的时间复杂度是O(1),但是要删除数据却是开销很大，因为这需要重排数组中的所有数据, (因为删除数据以后, 需要把后面所有的数据前移)。缺点: 数组初始化必须指定初始化的长度, 否则报错。
List—是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式，它继承Collection。
List有两个重要的实现类：ArrayList和LinkedList
ArrayList: 可以看作是能够自动增长容量的数组。
ArrayList的toArray方法返回一个数组。
ArrayList的asList方法返回一个列表。
LinkList是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于ArrayList.当然,这些对比都是指数据量很大或者操作很频繁。