LeetCode 0069 - Sqrt(x)
# Hints
- 二分查找
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Easy |
Implement int sqrt(int x)
.
Compute and return the square root of , where 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.
# 题意
给定一个非负整数 ,求 的结果的整数部分。
# 题解
水题,二分查找即可。
细节问题:
- 注意防止乘法溢出,在 check 时需要改用除法,但此时需要特判 的情况。
# AC代码
class Solution {
public:
int mySqrt(int x) {
// 特判
if (x < 2) {
return x;
}
// 二分查找
int left = 1, right = x / 2;
int res = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (mid <= x / mid) {
left = mid + 1;
res = mid;
} else {
right = mid - 1;
}
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01