题目描述：

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X.  Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.

Now given a positive number N, how many numbers X from 1 to N are good?

Example:Input: 10Output: 4Explanation: There are four good numbers in the range [1, 10] : 2, 5, 6, 9.Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Note:

• N  will be in range [1, 10000].

 

要完成的函数：

int rotatedDigits(int N) 

 

说明：

1、这道题给定一个数字N，要求判断在[1,N]之间的数有多少个“好数”。好数的判断标准是这样的：数位上的每个数字翻转180度，翻转之后的所有数位还能构成数字的，并且该数字与翻转之前的不一样，那么就是一个好数。

数字0/1/8，180度翻转之后还是本身，数字3/4/7,180度翻转之后形成不了数字，数字2和数字5翻转之后是对方，数字6和数字9翻转之后也是对方。

比如数字17，反转之后不是数字，那么不是好数。比如数字18，翻转之后还是数字18，也不是好数。比如数字19，翻转之后是16，是好数。

2、明白题意之后，这道题笔者最开始想要看看有没有什么数学规律，能够比较便捷地计算，但后来发现，好像还是暴力迭代最容易做了。

不过暴力迭代法中间也有技巧。

碰到一个数字，不断地对10取余数，取出末位，判断末位是三种数字中的哪一种。

这个判断如果一个个去判断，还是很慢。可以用set.count()，会快很多。但还有一种更快的做法，如下述代码：

int rotatedDigits(int N)     {        vector
     
      judge={1,1,2,0,0,2,2,0,1,2};//0表示形成不了有效数字        int j,t,count=0;                       //2表示出现了2/5/6/9        bool flag=0;        for(int i=1;i<=N;i++)        {            j=i;            flag=0;            while(j)            {                t=j%10;                if(judge[t]==0)                {                    flag=0;//这里要flag=0，不然比如32，就出错了                    break;                }                else if(judge[t]==2)                    flag=1;                j/=10;            }            if(flag==1)                count++;        }        return count;            }
     

上述代码实测9ms，beats 37.13% of cpp submissions。

 

3、改进：

看了一些discuss的代码，发现大家大体上都是暴力迭代法实现的，但是他们就是能跑到4ms……

看了他们的方法，自己实现了一下，代码分享给大家，如下：

bool isvalid(int n)    {        bool flag=false;        while(n>0)        {            if(n%10==2)                 flag=true;            else if(n%10==5)                 flag = true;            else if(n%10==6)                 flag=true;            else if(n%10==9)                 flag=true;            else if(n%10==3)                 return false;            else if(n%10==4)                 return false;            else if(n%10==7)                 return false;            n/=10;        }        return flag;    }    int rotatedDigits(int N)     {        int res=0;        for(int i=1;i<=N;i++)        {            if(isvalid(i))                res++;        }        return res;    }

代码思想大同小异，笔者2中的代码，也是逐个判断是否为好数，然后count++。但是判断的过程不一样。

笔者在函数内部实现判断，上述代码是另外定义一个函数来判断，照理来说，调用函数这个过程会花费一些时间。

此外，笔者的代码多了一个要判断flag的值是否为1的过程，而上述代码没有这个过程。

总的来说，比起大神的代码，多了判断flag==1的的过程，少了函数调用的过程，这样能省5ms……

 上述代码实测4ms，beats 95.00% of cpp submissions。