题目描述：

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

示例：

输入: 10
输出: 4
解释:
在[1, 10]中有四个好数： 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。

提示：

N 的取值范围是 [1, 10000]。

解题思路一：暴力硬算，剪枝是当数中出现3.4.7会直接break。charge|=rem == 2 || rem== 5 ||rem == 6||rem == 9;是一个二进制或运算，等同于if(rem == 2||rem== 5||rem == 6||rem == 9) charge=true;

class Solution {
public:
    int rotatedDigits(int n) {
        //x旋转之后是有效的那么3,4,7不能出现。而2,5,6,9必须出现一次。0.1.8可以出现n次。
        int count=0;//计数，即返回结果
        for(int i=1;i<=n;++i){
            int num=i;
            bool charge=false;//记录是否出现了2,5,6,9.
            while(num){
                int rem=num%10;
                if(rem==3||rem==4||rem==7) break;
                charge|=rem==2||rem==5||rem==6||rem==9;
                num/=10;
            }
            if(charge&&!num) ++count;
        }
        return count;
    }
};

假设数长平均为r
时间O(nr)，空间O(1)

解题思路二：动态规划，大于9的数分为两个部分一个是i%10，一个是i/10；dp数组存储3种值，0：不包含3、4、7的坏数，1：含有3、4、7的坏数，2：好数，通过dp数组可以知晓a和b是否含有3、4、7或2、5、6、9，直接判断出n是否是好数

class Solution {
public:
    int rotatedDigits(int n) {
        //x旋转之后是有效的那么3,4,7不能出现。而2,5,6,9必须出现一次。0.1.8可以出现n次。
        vector<int> dp(n+1,0);
        int count=0;//计数，即返回结果
        for(int i=1;i<=n;++i){
            if(i==3||i==4||i==7||dp[i%10]==1||dp[i/10]==1) dp[i]=1;
            else if(i==2||i==5||i==6||i==9||dp[i%10]==2||dp[i/10]==2){
                dp[i]=2;
                ++count;
            }                        
        }
        return count;
    }
};

时间O(n)，空间O(n)

解题思路三：转为字符串求解，利用好STL。不会stl的可以看下下面的注解。

class Solution {
public:
    int rotatedDigits(int n) {
        //x旋转之后是有效的那么3,4,7不能出现。而2,5,6,9必须出现一次。0.1.8可以出现n次。
        int count=0;//计数，即返回结果
        for(int i=1;i<=n;++i){
            string num = to_string(i);
            if (num.find_first_of( "347") == -1 &&
                num.find_first_of("2569") != -1) {
                count++;
            }                     
        }
        return count;
    }
};

string.find()函数有三个参数。
使用样例：

string str1(“the usage of find can you use it”);

string str2(“the”);

上面定义出了两个字符串；

str1.find(str2); // 从串str1中查找时str2，返回str2中首个字符在str1中的地址

str1.find(str2,5); // 从str1的第5个字符开始查找str2

str1.find(“usage”); // 如果usage在str1中查找到，返回u在str1中的位置

str1.find(“o”); // 查找字符o并返回地址

str1.find(“of big”,2,2); // 从str1中的第二个字符开始查找of big的前两个字符

string.find_first_of()函数参数与find()基本相同。

特别注意：

find_first_of 函数最容易出错的地方是和find函数搞混。它最大的区别就是如果在一个字符串str1中查找另一个字符串str2，如果str1中含有str2中的任何字符，则就会查找成功，而find则不同；

比如：

string str1(“I am change”);

string str2(“about”);

int k=str1.find_first_of(str2); //k返回的值是about这5个字符中任何一个首次在str1中出现的位置；
参考链接