leecode#x平方根#爬楼梯

题目描述：

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。 

分析：

法一「袖珍计算器算法」是一种用指数函数 exp 和对数函数 ln 代替平方根函数的方法。

代码：

import math
#x的算术平方根
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        ans = int(math.exp(0.5 * math.log(x)))
        return ans+1 if (ans+1)**2 <= x else ans
 
s = Solution()
a = s.mySqrt(15)
print(a)

分析：

法二：二分查找法：由于 x 平方根的整数部分ans 是满足 k^2 ≤x 的最大 k 值，因此我们可以对 k进行二分查找，从而得到答案。

二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x的大小关系，并通过比较的结果调整上下界的范围。

代码：

class Solution:
    def mySqrt(self, x: int) -> int:
        a,b,ans = 0,x,-1
        while a <= b:
            mid = (a + b)//2
            if mid * mid <= x:
                ans = mid
                a=mid + 1
            else:
                b=mid - 1
        return ans

返回int类型函数时：

return 0：一般用在主函数结束时，按照程序开发的一般惯例，表示成功完成本函数。
return -1：:表示返回一个代数值，一般用在子函数结尾。按照程序开发的一般惯例，表示该函数失败；

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析：

动态规划：f(x）表示爬到第x级台阶的方案数，f(x) = f(x-1) + f(x-2),意味着爬到第x阶方案数等于x-1阶加上x-2阶方案数。f(0)=1,f(1)=1,表示从0级爬到0级一种方案，从0级爬到1级1种方案。有了这两个边界条件，就可以向后推导n级正确结果。

代码：

class Solution:
    def climbStairs(self, n: int) -> int:
        a,b,c,i= 0,0,1,1
        while(i <= n):
            a = b         #a表示爬o级台阶，b表示爬1级台阶
            b = c
            c = a + b
            i += 1
        return c