力扣网简单题：加一，二进制求和、x 的平方根

1. 加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    // 我的想法是在处理数组之前就判断数组是不是全部是9，如果全部是9，在加完1后，需要在首位拼一个1作为进位。
    let flag = true;
    digits.forEach(v => {
        if(flag){
            if(v !== 9){
                flag = false; 
            }
        }
    })
    // 从后往前遍历
    for(i = digits.length - 1; i => 0;i--){
        if(digits[i] === 9){
            digits[i] = 0
        }else{
            // 当不为9时，加一后就结束循环。
            digits[i]++;
            break;
        }
    }
    //如果全部是9如，[9],[9,9]处理后会变成[0],[0,0]。需要拼接一个[1]
    if(flag){
        return [1].concat(digits)
    }
    return digits;
};

2.二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

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

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let arrA = a.split('')
    let arrB = b.split('')
    let len = arrA.length < arrB.length ? arrB.length : arrA.length
    let c = 0
    let result = ''

    for(let i = len - 1; i >= 0 || c > 0; i--) {
        
        let curA = arrA.pop()
        let curB = arrB.pop()

        if(curA) {
            c += parseInt(curA)
        }
        if(curB) {
            c += parseInt(curB)
        }
        result = (c % 2) + result
        c = c > 1 ? 1 : 0
    }
    return result
};

3. x 的平方根

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

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

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

例 1：

输入：x = 4
输出：2

示例 2：

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

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
  // 第一种方法，从0开始循环，当平方大于x，那就是此时循环的值减去1.
  // let res = 0;
  // if(x < 2){
  //     return x
  // }
  // if(x === 2){
  //     return 1
  // }
  // for(let i = 0;i<x;i++){
  //     if(i*i>x){
  //         res = i;
  //         break
  //     }
  // }
  // return res - 1;
  // 第二种方法，二分法，每次循环重新计算中间位置，不断缩小范围
  let left = 0;
  let right = x;
  let mid;
  while(left <= right){
    mid = Math.ceil((left+right)/2);
    if(mid*mid === x){
      return mid;
    }else if(mid*mid < x){
      left = mid + 1;
    }else{
      right = mid -1;
    }
  }
  return right
};