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

1.1.1. 完全平方数(PerfectSquare

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

1. 思路

条件

处理

x*x>y

丢弃右半部分

x*x==y

y是完全平方数

x*x<y

丢弃左半部分

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

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

扩展:如果y是自然数呢?y可以为0

 

代码

 

#include <iostream>
#include <vector>

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<int> 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个箱子...ii个箱子。注意:最后一行可能没满,除最后一行外其他行全满。

1. 解题思路

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

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

如果n小于minN,则抛弃右边;

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

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

 

代码

 

#include <iostream>
#include <assert.h>

 

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));
}

 

 

  

 

热门相关:流鱼无恙   食母:墨菲定律   成人高校教师   金粉   裙上之臣