LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 二分查找即可，注意判断过程中，值的平方可能产生溢出，因此判断应该用除法而非乘法

class Solution {
 public:
  int mySqrt(int x) {
    if (x <= 1) {
      return x;
    }
    int l = 1;
    int r = x;
    while (l < r) {
      int m = l + (r - l) / 2;
      int t = x / m;  // m * m 可能溢出
      if (m == t) {
        return m;
      } else if (m > t) {
        r = m;
      } else {
        l = m + 1;
      }
    }              // l 是第一个满足 x / m < m 的值
    return l - 1;  // 商应该向下取整，因此返回 l - 1
  }
};