剑指Offer(2)6-10题

xiaoxiao2021-02-28  36

第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); } } }
转载请注明原文地址: https://www.6miu.com/read-2800246.html

最新回复(0)