leetcode367 判断该数是否是完全平方数

蚊子前端博客
发布于 2022-04-23 11:07
介绍下leetcode中该题目的注意事项

题目地址 367. 有效的完全平方数。题目要求不能用库函数来直接开平方,本意是希望用二分法来解决该问题。

1. 完全平方数的解决方案

两种方式:

  1. 直接检索:从 1 开始匹配,挨个儿匹配 num,直到能匹配上(返回 true),或超过 num(返回 false)。时间复杂度为 O(n);

  2. 二分查找:取中间数来匹配 num,匹配上就直接返回,否则根据大小来决定取左边或者右边;

无论使用哪种方式,都应该注意类型范围和精度这两个问题。

题目中限制了 num 的范围在[1, 2^31-1],若我们选择了 int 类型,并且用乘方结果来跟 num 进行匹配时,无论是直接检索还是二分查找,都会极大概率出现超过类型范围的问题。这里应该选择long long类型。

同时,取中间值时,不要直接(left+right)/2,这也会超出 int 范围的,应该使用 left + 偏移量的方法:

COPYCPP

mid = left + (right - left) / 2;

我们换个角度,为避免数字超过类型范围,用 num 来除以这个数 mid,再判断商是否等于 mid。但在 C/C++中,会舍弃小数,导致判断失败,如 10000 和 10001 两个数字:

COPYCPP

int result0, result1, mid = 100; result0 = 10000 / 100; result1 = 10001 / 100; result0 == mid; // 正确,expect true, receive true result1 == mid; // 错误, expect false, receive true

这里最好再用取余判断下是否可以整除,最终的代码:

COPYCPP

class Solution { public: bool isPerfectSquare(int num) { int left, right, mid; int square; left = 1; right = num; while (left <= right) { mid = left + (right - left) / 2; square = num / mid; if (square == mid) { return num % mid == 0; } if (square > mid) { left = mid + 1; } else { right = mid - 1; } } // 没找到 return false; } };

2. 平方根

这里还有个上面平方数的姊妹篇:69. x 的平方根 ,即求 x 的平方根的整数位置。

跟上面的思路一样,要考虑取中间数的方式和用于相除来代替相乘,避免超出整型数字范围。

最终实现的代码如下:

COPYCPP

class Solution { public: int mySqrt(int x) { if (x <= 1) { return x; } int left, right, mid, result; left = 1; right = x; while (left <= right) { mid = left + ((right - left) >> 1); result = x / mid; // 已自动取整 if (result == mid) { return mid; } if (result > mid) { // result大,说明mid做为除数偏小,应当向右移动 left = mid + 1; } else { right = mid - 1; } } return right; } };

关键点在于 x / mid在强制类型的语言中会自动取整,因此若mid == x / mid时,就说明 mid 是 x 的平方根的整数部分。

如数字 4 的平方根正好是 2 ;而 5/2==2,因此 2 就是 5 的平方根的整数部分;数字 6 则是在循环里找不到对应的数字的,会在最后返回 right 指向的值。

标签:
阅读(388)

公众号:

qrcode

微信公众号:前端小茶馆