Lumos学习python第六课：算法初体验

一、老规矩，上题！

1、题目-----来源力扣

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = "11", b = "1"
输出："100"

示例 2：

输入：a = "1010", b = "1011"
输出："10101"

提示：

1 <= a.length, b.length <= 104

a 和 b 仅由字符 '0' 或 '1' 组成

字符串如果不是 "0" ，就不含前导零

题解

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        a1 = int(a,base = 2)
        b1 = int(b,base = 2)
        c = "{0:b}".format(a1+b1)
        return c

2、题目-----来源力扣

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

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

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

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

• 0 <= x <= 231 - 1

题解

class Solution:
    def mySqrt(self, x: int) -> int:
        y = x
        while x>=0:
            y = y // 2
            z = y * y
            if x==1:
                return 1
                break
            elif z > x:
                continue
            elif z == x:
                return y
                break
            else:
                for i in range(y+1,x+1,1):
                    res = i * i  
                    if res < x:
                        continue
                    elif res == x:
                        return i
                        break
                    else:
                        return i-1
                        break
                break

今天两道题哈，第二道题大家单看代码来说，稍微复杂些，但是算法思想非常简单，首先思考一种适用性强的算法，再考虑特殊情况。就本题而言，题干中要求我们不能使用函数（否则，一行代码就搞定），所以考虑一下底层的算法。根据给定的非负整数，通过试结果找到正确答案，因为题目要求不是精准结果，要求开平方数等于精确结果的整数部分即可，那么通过依次试结果就可以找到，试结果的原则是：每次将给定的数x除以2得到y1，再进行平方得到y2，与给定数x比大小，若y2≥x，重新循环上次规则（y1除以2，再进行平方），至到y2≤x，再对y1进行＋1试根，直到平方结果最大限度接近于x，返回具体值即可。然后需要考虑不适用于这种规则的特殊情况，写几个条件语句，一般都会是比较小的数，比如0、1、2......这样结果就比较完备，是不是，思想很简单，你用小脑袋瓜稍微思考一下就明白了。

接下来给一种经典算法：二分查找

二分查找，也称为折半查找，是一种高效的查找方法。它基于分治策略，利用数据的有序性，每次将搜索范围缩小一半，直至找到目标元素或搜索区间为空。

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

经典算法之所以经典，是因为简单通俗而不失精确。

二、算法

1、基本定义

计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述。我理解其实就是用计算机语言体验数学算法。

2、算法与函数

算法是可以用构造性方式定义的函数。

虽然我们的编程工作多数时候都是基于调用那些预先封装好的接口和软件开发工具包（SDK），但是，如果我们能深入了解底层的算法与数据结构的实现方式，我们便能更清晰地判断，在何种具体情境下应该选择使用哪种底层工具。算法的价值不仅仅在于编写，更重要的是其能在任何需要的时刻为我们计算出问题的答案。因此，我们需要将算法进行单独的封装，通过调整参数来改变输入的数据，从而得到我们期望的结果。换句话说，为了真正实现算法的复用，我们需要将其编写成可重复使用的函数形式。

算法和数据结构就是计算机科学与技术的立身之本，学好，就可以学好计算机！！！加油，各位。