枚举+优化（1）——枚举

十位平方数

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