猫猫说了算
理解是偶然,误解是常态。

【算法】用加减法实现整除法

远浅发表于: 2021-10-12 13:50分类: 技术

来源

LeetCode 29. 两数相除,只保留整数部分 这道题由于加上了边界条件,导致需要进行一些逻辑判断,但是其实思路很简单, 下面解释一下核心思路。

最简实践

被除数 ➗ 除数,最简单的做法就是不断的 被除数 减去 除数,计算次数就能得到商。

实现如下

function div(a, b) {
  let count = 0;
  while (a >= b) {
    a -= b;
    count += 1;
  }
  return count;
}

进阶实现

既然 a 是 b 的倍数,那么我们可以胆子大点,不必每次减 b。可以尝试减去 b的倍数,如下。


function def(a, b) {
    let count = 1;
    // a 比 b小 没的除
    if (a < b) return 0;
    let tmpb = b;
    // 倍数相加判断 
    while (tmpb + tmpb <= a) {
      count += count;
      tmpb += tmpb;
    }
    // 减去倍数
    return count + def(a - tmpb, b);
  }
赠人玫瑰, 手有余香。🌹
打赏
特别鸣谢
感谢以下用户对本文的支持与鼓励
加载打赏用户中
发表评论
文章评论
暂无任何评论,快去发表吧~