算法复健-第一天

因为又报了某臭名昭著300元蓝桥杯，太久不写算法，虽然是暴力赛，但为了防止打水漂，还是每天写两道题复健一下

Math-Easy-二进制求和

题面

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

示例 1：

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

示例 2：

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

提示：

• 1 <= a.length, b.length <= 10^4
• a 和 b 仅由字符 '0' 或 '1' 组成
• 字符串如果不是 "0" ，就不含前导零

解答过程

这题显然要用字符串模拟，我们使用字符串模拟竖式的计算过程，先反转两个字符串以使两个数字对齐，然后从高位往低位遍历，把进位考虑在内就结束了

代码

string addBinary(string a, string b) {
        string ans;
        // 反转两个字符串
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        int n = max(a.size(),b.size()) , carry = 0;// carry用于保存进位
        for (size_t i = 0; i < n; i++)
        {
            carry += i < a.size() ? (a.at(i) == '1') : 0;
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            ans.push_back(carry % 2 + '0');
            carry /= 2;
        }
        if (carry)
        {
            ans.push_back('1');
        }// 处理首位的进位
        reverse(ans.begin(),ans.end());
        return ans;
    }

Math-Easy-x的平方根

题面

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

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

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

示例 1：

输入：x = 4
输出：2

示例 2：

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

提示：

• 0 <= x <= 2^31 - 1

解答过程

本题第一印象是打个暴力，很朴素的想到从1到x遍历每一个数字i，若这个数字i的平方大于x，则答案为i-1, 对i=1和i<4做特判，这样显然效率极低

不难想到优化方案：二分查找，下界为0，上界设定为x，我们比较中间元素mid的平方与x的大小关系，并通过比较调整上下界，最终得到结果，时间复杂度为O(logn)

当然也可以用指数函数和对数函数，利用换底公式计算平方根或者使用牛顿迭代法(泰勒级数来了)求解结果

代码

   int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2; // 计算中间元素
            if ((long long)mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }