Topic 10-2 Young frogs jump on the steps

A frog can jump up one step or two steps at a time. Find out how many ways the frog can jump up n steps.

This problem is relatively simple, the idea and Fibonacci sequence is the same, directly paste the code. Note the return 1 when n=0, presumably meaning that the frog will jump on the spot when there are no steps

class Solution:
    def numWays(self, n: int) - >int:
        Step I-1 and step I-2 will determine the jump method for step I
        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)
Copy the code

Problem 11 rotates the smallest number in the array

Moving the beginning elements of an array to the end of the array is called array rotation. Take a rotation of an incrementally sorted array and print the smallest element of the rotation array. For example, the array [3,4,5,1,2] is a rotation of [1,2,3,4,5], whose minimum value is 1.

Train of thought

I’m going to use binary, but be careful what kind of situation the mid pointer is in. In fact, the rotated array can be viewed as a concatenation of two ordered arrays, and none of the elements in the second ordered array is greater than or equal to the first element in the first array. The minimum value must be the first element (or duplicate element) in the second increment interval, something like that.

1. If mid is greater than right, then mid is in the first ordered array, and the minimum value cannot fall to the left of mid and mid, so left = mid+1.
2. If mid is equal to right, we can’t tell what the minimum is, but we can rule out that the minimum is not right. For example, [2,3,1,1,1,1], mid and right are both 1, so we can drop right first.
3. If mid is less than right, mid must be in the second increasing interval, so set right = mid.

code

class Solution:
    def minArray(self, numbers: List[int]) - >int:
        #return min(numbers)
        Return min is actually much faster than writing it (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]
Copy the code