坚持写算法题的第四周（四）

//第一个超时
class Solution1:
    def isPerfectSquare(self, num: int) -> bool:
        if num == 1:
            return True
        for i in range(1,num//2+1):
            if i*i == num:
                return True
        return False
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        x = 1
        square = 1
        while square <= num:
            if square == num:
                return True
            x += 1
            square = x * x
        return False

class Solution:
    def numWays(self, n: int) -> int:
        if n == 0:
            return 1
        dp = {}
        dp[1] = 1
        dp[2] = 2
        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]%1000000007

class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a % 1000000007

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        low, high = 0, len(numbers) - 1
        while low < high:
            pivot = low + (high - low) // 2
            if numbers[pivot] < numbers[high]:
                high = pivot 
            elif numbers[pivot] > numbers[high]:
                low = pivot + 1
            else:
                high -= 1
        return numbers[low]

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        res = []
        for i in range(1,10**(n)):
            res.append(i)
        return res