手写算法:第一个错误的版本

278. 第一个错误的版本

思路

1. 分析题意：找出第一个错误的版本，那么当前是正确版本的话，前面的都是正确版本，只有找到错误版本，该版本后面的就全是错误版本。题目提供单元测试，isBadVersion(version)来验证是否是错误版本

2. 题目说要尽量减少对 API 的调用，那么可以用二分查找，每次缩短为原来的一半 n(logn)

3. 设定左右边界，下届为 0，上界粗略设置为 n，那么可以找到中间版本 mid，检查中间版本是否为错误版本

• 如果是错误版本，那么右边都是错误版本，直接缩紧右边界，所以第一个错误版本的区间在 [left, mid] 中

• 如果是正确版本，那么左边都是正确版本，直接缩紧左边界，所以第一个错误版本的区间在 [mid + 1, right] 中

/**
 * Definition for isBadVersion()
 *
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
  /**
   * @param {integer} n Total versions
   * @return {integer} The first bad version
   */
  return function(n) {
    let left = 0,
      right = n;
    while (left < right) {
      let mid = left + ((right - left) >> 1);
      if (isBadVersion(mid)) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return right;
  };
};

手写题: 实现 parseToMoney

实现千位分隔符

// 保留三位小数
parseToMoney(1234.56); // return '1,234.56'
parseToMoney(123456789); // return '123,456,789'
parseToMoney(1087654.321); // return '1,087,654.321'

解法一：常规方法计算长度

function parseToMoney(num) {
  const [str, decimal] = `${num}`.split('.');

  const len = str.length;
  let count = len;
  let result = [];

  while (count >= 3) {
    result.unshift(str.slice(count - 3, count));
    count -= 3;
  }

  len % 3 && result.unshift(str.slice(0, len % 3));
  const ans = result.join(',').toString();
  return decimal ? `${ans}.${decimal}` : ans;
}

解法二：正则表达式

function parseToMoney(num) {
  return num.toString().replace(/\B(?=(\d{3})+(?!\d))/g, ',');
}

解析

e.g.1 num = 1234567890;

① /\B(?=(\d{3})+(?!\d))/g ：正则匹配非单词边界\B，即除了 1 之前的位置，其他字符之间的边界，后面必须跟着 3N 个数字直到字符串末尾;

② (\d{3})+ ：必须是 1 个或多个的 3 个连续数字;

③ (?!\d) ：第 2 步中的 3 个数字不允许后面跟着数字;

解法上： API 大法

function parseToMoney(num) {
  return num.toLocaleString();
}