题目10-2 小青蛙跳台阶

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

这题就比较简单，思路和斐波那契数列是一样的，就直接贴代码了。注意当n=0时返回的1，大概意思是没台阶时小青蛙会原地跳一下以示尊重吧（大雾x

class Solution:
    def numWays(self, n: int) -> int:
        #对于台阶i的跳法，由台阶i-1和台阶i-2共同决定
        if n==0:
            return 1

        res = [1,1]
        for i in range(1,n):
            tmp = res[1]
            res[1] = sum(res)
            res[0] = tmp
        return res[1]%(10**9+7)
复制代码

题目11 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。 

思路

还是用二分，不过要小心判断mid指针究竟落在了哪种情况下。实际上旋转后的数组可以看成两个有序数组的拼接，且第二个有序数组的所有元素均不大于第一个数组的首元素，最小值一定是第二个递增区间的首元素（或者有重复元素），大概是这么个意思。

1. 如果mid大于right，那么说明此时mid位于第一个有序数组中，则最小值不可能落在mid和mid左边，因此将left = mid+1。
2. 如果mid等于right，此时并不能判断最小值是谁，但是能够排除最小值一定不是right。例如[2,3,1,1,1,1]，mid和right都是1，因此可以先把right去掉。
3. 如果mid小于right，此时mid一定落在第二个递增区间内，因此令right = mid即可。

代码

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        #return min(numbers)
        #实际上直接return min比自己写要快很多（x

        if not numbers:
            return []

        l = 0
        r = len(numbers)-1

        while l < r:
            mid = (l + r) // 2
            if numbers[mid] > numbers[r]:
                l = mid + 1
            elif numbers[mid] == numbers[r]:
                r = r - 1
            else:
                r = mid
        return numbers[l]
复制代码