剑指offer ------ 刷题总结

 1 class Solution {
 2     /**
 3      * @param n: an integer
 4      * @return an integer f(n)
 5      */
 6     public int fibonacci(int n) {
 7         // write your code here
 8         if (n == 1) {
 9             return 0;
10         }
11         if (n == 2) {
12             return 1;
13         }
14         return fibonacci(n - 1) + fibonacci(n  - 2);
15     }
16 }

 1 class Solution {
 2     /**
 3      * @param n: an integer
 4      * @return an integer f(n)
 5      */
 6     public int fibonacci(int n) {
 7         // write your code here
 8         Map<Integer, Integer> map = new HashMap<Integer, Integer>();
 9         return fibonacci(n, map);
10     }
11     public int fibonacci(int n, Map<Integer, Integer> map) {
12         if (n == 1) {
13             map.put(1, 0);
14             return 0;
15         }
16         if (n == 2) {
17             map.put(2, 1);
18             return 1;
19         }
20         int sum = 0;
21         if (map.containsKey(n - 1)) {
22             sum += map.get(n - 1);
23         } else {
24             int temp = fibonacci(n - 1, map);
25             map.put(n - 1, temp);
26             sum += temp;
27         }
28         if (map.containsKey(n - 2)) {
29             sum += map.get(n - 2);
30         } else {
31             int temp = fibonacci(n - 2, map);
32             map.put(n - 2, temp);
33             sum += temp;
34         }
35         return sum;
36     }
37 }

 1 class Solution {
 2     /**
 3      * @param n: an integer
 4      * @return an integer f(n)
 5      */
 6     public int fibonacci(int n) {
 7         // write your code here
 8         if (n == 1) {
 9             return 0;
10         }
11         if (n == 2) {
12             return 1;
13         }
14         int fibNMinusTwo = 0;
15         int fibNMinusOne = 1;
16         int fibN = 0;
17         for (int i = 3; i <= n; i++) {
18             fibN = fibNMinusTwo + fibNMinusOne;
19             fibNMinusTwo = fibNMinusOne;
20             fibNMinusOne = fibN;
21         }
22         return fibN;
23     }
24 }