题解 | #完全平方数的尾巴#

题意整理

输入一个整数x（范围在0到999之间）。
判断它是否是由某个完全平方数对1000取模所得。

方法一（模拟）

1.解题思路

遍历所有可能。
如果x是某个平方数对1000取余，直接返回true。
如果遍历完，还没有找到对应的平方数，则返回false。

动图展示：
图片说明

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return bool布尔型
     */
    //取余常数
    int mod=1000;
    public boolean solve (int x) {
        //遍历所有可能
        for(int i=0;i<1000;i++){
            //如果x是某个平方数对mod取余，直接返回true
            if(x==(i*i)%mod){
                return true;
            }
        }
        return false;
    }
}

3.复杂度分析

时间复杂度：假设x取值范围的大小为k，则时间复杂度为 $O(k)$ 。
空间复杂度：不需要额外的空间，所以空间复杂度为 $O(1)$ 。

方法二（打表统计）

1.解题思路

将所有可能的x对应的情况，统计在一个记录表里。
当输入x时，直接从表里对应的位置取。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param x int整型 
     * @return bool布尔型
     */
    //取余常数
    int mod=1000;
    //记录表
    boolean[] f;
    public boolean solve (int x) {
        //初始化记录表
        init();
        return f[x];
    }

    private void init(){
        f=new boolean[1000];
        //遍历所有可能输入的x
        for(int i=0;i<1000;i++){
            for(int j=0;j<1000;j++){
                //如果满足题目所给的规则
                if(i==(j*j)%mod){
                    f[i]=true;
                    break;
                }
            }
        }
    }
}

3.复杂度分析

时间复杂度：假设x取值范围大小为k，初始化记录表的复杂度为 $O(k^2)$ ，最终判断的时间复杂度为 $O(1)$ 。
空间复杂度：需要额外大小为k的记录表，所以空间复杂度为 $O(k)$ 。