题目1 斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

代码

递归方法：

int Fibonacci(int n) { if(n==0) return 0; if(n==1||n==2) return 1; return Fibonacci(n-1)+Fibonacci(n-2);}

非递归方法：

int Fibonacci(int n) { int first = 0; int second = 1; int result = n; for(int i = 2; i<=n; i++){ result = first + second; first = second; second = result; } return result; }

题目2 青蛙跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

题目解析

对于这种问题我们可以这样分析。在第一次跳台阶的时候，它可以选择跳1个台阶，也可以选择跳两个台阶。对于它要跳n个台阶来说（设为f(n)），假如第一次跳了1个台阶，那么第二次跳就是f(n-1)的问题；假如第一次跳了2个台阶，那么第二次就是f(n-2)的问题。对于第二次跳也是如此，就是分别是f(n-2)和f(n-3)（对于第一次跳了1阶的情况下）、f(n-3)和f(n-4)（对于第一次跳了2阶的情况下），依次类推下去，成为一个递归。特别的，当n=1的时候，只有一种跳法（只跳一阶），当n=2的时候，有两种跳法（跳1阶跳两次，跳2阶跳一次）。实际上这就是一个斐波那契数列。

代码

int jumpFloor(int number) { if(number==1) return 1; else if(number==2) return 2; else return jumpFloor(number-1)+jumpFloor(number-2); }

题目3 变态跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目解析

当一个青蛙跳上n级台阶有以下的情况：

通过尝试，可以发现规律，当n>1的时候，f(n)=2*f(n-1)。

代码

 int jumpFloorII(int number) { if(number<1) return -1; else if(number==1) return 1; else return 2*jumpFloorII(n-1); }

题目4 矩形覆盖

题目描述

我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

题目解析

对于这种问题，我们还是需要进行分析。

当n=3的时候，我们发现，若固定了第三块砖的放置方式，那么前两块砖有两种放置方式（f(2)）；若固定了第二块和第三块的放置方式，则前一块砖有一种放置方式（f(1)）。以此类推，可以得出f(n)=f(n-1)+f(n-2)，当n>2的时候。

代码

int rectCover(int number) { if(number<=0) return 0; else if(number==1) return 1; else if(number==2) return 2; else return rectCover(number-1)+rectCover(number-2);}

题目5 二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

题目解析

思路很简单，利用与的特性：1&1=1，0&1=0就可以进行判断。

代码

 int NumberOf1(int n) { int count=0; for(int i=0;i<32;i++) //32位是由int决定 { if((n>>i)&1) count++; } return count; }

题目6 调整数组，使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

题目解析

其实这个可以借助于类似于冒泡法的思想，不过这样的复杂度有O(n²)，并且空间复杂度也较高。因此可以使用下面的方法。借鉴了插入排序。

代码

void reOrderArray(vector<int> &array) { for(int i = 0;i < array.size();i++){ for(int j = array.size()-1; j>i;j--){ if(array[j]%2==1&&array[j-1]%2==0) swap(array[j],array[j-1]); } } }