1.png

因为是看别人的顺序刷题，所以直接想到可以二分法找（找整数部分）

我的错误答案

  1. class Solution {
  2.     public int mySqrt(int x) {
  3.         if (x == 0){
  4.             return 0;
  5.         }
  6.         int low = 1,high = x;
  7.         while(low < high){
  8.             int mid = low + (high - low) / 2;
  9.             if (mid * mid > x){
  10.                 high = mid - 1;
  11.             }
  12.             else if (mid * mid <= x && (mid + 1) * (mid + 1) > x){
  13.                 return mid;
  14.             }
  15.             else{
  16.                 low = mid;
  17.             }
  18.         }
  19.         return low;
  20.     }
  21. }

虽说考虑了0，但是….x=2147395600就炸了…思路可能有点问题或者说是算法有点问题

二分法正解

找到k*k<=x的最大整数k

  1. class Solution {
  2.     public int mySqrt(int x) {
  3.         int l = 0, r = x, ans = -1;
  4.         while (l <= r) {
  5.             int mid = l + (r - l) / 2;
  6.             if ((long) mid * mid <= x) {
  7.                 ans = mid;
  8.                 l = mid + 1;
  9.             } else {
  10.                 r = mid - 1;
  11.             }
  12.         }
  13.         return ans;
  14.     }
  15. }
  18. 作者：LeetCode-Solution
  19. 链接：https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
  20. 来源：力扣（LeetCode）
  21. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

显然那个long是必须的

而且显然我想复杂了 我那个跑不完的

数学方法

禁用幂，可以凑，不过这个方法真的好吗….

  1. class Solution {
  2.     public int mySqrt(int x) {
  3.         if (x == 0) {
  4.             return 0;
  5.         }
  6.         int ans = (int) Math.exp(0.5 * Math.log(x));
  7.         return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
  8.     }
  9. }

还是注意long，然后浮点数有误差，所以要在附近找

牛顿迭代

没学