剑指offer（二）

╰半橙微兮° 2022-02-18 11:27 151阅读 0赞

剑指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 \[ n \] = f \[ n − 2 \] + f \[ n − 1 \] f\[n\]=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 \[ n \] = 2 n − 1 f\[n\]=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 × 1 2 \\times 1 2×1的小矩形横着或者竖着去覆盖更大的矩形。  
请问用n个 2 × 1 2 \\times 1 2×1的小矩形无重叠地覆盖一个 2 × n 2 \\times n 2×n的大矩形，总共有多少种方法？

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

![1.png][]

**代码实现**

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

[1.png]: /images/20220218/1ca4195832ae4b07a8848889b94bf2a6.png