题意及思路


  • 题意：去除给定区间内“不吉利”的数字。计算“不吉利”数字的个数。
  • 思路：@一开始，想用的是将每一个数字转化为字符串，然后使用字符串的contains方法，查询是否为“不吉利”数字。可是每次循环都将重新判断，可能会超时。提交结果不出所料，是TLE。


@然后借鉴了网上一些好的想法，以空间换时间。先将给定的最大范围内的数字的“吉利”与否都给记录下。然后计算给定区间内的非不吉利数字的个数也就迎刃而解了。

  • 踩坑点：思路大致以“换”原则，但是不要讲换的空间增大了（无故），像我出现了一个错误是：原本是百万级的数组，我粗心地写成了千万级。出现了MLE。（Memory Limit Exceed）

代码 

import java.util.Scanner;

public class HD2089 {
    // 1000000
    private static int ans[] = new int[1000001];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a, b, times;
        // 初始化ans[]
        init();
        while (in.hasNext()) {
            a = in.nextInt();
            b = in.nextInt();
            if (a == 0 && b == 0)
                break;
            times = 0;
            for (int i = a; i <= b; i++) {
                times += ans[i];
            }
            System.out.println(times);
        }
        in.close();
    }

    private static void init() {
        String str;
        for (int i = 0; i < ans.length; i++) {
            str = String.valueOf(i);
            if (!str.contains("62") && !str.contains("4")) {
                ans[i] = 1;
            }
        }
    }
}