MENU

枚举+优化(1)——枚举

June 5, 2018 • Read: 153 • 算法

十位平方数

由0~9这10个数字不重复、不遗漏,可以组成很多10位数字。这其中也有很多恰好是平方数。

比如:1026753849,就是其中一个最小的平方数。

请你找出其中最大的一个平方数是多少?

思路1

  1. 枚举答案X [9876853210,1026753849](从最大的数枚举到最小的数)
  2. 判断是不是恰好0-9十个数字
  3. 判断是不是完全平方数

    • 令Y = int(sqrt(x))
    • 判断Y * Y == X

思路2(优化)

  1. 枚举Y[100000,30000]
  2. 计算X = Y * Y
  3. 判断X是不是恰好是0-9十个数字
//判断是不是包含0-9
bool contains0_9(int x)
{
    if(x == 0)
        return false;
    set<int> s;
    while(x)//把x的末位数字通过模10分离
    {
        int d = x % 10;
        s.insert(d);
        x /= 10;
    }
    return (s.size() == 10);
}
//完整代码
#include <bits/stdc++.h>
using namespace std;
bool contains0_9(long long x)
{
    set<int> s;
    while(x)
    {
        int d = x % 10;
        s.insert(d);
        x /= 10;
    }
    return (s.size() == 10);
}
int main()
{
    for(long long y = 100000;y >= 30000;y--)
        if(contains0_9(y * y))
            cout<<y * y<<endl;
    return 0;
}
最后编辑于: October 19, 2018
Archives Tip
QR Code for this page
Tipping QR Code