UVa1583 Digit Generator — Java

我在 github 上建立了一个 repo，专门记录自己对刘汝佳的《算法竞赛入门经典（第二版）》中每个 UVa 例题和习题的解答，目前刚刚开始，会不断升级，本人水平不高，如有错误，欢迎大家指正。当然更希望大家能提供更优的解法，共同提高进步，满意的话给个 star 啊(●ˇ?ˇ●)

github repo 传送门

QQ: 1583801169

【原题链接】点击即达

不过UVa OJ需要科学上网才能访问，故此处贴出百度云链接，有原题的pdf文档，需要的直接下载。失效的话可以私信或者者评论留下邮箱。
链接：https://pan.baidu.com/s/1xV44H0SF0Ik45G515hSMGA
提取码：3n8v

【题意】
??生成元：给出两个正数 x 和 y，若 y 等于 x 加上 x 的各个数字之和，则称 x 是 y 的生成元。例如，216 的最小生成元是 198，121 的最小生成元是 0。
??此题要求你能求出一个给定正整数 n(1 <= n <= 100000) 的最小生成元，即若一个正整数 n 有多个生成元，你需要求出的是最小的那个生成元，若没有生成元，你需要打印出 0。

【输入】
??首先输入一个正整数 T，表示你需要输入 T 个正整数，并求出它们的最小生成元。

【输出】
每行输出对应正整数的最小生成元。

【代码】

???????代码通过事前计算范围内所有正整数的最小生成元，存放在一个数组中，该下标对应的数组中的数值就是该下标的最小生成元。最后，通过查数组就能找到。

在 if 判断中，请大家仔细判别哦，此处需要体会一下。
y < MAXN：这个条件是防止数组越界的，假如你用的 C/C++ 此处不需要这个判断，但是 Java 此处需要。或者者可以捕捉这个异常，但是此处我没有这么做。（这涉及语言自己解决的问题了）
i < ans[y]：这个条件是找出最小生成元啊！(o?v?)ノ

import java.util.Scanner;/** * @author Adonis * @Email 1583801169@qq.com * @Date 2019-01-18 10:24:57 * @Version V1.0 */public class Main {    private static final int MAXN = 100005;        public static void main(String[] args) {        int[] ans = new int[MAXN];  // automatically initialized to 0        int n = 0, c = 0;        Scanner in = new Scanner(System.in);                for (int i=1; i<MAXN; i++) {            int x = i, y = i;                        while (x > 0) { // get the sum of the numbers of x and x                y += x % 10;                x /= 10;            }            if (y < MAXN && (ans[y] == 0 || i < ans[y])) {  // y<MAXN: avoid exceeding the length of array ans                ans[y] = i;            }        }                c = in.nextInt();        for (int i=0; i<c; i++) {            n = in.nextInt();            System.out.println(ans[n]);        }        in.close();    }}