手写算法: x 的平方根

69. x 的平方根

思路

1. 理解题意：求算数平方根，只保留整数部分，小数舍去

2. 可以看作是x^2 <= y, 求 x 的最大值就可以了，那么可以用二分查找法来解决此问题。

3. 二分查找需要设定边界，下界为 0，上界可以粗略设为 x，只要比较中位数 mid^2 与 x 的大小关系，通过比较结果调整上下界的范围，就可以了。

4. 求 mid，mid = left + ((right - left) >> 1) 与 mid = left + Math.ceil((right - left) / 2),这两个的不同点是，一个向下取整 Math.floor,一个向上取整 Math.ceil。

可以拿实际数字带入，这样容易理解，如 left 为 3， right 为 7，现在求中位数。那么肯定是（right - left）/ 2， 再向上取整，但是 left 是从 3 开始，所以还要加上 left，即 left + Math.ceil((right - left) / 2)

/**
 * @param {any} x
 * @return {number}
 */
function mySqrt(x) {
  if (x < 0 || isNaN(x) || typeof x !== 'number') return NaN;

  let left = 0,
    right = x;
  while (left < right) {
    const mid = left + Math.ceil((right - left) / 2);
    const square = mid * mid;
    if (square <= x) {
      left = mid;
    } else {
      right = mid - 1;
    }
  }
  return left;
}

位运算知识巩固

根据二进制计算，向左/右移动

• << : 左移运算符，num << 1, 相当于 num * 2, 结果向下取整

• >> : 右移运算符，num >> 1, 相当于 num \ 2, 结果同样是向下取整

• >>> : 无符号右移，忽略符号位，空位都以 0 补齐

手写题: 实现_.chunk()

131. 实现_.chunk()

解法一： 使用Array.prototype.slice()浅拷贝数组，不会改变原数组

function chunk(items, size) {
  if (size < 1) return [];
  let result = [];

  for (let i = 0; i < items.length; i += size) {
    result.push(items.slice(i, i + size));
  }
  return result;
}

解法二：使用模

function chunk(items, size) {
  let result = [];
  if (size < 1) return result;

  for (let i = 0; i < items.length; i++) {
    const j = i % size;
    if (j === 0) {
      result.push([]);
    }
    const last = result[result.length - 1];
    last[j] = items[i];
  }
  return result;
}