leetcode笔记:Sqrt(x)
2023-09-11 14:14:09 时间
一. 题目描写叙述
Implement int sqrt(int x).
Compute and return the square root of x.
二. 题目分析
该题要求实现求根公式,该题还算是比較简单的,由于仅仅需返回最接近的整数,直接二分法就可以。在实现的过程中还是有一些细节的,比方推断条件:x / mid > mid
而不能是x > mid * mid
。由于mid * mid
会导致溢出。
三. 演示样例代码
#include <iostream>
using namespace std;
class Solution
{
public:
int sqrt(int x)
{
if (x == 0 || x == 1) return x;
int min = 1, max = x / 2; // 根必在此区间中
// 二分查找
int mid, result;
while (min <= max)
{
mid = min + (max - min) / 2;
if (x / mid > mid)
{
// 根的平方需小于等于x,因此每次须在此处更新根的值
result = mid;
min = mid + 1;
}
else if (x / mid < mid) max = mid - 1;
else return mid;
}
return result;
}
};
一些执行结果:
四. 小结
此题为分治思路的经典题型之中的一个。
相关文章
- Java实现 LeetCode 653 两数之和 IV - 输入 BST(递归,找差值)
- Java实现 LeetCode 225 用队列实现栈
- Java实现 LeetCode 77 组合
- LeetCode-1237. 找出给定方程的正整数解【双指针,二分查找】
- Python 刷Leetcode题库,顺带学英语单词(50)
- LeetCode - 630 课程表Ⅲ
- Leetcode 1332. 删除回文子序列(看完题解才恍然大悟!!!!!!!)
- leetcode 104. 二叉树的最大深度 js实现
- 【Leetcode刷题Python】74. 搜索二维矩阵
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点