LeetCode 每日一题
二分专题
2020/10/07
- 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.
解决思路
-
利用自带的库函数
主要代码:
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); } } }
-
暴力搜索
主要思路:
利用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);
}
}
}
-
二分搜索
主要思路: 二分搜索的两个主要模板
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中使用断点调试, 便于理解整个流程, 而不是只知道答案!