今天去一家小公司面试，算是开了眼 公司藏在居民楼里，老板亲自开门，办公室直接设在客厅，勉强摆下两张桌子，算上我总共就三个员工。

真是活久见。我在网上看到一个吐槽帖：有人去一家小公司面试，结果公司藏在居民楼里，老板亲自来开门，办公室就设在客厅，两张桌子一摆，空气里都透着“创业要省到骨头里”的味儿。

更离谱的是，算上面试的人，屋里一共才仨人，老板自己还占着一个工位。这场面，乍一看像临时组队干活，仔细一想，连摸鱼都不太好意思。

说实话，这种公司看着草台班子，待着还真可能挺香。尤其对打工人来说，通勤少折腾，规矩少一点，人反而松快。老板坐你旁边是压力，转头一想，也省得层层汇报，出了问题直接当面对线，连会议室都省了。

面试题：有效的完全平方数

题意也直接：给你一个正整数 num，判断它是不是完全平方数。注意，题目一般会带一个限制：不要用内置的开方函数。

很多人第一反应是：

publicbooleanisPerfectSquare(int num){
int x = (int) Math.sqrt(num);
return x * x == num;
}

本地跑没问题，但这题本来就是不想让你这么做。真正在面试里，考的也不是你会不会调 API，而是你能不能自己把判断过程写出来。

这题最稳的解法，其实是二分查找。

因为完全平方数的平方根一定落在 1 ~ num 之间。比如 16 的平方根是 4，14 的平方根就在某两个整数之间，不会整除。既然范围天然有序，就可以二分去找。

先看代码，核心就这么几行：

classSolution{
publicbooleanisPerfectSquare(int num){
if (num == 1) {
returntrue;
        }

long left = 1;
long right = num;

while (left <= right) {
long mid = left + ((right - left) >> 1);
long square = mid * mid;

if (square == num) {
returntrue;
            }

if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

returnfalse;
    }
}

这里真正要注意的，不是二分本身，而是两个小细节。

第一个是 mid * mid 可能溢出。

比如 num 接近 int 上限时，mid 也是个很大的数，如果你还用 int 去乘，结果可能直接变成负数，判断就乱了。所以我这里把 left、right、mid、square 都提成了 long。这不是为了好看，是为了避免这类题里最常见的坑。

第二个是边界。

像 num = 1 这种值，单独拎出来并不是必须，但写出来代码会更顺一点，读起来也清楚。面试里这种处理方式通常比把所有情况都塞进循环里更稳。

这题时间复杂度是 O(log n)，空间复杂度 O(1)，放在算法题里算是很标准的一档。

当然，这题还有另一个思路，也挺有意思：利用奇数求和。

因为一个数学规律是：

1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7

也就是说，任意一个完全平方数，都可以表示成前若干个连续奇数的和。

按这个思路，代码可以写成这样：

classSolution{
publicbooleanisPerfectSquare(int num){
int odd = 1;

while (num > 0) {
            num -= odd;
            odd += 2;
        }

return num == 0;
    }
}

这个写法很巧，面试官看了通常也知道你是认真想过题的。不过它的时间复杂度是 O(sqrt n)，数据再大一点，就没有二分那么利索了。

所以如果是我自己做题，或者写面试答案，还是更倾向于交二分版本。原因很简单：思路稳，边界清楚，复杂度也更好。

再拿几个数过一下：

isPerfectSquare(16)  // true
isPerfectSquare(14)  // false
isPerfectSquare(1)   // true
isPerfectSquare(808201) // true，899 * 899

这题不难，但很适合看一个人写代码时有没有“下意识处理溢出和边界”的习惯。题目表面是在判断平方数，实际写的时候，考点已经落到二分模板、数值范围和细节控制上了。

所以做这题的时候，别急着背答案。把 mid 怎么取、为什么要用 long、循环什么时候停，这几个点自己顺一遍，后面再碰到“求平方根”“查目标值范围”这一类题，基本都能接上。