【Leetcode-67. 二进制求和-69.x的平方根】

简介: 【Leetcode-67. 二进制求和-69.x的平方根】

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 。

  1. 暴力解法,i直接从0开始遍历
int mySqrt(int x)
  {
      long long i = 0;
      while (i * i <= x)
      {
          i++;
      }
      return i - 1;
  }
  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;
  }
目录
相关文章
|
2月前
|
Java 编译器
LeetCode 190. 颠倒二进制位
LeetCode 190. 颠倒二进制位
25 0
【LeetCode-每日一题】-67. 二进制求和
【LeetCode-每日一题】-67. 二进制求和
|
1月前
|
SQL 算法 数据可视化
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
|
1月前
|
存储 SQL 算法
LeetCode题目67:二进制求和
LeetCode题目67:二进制求和
|
1月前
|
算法 Java Go
【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)
16 2
|
1月前
|
算法 Java Go
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
12 1
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
2月前
【力扣】67. 二进制求和
【力扣】67. 二进制求和
|
2月前
【力扣】69. x 的平方根
【力扣】69. x 的平方根