每日Leetcode—算法（8）

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 阶 + 1 阶
2. 2 阶

输入： 3，输出： 3
解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 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]

分析：该问题是除了兔子问题之外，另一个满足斐波那契数列的问题，所以直接使用即可求出。