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();
    }

}