题解 | #自守数#
自守数
https://www.nowcoder.com/practice/88ddd31618f04514ae3a689e83f3ab8e
两种解法
package com.zkj.test.algorithm.huawei.nowcoder.simple; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.util.stream.LongStream; /** * @author hll[yellowdradra@foxmail.com] * @since 2023-03-31 14:59 **/ public class HJ99_自守数 { 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'; } }