69.x的平方根
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
输入: 8，输出: 2
说明: 8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
算法一：
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
if x == 1:
return 1
for i in range(2,x+1):
if i**2<=x and (i+1)**2>x:
a = i
else:
return a
分析：该方法使用for循环进行查找，效率非常低
算法二：
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
if x == 1:
return 1
h = x
l = 0
while l<h:
m = (l + h)//2
if m**2<=x and (m+1)**2>x:
return m
if m**2 > x:
h = m
if m**2 < x:
l = m
分析：因为结果会从1,2,3...进行顺序查找，所以直接使用二分法。
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
输入： 2，输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
输入： 3，输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
算法：
def climbStairs(self, n: int) -> int:
res = [0]*(n+1)
res[0] = 1
res[1] = 1
for i in range(2,n+1):
res[i] = res[i-2] + res[i-1]
return res[n]
分析：该问题是除了兔子问题之外，另一个满足斐波那契数列的问题，所以直接使用即可求出。
