由0~9这10个数字不重复、不遗漏，可以组成很多10位数字。
这其中也有很多恰好是平方数（是某个数的平方）。比如：1026753849，就是其中最小的一个平方数。
请你找出其中最大的一个平方数是多少？
注意：你需要提交的是一个10位数字，不要填写任何多余内容。
思路1：
1.枚举答案 X[9876543210，1026753849]
2.判断是不是恰好0-9十个数字
3.判断是不是完全平方数
令Y=int(sqrt(X))
判断 Y*Y==X;
缺点：时间复杂度10^10,超时
思路2：
换种枚举方式
1.枚举X的开平方跟Y[100000,32043]，相当于对区间的两个端值开了平方根
2.运用set容器，来判断所枚举的x是否是不重复的10为数字
codes:
#include<iostream>
#include<set>
using namespace std;
//该函数求解的结果位数是否为10位
bool contain(long long n)
{
if(n == 0)
return false;
set<long long> s;
while(n)
{
long long m = n % 10;
s.insert(m);
n /= 10;
}
return s.size() == 10;//检查是否为不重复的十位数字
}
int main()
{
for(long long i = 32043; i <= 100000; i++){//缩小范围
long long x = i * i;//求平方
if(contain(x)){
cout << x << endl;//输出结果
}
}
return 0;
}
You can leave me a message if you find out anything incorrect in my diary, I'll correct it, thanks.
