之前提到的，打算把国庆期间复习的笔记，整理贴出来一部分有意思的题目，虽然有些比较基础，但更不可掉以轻心。

- Fibonacci 数列 — 《剑指offer》

首先大家都知道，Fibonacci数列计算公式如下：

最先想到的就是递归吧：

1
2
3
4
5
6
7
8
9

private static long  Fibonacci(int n) {
	if (n <= 0) {
		return 0;
	}if (n == 1) {
		return 1;
	}
	
	return Fibonacci(n-1) + Fibonacci(n-2);
}

但这样递归的效率不高，简单分析一下，比如计算 Fibonacci(10) 的时候，你计算 Fibonacci(10) 会调用 Fibonacci(9) + Fibonacci(8)，而 Fibonacci(9) 又会调用 Fibonacci(8) + Fibonacci(7) … 不难发现，Fibonacci(8) 在这里存在重复调用、计算，类似的还有其他 Fibonacci 调用也存在重复情况。而且 n 越大，重复调用越多，效率越低。我在 eclipse 上试着运行 Fibonacci(100) ，结果 eclipse 半天都不出结果，而且风扇转得很快。

所以这种方法，虽然简单，但实际上不可行，在笔试面试中用这种方法，估计得分很低。通过上面的分析，我们有一个思路，就是避免重复调用，最好能利用已经计算过的中间项，于是就有了迭代法，也可以理解为辗转相加：

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

private static long Fibonacci2(int n) {

	if (n <=0 ) {
		return 0;
	}
	if (n == 1) {
		return 1;
	}
	
	long fOne = 1;
	long fTwo = 0;
	long fN = 0;
	for (int i = 2; i <= n; i++) {
		fN = fOne + fTwo;
		fTwo = fOne; //辗转相加
		fOne = fN;
	}
	return fN;
}

再用 eclipse 测试，很快得到结果：

- 求二进制中1的个数

这道题也是再烂大街不过了，腾讯面试的时候被问过，百度笔试题也有考到，然后在《剑指offer》里面也看到了。题目大概意思就是

输入一个整数，然后把整数用二进制表示，求出该二进制中 1 的个数。例如输入整数 10，10 的二进制表示为 1010 , 1 的个数为 2， 那么输出结果即为 2.

要求 1 的个数，就需要整数n 与 1 按位与 n&1. 第一种方法是，把整数从最末位开始，逐个往右移，并与 1 做 & 运算，即：

1
2
3
4
5
6
7
8
9
10
11

int Count1(int n)  
{  
    int count = 0;  
    while (n)  
    {  
        if ( n&1 )
        	count++;
        n >>= 1;  
    }  
    return count;  
}

这种方法有一个问题，就是当 n 为负数(n < 0) 的时候，不但不能得到正确的结果，还将导致死循环。以负数 0x80000000 为例，负数右移一位并不是简单地把最高位的1移到第二位变成 0x40000000，而是 0xC0000000 （这是因为移位前是个负数，移位后要保证仍然是个负数， 因此移位后的最高位会设为1）。如果一直做右移运算，最终这个数字就会变成 0xFFFFFFFF 而陷入死循环。

第二种方法，我们不移动整数 n 了，我们移动 1，每次使 1 左移一位，并与整数 n 做 & 运算。

1
2
3
4
5
6
7
8
9
10
11
12

int Count2(int n)
{
      int count = 0;
      unsigned int flag = 1;
      while (flag)
      {
            if(n & flag)
                  count ++;
            flag <<= 1;
      }
      return count;
}

因为 1 始终是正整数，不会存在负数最高位补1的情况。这个方法也是我一直在用的方法，笔试面试遇到的时候都是写的这个。

但在《剑指offer》一书中，还记录了一种思路，并且认为这比前面两个思路都要好。如果一个整数不为0，那么这个整数至少有一位是1. 如果我们把这个整数减去1，那么原来处在整数最右边的1就会变成0，原来在1后面的所有的0都会变成1，其余的所有位将不受到影响。

例如：一个二进制数1100，从右边数起的第三位是处于最右边的一个1。减去1后，第三位变成0，它后面 的两位0变成1，而前面的1保持不变，因此得到结果是1011。

我们发现减1的结果是把从最右边一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位 开始所有位都会变成0。如 1100&1011=1000. 也就是说，把一个整数减去1，再和原整数做与&运算，会把该整数最右边一个1变成0. 那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

1
2
3
4
5
6
7
8
9
10
11
12

int Count3(int n)
{
    int count = 0;

    while (n)
    {
        count++;
        n = (n - 1) & n;
    }

    return count;
}

网上还有其他方法，比如查表法、平行法、×86指令法 等等，有兴趣的可以深入研究。

- String

这段代码，你觉得会输出什么？

1
2
3
4
5
6
7

public static void main(String[] args) {
	
	String s1;
	
	System.out.println("s1 = " + s1);
	
}

答案是，编译不通过，Java 局部变量必须初始化。

下面这个呢？

1
2
3
4
5
6
7

public static String s2;

public static void main(String[] args) {
			
	System.out.println("s2 = " + s2);
	
}

是 s2 = 还是s2 = null ？ 答案是后者，对于静态全局变量，String 型静态变量初始化为 null, short、int、long、byte型初始化为 0. float、double 型初始化为 0.0. char 型初始化为空（不是null）. boolean 型初始化为 false.

先写到这里 :)