牛客网真题2019-41-X游戏

排除掉坏数，剩下都是好数，坏数有两种：

• 只要有一位数字是3，4，7

• 这个数全是由0，1，8构成，不包含数字 2，5，6，9
  根据这两种规则可以写出judgeOK函数，然后可以在搜索上优化，本题不优化也能过
  将for循环变成while循环，当n的最高位是3，4，7可以直接跳过。这样能优化1/3
  显然这是数论题：于是有排列组合求解
  例：1000， 这是一个4位数，第一位有1种情况，后面三位有10种情况，总共数字1X10X10X10，这里不包括1000这个数在内，但包含0000
  只要有一位包含3，4，7的数字是可以有1位，2位，3位=总数-不包含3，4，7=1000-7x7x7=657,只包含0，1，8是3x3x3
  1000-657-27=316 常数时间求解

  import java.util.*;
  public class Main {
    private static Set<Integer> set = new HashSet<>();
    private static Set<Integer> okSet = new HashSet<>();
  
    public static boolean judgeOK(int p){
        boolean ok = false;
  
        while (p > 0) {
            int q = p % 10;
            if(set.contains(q)){
                return false;
            }else{
                if(okSet.contains(q)){
                    ok = true;
                }
                p = p / 10;
            }
        }
        return ok;
    }
  
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Collections.addAll(set, 3, 4, 7);
        Collections.addAll(okSet, 2, 5, 6, 9);
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            if(judgeOK(i)){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
  }
  

```