Leetcode-67. 二进制求和
题目：给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
如：
输入:a = “11”, b = “1”
输出：“100”
我们的思路是，首先要返回一个数组，先malloc一个char*数组，长度是要相加的两个数组中最长的那个还要+2，因为考虑到进位问题还有’ \0 '；然后依次从后面遍历，用flag和sum来记录进位的情况；
下面看代码和注释：
char* addBinary(char* a, char* b) { int la = strlen(a); int lb = strlen(b); //为创建一个新的数组做好长度准备 //这个长度要是a和b中最长的+2 //因为考虑到进1问题还有'0'，'0'占一个，还有一个预留出来预防进一 int max = la > lb ? la + 2 : lb + 2; int i = la - 1, j = lb - 1, k = max - 2; //开辟一个新的char*空间，最后返回去 char* p = (char*)malloc(sizeof(char) * max); assert(p); //最高位赋'0' p[0] = '0'; //最后一位赋'\0' p[max - 1] = '\0'; //flag用来记录进位的情况 //二进制中凡二进一，下面我们用sum来记录nums1（a[i]）和nums2（b[j]）还有flag的和的情况 //最后将sum中余的1赋给flag，若没有进位情况，flag应为0 int flag = 0; while (i >= 0 || j >= 0) { int nums1 = i >= 0 ? a[i] - '0' : 0; int nums2 = j >= 0 ? b[j] - '0' : 0; int sum = nums1 + nums2 + flag; p[k] = sum % 2 + '0'; flag = sum / 2; i--, j--, k--; } //如果循环已经结束，但是还有留下来的余1没处理 //由于上面k已经--，k已经走到下一位 //所以直接将1赋给p[k] if (flag != 0) { p[k] = '1'; } //如果最高为是'1'，证明进位的时候用到了最高位，就直接返回p if (p[0] == '1') { return p; } //如果最高位是'0'，证明没有用到最高位，返回p+1的数组 else { return p + 1; } }
Leetcode-69. x的平方根
题目：给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x** 0.5 。
- 暴力解法，i直接从0开始遍历
int mySqrt(int x) { long long i = 0; while (i * i <= x) { i++; } return i - 1; }
- 二分查找法
int mySqrt(int x) { //需要长整型，防止溢出 long long left, right; left = 1; right = x / 2; if (x == 1) return 1; while (left <= right) { //找到中间值，与x比较； //如果大了，将右边界缩小范围 //如果小了，将左边界往右移缩小答案范围 long long mid = left + (right - left) / 2; if (mid * mid == x) return mid; else if (mid * mid > x) right = mid - 1; else left = mid + 1; } return left - 1; }
