剑指Offer（2）6-10题

第6题：旋转数组的最小数字

题目描述： 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 思路： 第一个想到的方法肯定是遍历，每次遍历的时候比较arr[cur]和arr[cur+1]，如果出现arr[cur]>arr[cur+1]，那么arr[cur+1]就是最小的。不过这种方法肯定是不行的，时间复杂度是O（n）。 那么可以采用二分查找的方法。如果arr[mid]>arr[right]的话，说明最小值肯定在右边，那么left=mid+1。如果arr[mid]<=arr[right]的话，说明最小值在左边，right=mid。这里right不能=mid-1，因为如果最后只剩两个元素的话，right和left就重合了。

public class Solution { public int findMin(int[] arr,int left, int right){ while(left < right){ int mid = left + (right - left)/2; if(arr[mid] > arr[right]){ left = mid+1; } else{ right = mid; } } return arr[left]; } public int minNumberInRotateArray(int [] array) { if(array.length == 0){ return 0; } int res; res = findMin(array, 0, array.length-1); return res; } }

一开始二分我是用递归写的，时间跑不过去。。后来修改成，直接改下标的形式就过了。说明能避免递归的时候，用循环比较好，递归的开销是很大的。

第7题：裴波那切数列

题目描述： 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 n<=39 思路：不能用递归，会超时，用循环。

public class Solution { public int Fibonacci(int n) { int[] res = {0,1}; if(n < 2) { return res[n]; } int fibNMinusOne = 1; int fibNMinusTwo = 0; int fibN = 0; for(int i = 2;i <= n; i++) { fibN = fibNMinusOne + fibNMinusTwo; fibNMinusTwo = fibNMinusOne; fibNMinusOne = fibN; } return fibN; } }

第8题：跳台阶

题目描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 思路： 其实也是一种裴波那切数列。最后一个台阶肯定是必须跳的，那么在这之前的一个状态，青蛙有可能是在n-1个台阶，也有可能在n-2个台阶，只有这两个可能。

public class Solution { public int JumpFloor(int target) { if(target == 1){ return 1; }else if (target == 2){ return 2; } return JumpFloor(target - 1) + JumpFloor(target - 2); } }

第9题：变态跳台阶

题目描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 思路： 这个题看起来是很变态。其实可以通过数学找规律找出一个公式f(n)=2*f(n-1),不过还是有点麻烦。 其实对于每个台阶来说，只有跳或者不跳2种选择，最后一个台阶是必须要跳的。所以一共有2^n-1种选择。

public class Solution { public int JumpFloorII(int target) { //每个台阶只有跳或者不跳2种选择，最后一个台阶必须跳 //所以一共有2的n-1次方种选择 return 1<<--target; } }

第10题：矩形覆盖

题目描述： 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？ 思路：首先如果n=1，即2*1的矩形，只有一种方法。n=2，即2*2的矩形，有横着放2个，和竖着放2个，2种方法。如果是2*n的矩形的话，如果在最边缘，竖着放一个的话，那么剩下的正好是2*（n-1）的一个矩形。如果横着放一个的话，下面的那2个格子只能那么放，没有其他选择，那么剩下的正好是2*（n-2）的一个矩形。所以f(n)=f(n-1)+f(n-2)。

public class Solution { public int RectCover(int target) { if(target < 1){ return 0; } if(target == 1){ return 1; } else if(target == 2){ return 2; } else{ return RectCover(target - 1) + RectCover(target - 2); } } }