题目难度：二星
考察点：二分查找

方法：模拟

1.分析：

对于这个题我们首先要搞清楚什么样的数是“好数”，对于数字0-9，有如下三种情况:
a. 0,1,8旋转180°之后是它本身；
b. 2,5,6,9旋转180°之后是另外一个不同的数；
c. 3,4,7旋转180°之后不是一个有效的数字。
那么根据这三种情况，我们可以判断如果一个数含有情况b中的任一数字，且不包含情况c中的任一数字，那么这个数就是“好数”，对于一个数中是否含有情况a中的数字并没有太大的关系，即情况a中的数字是可有可无的，所以我们就可以将i从2一直循环到n，判断i中是否满足条件（即上述的条件）即可。对于如何判断一个数是否包含某个数字，将这个数转换为字符串，然后在进行判断比较方便。

算法实现：
(1). 输入一个n。
(2). 列出好数中必须含有的数字rot = "2569"和必须不能包含的数字bad = "347"。
(3).遍历[2,n]，将i转化为字符串，然后判断是否包含必有rot字符串中的数字和不能包含bad字符串中的数字，如果满足条件记录结果。
(4). 输出结果ans。

2.复杂度分析：

时间复杂度：O(n) 
空间复杂度：O(1)

3.代码： 

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, ans = 0; cin>>n;
    string rot = "2569", bad = "347";
    for(int i=2; i<=n; i++) {
        string s = to_string(i);
        if(s.find_first_of(bad)==s.npos && s.find_first_of(rot)!=s.npos) ans++;
    }
    cout<<ans<<endl;
    return 0;
}