LintCode--剑指offer第1--10题

1. Fizz Buzz 问题:

给你一个整数n. 从 1 到 n 按照下面的规则打印每个数：

• 如果这个数被3整除，打印fizz.
• 如果这个数被5整除，打印buzz.
• 如果这个数能同时被3和5整除，打印fizz buzz.

样例:
比如 n = 15, 返回一个字符串数组：

[
  "1", "2", "fizz",
  "4", "buzz", "fizz",
  "7", "8", "fizz",
  "buzz", "11", "fizz",
  "13", "14", "fizz buzz"
]

解答：

public class Solution {
    /*
     * @param n: An integer
     * @return: A list of strings.
     */
    public List<String> fizzBuzz(int n) {
        // write your code here
        ArrayList<String> results = new ArrayList<String>();
        for (int i = 1; i <= n; i++) {
            if (i % 15 == 0) {
                results.add("fizz buzz");
            } else if (i % 5 == 0) {
                results.add("buzz");
            } else if (i % 3 == 0) {
                results.add("fizz");
            } else {
                results.add(String.valueOf(i));
            }
        }
        return results;
    }
}

2.斐波纳契数列:

查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指：

• 前2个数是 0 和 1 。
• 第 i 个数是第 i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

样例:

给定 1，返回 0
给定 2，返回 1
给定 10，返回 34

解答1：

class Solution {
    public int fibonacci(int n) {
        if (n == 1) {
            return 0;
        } else if (n == 2) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

这个算法会出现时间超出错误，原因是要计算fn,就要计算fn-1和fn-2，而要计算fn-1，就要计算fn-2和fn-3，依次类推。
改进如下：

解答2：

public class Solution {
    /*
     * @param n: an integer
     * @return: an ineger f(n)
     */
    public int fibonacci(int n) {
        // write your code here
        int fibone=0;
        int fibtwo=1;
        int fibn=1;
       if(n==1){
           return 0;
       }else if(n==2){
           return 1;
       }else{
            for (int i = 3; i <= n; i++) {
                fibtwo = fibone;
                fibone = fibn;
                fibn = fibone + fibtwo;
            }
           return fibn;
       }
    }
}