leetcode-788-Rotated Digits(使用vector替代if else的逐个判断)

题目描述:

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: 10
Output: 4
Explanation: 
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<int>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。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

扫码关注云+社区

领取腾讯云代金券