判断是否是完全平方数[容易]和排列箱子[容易]

1.1.1.完全平方数（PerfectSquare）

判断正整数y是否是完全平方数。如果能找到正整数x，使得x*x==y，则y是平方数。

1.思路

x的取值范围是[1,y]，我们用左闭右开空间，就是[1,y+1)。

注意：计算过程要注意溢出。

扩展：如果y是自然数呢？y可以为0。

代码

#include #include bool IsPerfectSquare(int y ){    int left = 1, right = y + 1;    while (right - left > 1)    {        int x = left + (right - left) / 2;        if (x * x == y)        {            return true;        }        else if (x * x > y)        {            right = x;        }        else        {            left = x;        }    }    return left * left == y;}int main(){    std::vector v;    for (int i = 1; i < 1000; i++)    {        if (IsPerfectSquare(i))        {            v.emplace_back(i);        }    }    for (const auto& n : v)    {        std::cout << n << " ";    }}

1.1.1.排列箱子

有n个箱子，求可以排列多少行（包括不完整行）。第一行1个箱子，第二行2个箱子…第i行i个箱子。注意：最后一行可能没满，除最后一行外其他行全满。

1.解题思路

m行排满，共有maxN= m*(1+m)/2个箱子。

m行只排一个，共有minN = maxN-m+1个箱子。

如果n小于minN，则抛弃右边；

如果n大于maxN，则抛弃左边。

边界[1,n]，左闭右开空间是[1,n+1)

代码

#include
#include

int BoxLeve(int n)
{
int left = 1, right = n + 1;
while (right – left > 1)
{
int mid = left + (right – left) / 2;
int maxN = (1 + mid)* mid / 2;
int minN = maxN – mid + 1;
if (n < minN)
{
right = mid;
}
else if (n > maxN)
{
left = mid;
}
else
{
return mid;
}
}
return left;
}
int main()
{
assert(1 == BoxLeve(1));
assert(3 == BoxLeve(4));
assert(3 == BoxLeve(5));
assert(3 == BoxLeve(6));
assert(4 == BoxLeve(7));
assert(4 == BoxLeve(10));
//assert(51 == BoxLeve(11));
}

2021年目标：完成新书《闻缺陷则喜》,本博客右上公告有下载、阅读链接。