剑指offer（二）

剑指offer编程（6-10）

旋转数组中的最小数字

题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路一
直接遍历数组，如果一个数比前一个数小，该数即为最小，复杂度较高O（n）

代码实现

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if (len(rotateArray)==0):
            return 0
        min=rotateArray[0]
        for i in range(len(rotateArray)-1): #如果一个数比前一个数小，该数即为最小
            if (rotateArray[i]<min):
                min = rotateArray[i]
        return min

思路二
二分查找，复杂度为**O（logn）**需要考虑三种情况：

1. array[mid] > array[high]:
   出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。
   low = mid + 1
2. array[mid] == array[high]:
   出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边
   还是右边,这时只好一个一个试 ，
   high = high - 1
3. array[mid] < array[high]:
   出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
   边。因为右边必然都是递增的。
   high = mid

代码实现

class Solution2:
    def minNumberInRotateArray2(self, rotateArray):
        if(len(rotateArray)==0):
            return 0
        low=0
        high=len(rotateArray)-1
        while(low<high):
            mid=low+int((high-low)/2)
            if(rotateArray[mid]>rotateArray[high]):
                low=mid+1
            elif(rotateArray[mid]<rotateArray[high]):
                high=mid
            else:
                high=high-1
        return rotateArray[low]

斐波那契数列

题目描述
现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
0 ，1 ，1， 2， 3，5，8，13，21，34…

思路一
利用一个列表进行存储递归。

代码实现

class Solution:
    def Fibonacci(self, n):
        a=[0,1,1]        #前3项的值
        if n<3:
            return a[n]
        for i in range(3,n+1):
            a.append(a[i-2]+a[i-1]) #循环存入列表
        return a[n]

思路二
找规律，递归赋值。

代码实现

class Solution2:
    def Fibonacci(self, n):
        # write code here
        if n==0:
            return 0
        if n==1:
            return 1
        a,b = 0,1
        while n>0:
            a,b = b,a+b
            n-=1
        return a

跳台阶

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

思路
与上一题类似，通过列举，可以发现 $f\left[n\right]=f[n-2]+f[n-1]$f[n]=f[n−2]+f[n−1]

代码实现

class Solution:
    def jumpFloor(self, number):     #f[n]=f[n-2]+f[n-1],与斐波那契额数列类似
        result=[1,1]
        if number<2:
            return result[number]
        for i in range(2,number+1):
            result.append(result[i-2]+result[i-1])
        return result[number]
#方法二
class Solution2:
    def jumpFloor(self, number):
        # write code here
        a=1
        b=1
        while number>0:
            a,b = b,a+b
            number-=1
        return a

变态跳台阶

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

思路
通过列举找规律，发现 $f\left[n\right]=2^{n-1}$f[n]=2n−1

代码实现

class Solution:
    def jumpFloorII(self, number):  #找规律，f[n]=2的n-1次方
        if number<=0:
            return 0
        else:
            return pow(2,number-1)

矩形覆盖

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

思路
与跳台阶一样，通过列举，可以发现 $f\left[n\right]=f[n-2]+f[n-1]$f[n]=f[n−2]+f[n−1]​

代码实现

class Solution:
    def rectCover(self, number):   #还是斐波那契数列，f[n]=f[n-1]+f[n-2]
        if number == 0:
            return 0
        result = [1, 1]
        if number < 2:
            return result[number]
        for i in range(2, number + 1):
            result.append(result[i - 2] + result[i - 1])
        return result[number]
    
#方法二
class Solution2:
    def rectCover(self, number):
        # write code here
        if number == 0:
            return 0
        a=1
        b=1
        while number>0:
            a,b = b,a+b
            number-=1
        return a