LeetCode 每日一题

二分专题

2020/10/07

69. Sqrt(x)

Easy

15392037Add to ListShare

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

解决思路

1. 利用自带的库函数

   主要代码:

   public int mySqrt(int x) {
           return (int)Math.sqrt(x);
       }
   

   package Easy.liushijiu;
   
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   
   class Solution {
       public int mySqrt(int x) {
           return (int)Math.sqrt(x);
       }
   }
   
   public class MainClass {
       public static void main(String[] args) throws IOException {
           BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
           String line;
           while ((line = in.readLine()) != null) {
               int n = Integer.parseInt(line);
               int ret = new Solution().mySqrt(n);
               String out = String.valueOf(ret);
               System.out.print(out);
           }
       }
   }
   
   

2. 暴力搜索

   主要思路:

   利用for循环, 从1到x*x<=n

x*x 会造成整数溢出, 所以需要将int类型转换为long类型

​ 主要代码:

 public int mySqrt(int x) {
        long tmp = (long) x;
        long i = 0;
        for (i = 0; (long) (i * i) <= tmp; i++) {
            if (i * i == x) {
                return (int)i;
            }
        }

        return (int)(i - 1);
    }

全部代码:

package Easy.liushijiu;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Solution {
    public int mySqrt(int x) {
//        return (int)Math.sqrt(x);
        long tmp = (long) x;
        long i = 0;
        for (i = 0; (long) (i * i) <= tmp; i++) {
            if (i * i == x) {
                return (int)i;
            }
        }

        return (int)(i - 1);
    }
}

public class MainClass {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int n = Integer.parseInt(line);
            int ret = new Solution().mySqrt(n);
            String out = String.valueOf(ret);
            System.out.print(out);
        }
    }
}

3. 二分搜索

   主要思路: 二分搜索的两个主要模板

   a. 寻找值最小

   b. 寻找值最大

后面会写一篇关于其推导证明以及模板的博客

而本地明显属于寻找值最小的情况, 只需要使用第一个模板就可以

注意: 避免两数相加和两数相乘导致溢出的情况

主要代码

 public int mySqrt(int x) {long tmp = x;
        long l = 0, r = tmp;
        while (l < r) {
            long mid = (l + r + 1) / 2;
            if (mid <= x / mid) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return (int) l;
    }

全部代码

package Easy.liushijiu;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Solution {
    public int mySqrt(int x) {
//        return (int)Math.sqrt(x);
//        long tmp = (long) x;
//        long i = 0;
//        for (i = 0; (long) (i * i) <= tmp; i++) {
//            if (i * i == x) {
//                return (int)i;
//            }
//        }
//
//        return (int)(i - 1);

        long tmp = x;
        long l = 0, r = tmp;
        while (l < r) {
            long mid = (l + r + 1) / 2;
            if (mid <= x / mid) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return (int) l;
    }
}

public class MainClass {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int n = Integer.parseInt(line);
            int ret = new Solution().mySqrt(n);
            String out = String.valueOf(ret);
            System.out.print(out);
        }
    }
}

备注: 全部代码主要方便在IDEA中使用断点调试, 便于理解整个流程, 而不是只知道答案!