自守数

牛客网上的华为笔试题

描述

自守数是指一个数的平方的尾数等于该数自身的自然数。例如：。请求出n(包括n)以内的自守数的个数。

数据范围：

输入描述

int型整数

输出描述

n以内自守数的数量。

示例1

输入

6

输出

4

说明

有0，1，5，6这四个自守数

示例2

输入

1

输出

2

说明

有0, 1这两个自守数

代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.LongStream;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
//        System.out.println(countAutomorphicNumber0(n));
        System.out.println(countAutomorphicNumber1(n));
//        System.out.println(countAutomorphicNumber2(n));
    }

    public static long countAutomorphicNumber0(int n) {
        return LongStream
                .range(0, n + 1)
                .filter(x -> String.valueOf(x * x).endsWith(x + ""))
                .count();
    }

    public static int countAutomorphicNumber1(int n) {
        int count = 0;
        for (int i = 0; i <= n; i++) {
            if (isAutomorphicNumber(i)) {
                count++;
            }
        }
        return count;
    }

    public static int countAutomorphicNumber2(int n) {
        // FIXME
        return String.valueOf(n).length() << 1;
    }

    public static boolean isAutomorphicNumber(int n) {
        if (n == 0 || n == 1) {
            return true;
        }
        int mod10 = n % 10;
        // 只有以5和6结尾的数才有可能是自守数(除了0,1)
        if (mod10 != 5 && mod10 != 6) {
            return false;
        }
        // 反转便于后面理解和计算
        String rev = new StringBuilder().append(n).reverse().toString();
        int len = rev.length();
        // 存放计算结果 e.g. 125 存放形式为 [5, 2, 1]
        List<Integer> list = new ArrayList<>(len + 1);
        // 初始进位为0
        list.add(0);
        for (int i = 0; i < len; i++) {
            // 计算到len位就停止了 不多算
            // e.g.  625
            //     * 625
            //------------
            //      3125
            //      250
            //      30
            //------------
            //       625
            for (int j = 0; j < len - i; j++) {
                int idx = i + j;
                // 第i位和第j位的乘积加上i+j位的进位
                int product = charToDigit(rev.charAt(i)) * charToDigit(rev.charAt(j)) + list.get(idx);
                list.set(idx, product % 10);
                // 进位
                int carry = product / 10;
                if (idx + 1 < list.size()) {
                    list.set(idx + 1, list.get(idx + 1) + carry);
                } else {
                    list.add(carry);
                }
            }
            if (digitToChar(list.get(i)) != rev.charAt(i)) {
                return false;
            }
        }
        return true;
    }

    public static char digitToChar(int i) {
        return (char) (i + '0');
    }

    public static int charToDigit(char c) {
        return c - '0';
    }
}