HJ99 题解 | #自守数#

题意分析

给你一个数字，需要你找出在这个数字范围内的正整数中，自守数的个数。自守数是指一个数的平方的尾数等于该数自身的自然数。

思路分析

寻找规律

对于自守数，我们可以发现，如果这个数字是自守数，那么这个数的平方减去这个数得到的数的后面一定有这么多个0。比如5这个数字，5的平方是25，25-5=20，后面又一个0，5的位数也是1位，所以这个数字是自守数。其他的也可以发现也满足这个规律。但是这里要注意的一个情况是比如0和1这种情况，这种最后减下来一定是0，需要进行特判。
综上，我们就得到了我们的求解方法，我们先对n已被的每个数字进行枚举，然后，将这个数字的平方数减去这个数字。首先判断这个数字是否是0，如果是，那么一定是自守数。否则，寻找得到的数字的最后的0的个数，与枚举的这个数字的位数进行比较。如果0的个数比枚举的这个数字的位数多，那么这个数一定是一个自守数。
代码如下
- 我们对每个数字进行枚举，然后枚举的每个数字，我们需要对这个数字进行拆位，寻找最后0的个数，其实这里面的复杂度可以看作是 $O (1)$ .所以总的时间复杂度为 $O (n)$
- 过程中只用了少数几个变量求解，空间复杂度为 $O (1)$

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int ans=0;
       while(n>=0){
           // 先计算n的长度
           int num=0;
           int x=n;
           while(x){
               num++;
               x/=10;
           }
           // 计算tmp-n的最后面的0的个数
           int tmp=n*n-n;
           // 特判如果为0的情况
           if(tmp==0){
               ans++;
           }else{
               int num1=0;
               // 计算这个数的最后的0的个数
               while(tmp){
                   if(tmp%10==0){
                       num1++;
                   }else{
                       break;
                   }
                   tmp/=10;
               }
               // 如果最后的0的个数比这个数的长度更长，那么就是一个自守数
               if(num1>=num){
                   ans++;
               }
           }
           n--;
       }
        printf("%d\n",ans);
    }
    return 0;
}

字符串前缀比较

我们根据定义，我们枚举n以内的数字，对于每个枚举的数字，我们先计算这个数字的平方，然后将这个数的平方和转化为字符串tmp1,这个数都转化为字符串tmp2。然后只要tmp2是tmp1的后缀就行了。但是我们比较后缀显然是不方便的，所以我们将字符串进行反转转化为比较前缀。如果满足则说明是自守数。
代码如下
- 我们对每个数字进行枚举，然后枚举的每个数字，我们需要对这个数字转化为字符串，最后比较前缀，但是由于字符串都比较短，这里面的复杂度可以看作是 $O (1)$ .所以总的时间复杂度为 $O (n)$
- 过程中只用了少数几个变量求解，空间复杂度为 $O (1)$

#include<bits/stdc++.h>

using namespace std;

// intTostring 数字转化为字符串
string intTostring(int x){
    string c="";
    while(x){
        c+=(x%10+'0');
        x/=10;
    }
    // 注意，我们这里没有对字符串进行翻转，是为了后续比较方便，可以直接比较前缀即可
    return c;
}

// compare 比较tmp2是否是tmp1的前缀
bool compare(string tmp1,string tmp2){
    int len=tmp2.size();
    int i=0;
    while(i<len){
        if(tmp1[i]!=tmp2[i]){
            return false;
        }
        i++;
    }
    return true;
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int ans=0;
       while(n>=0){
           // 将要比较的数字转换为字符串，这里得到的是反转字符串
           string tmp1=intTostring(n*n);
           string tmp2=intTostring(n);
           // 比较两个字符串，tmp2一定是tmp1的前缀才可以满足时自守数
           if(compare(tmp1,tmp2)) ans++;
           n--;
       }
        printf("%d\n",ans);
    }
    return 0;
}

图解补充

综合上面的两种解法给出举例图解

alt