2021-11-4
题目
1.有效的完全平方数
2.青蛙跳台阶
3.斐波那楔数列
4.旋转数组的最小数字
5.打印从1到n的最大的n位数
题解
1.有效的完全平方数
这个最少需要log（n）的复杂度才能过，o（n）就过不了，我把两个代码都发在下面了。
本题有多种解法，我用的时循环求解，找出最后的i。
2.青蛙跳台阶
这个就是第三题的那个解法，如果用递归的话这个题时会超时的，所以我们用记忆法来求解，大家可以直接看代码。
3.斐波那楔数列
同上。
4.旋转数组的最小数字
在升序表中找到突然下降的那个值就是这个表的最小值。
5.打印从1到n的最大的n位数
太简单了，没有题解。
代码
1.有效的完全平方数
//第一个超时 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
2.青蛙跳台阶
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
3.斐波那楔数列
class Solution: def fib(self, n: int) -> int: a, b = 0, 1 for _ in range(n): a, b = b, a + b return a % 1000000007
4.旋转数组的最小数字
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]
5.打印从1到n的最大的n位数
class Solution: def printNumbers(self, n: int) -> List[int]: res = [] for i in range(1,10**(n)): res.append(i) return res
