HDU 2089 不要62

Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input
输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

Output
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample Input

1 100 0 0

Sample Output

80
java code(Time out)

import java.util.Scanner;
public class Main {
   public static void main(String[] args) {
       Scanner input = new Scanner(System.in);
       while (input.hasNext()) {
           int n = input.nextInt();
           int m = input.nextInt();
           // 0<n≤m<1000000
           if (n == 0 && m == 0) {
               break;
           }
           int sum = m - n + 1;
           for (int i = n; i <= m; i++) {
               // String string = String.valueOf(i);
               // // 使用contains超时
               // if (string.contains("4") || string.contains("62")) {
               // sum--;
               // }
               //time out
               char[] strs = String.valueOf(i).toCharArray();
               for (int j = 0; j < strs.length; j++) {
                   if (strs[j] == '4'
                           || (strs.length >= 2 && j < strs.length - 1
                                   && strs[j] == '6' && strs[j + 1] == '2')) {
                       sum--;
                       break;
                   }
               }
           }
           System.out.println(sum);
       }
       input.close();
   }

}

c++ code

#include <iostream>
using namespace std  ;
int f[8][10] ;//f[i][j]表示第i位是数j时符合条件的数字数量
int digit[9] ;//digit[i]表示n从右到左第i位是多少
void Init()
{
    f[0][0]=1 ;
    for(int i=1 ;i<=7 ;i++)
    {
        for(int j=0 ;j<10 ;j++)//枚举第i位
        {
            for(int k=0 ;k<10 ;k++)//枚举第i-1位
            {
                if(!(j==6 && k==2) && j!=4)//如果符合条件
                    f[i][j]+=f[i-1][k] ;
            }
        }
    }
}
int callen(int n)//计算n的长度
{
    int cnt=0 ;
    while(n)
    {
        cnt++ ;
        n/=10 ;
    }
    return cnt ;
}
void caldigit(int n,int len)//计算n的digit数组
{
    memset(digit,0,sizeof(digit)) ;
    for(int i=1 ;i<=len ;i++)
    {
        digit[i]=n%10 ;
        n/=10 ;
    }
}
int solve(int n)//计算[0,n]区间满足条件的数字个数
{
    int ans=0 ;
    int len=callen(n) ;
    caldigit(n,len) ;
    for(int i=len ;i>=1 ;i--)
    {
        for(int j=0 ;j<digit[i] ;j++)//枚举第i位取值
        {
            if(!(j==2 && digit[i+1]==6) && j!=4)//第i位满足条件
                ans+=f[i][j] ;
        }
        if(digit[i]==4 || (digit[i]==2 && digit[i+1]==6))//第i位已经不满足条件，则i位以后都不可能满足条件，结束循环
            break ;
    }
    return ans ;
}
int main()
{
    Init() ;
    int n,m ;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0 && m==0)
            break ;
        printf("%d\n",solve(m+1)-solve(n)) ;//用[0,m]-[0,n)即可得到区间[n,m]
    }
    return 0 ;
}```