题目的主要信息：

根据题目要求，输出小于 n 的与 7 有关数字的个数，包括 7 的倍数，还有包含 7 的数字。

方法一：

枚举所有小于n的数字，同时用一个count来记录与7有关的数字个数，判断每一个数字是否与7有关，若有关则count加1。用isRelated函数判断数字n是否与7有关，首先判断n是否是7的倍数，如果不是7的倍数则判断n中是否含有7，每次对10取余判断，判断完后整个数字向右移动一位，这样高位就移动到了低位，可以继续用取余判断。判断是否包含7如下图例： alt

具体做法：

#include<iostream>

using namespace std;

bool isRelated(int n){//判断是否和7有关的函数
    if(n%7==0){//7的倍数
        return true;
    }
    while(n!=0){//判断是否含有7
        if(n%10==7){
            return true;
        }
        else{
            n=n/10;
        }
    }
    return false;
}
int main(){
    int n;
    while(cin>>n){
        int count=0;//记录总共有多个与7有关的数字
        for(int i=1;i<=n;i++){//枚举每个数字
            if(isRelated(i)){
                count++;//计数加1
            }
        }
       cout<<count<<endl;
    }
}

复杂度分析：

时间复杂度： $O (n)$ ，需要枚举n个数字。
空间复杂度： $O (1)$ ，只用了常数空间。

方法二：

方法二总体和方法一相同，只是在判断是否和7相关的时候转换为字符串来做，这么做的目的是字符串中有find函数可以快速判断是否包含7，而不用逐位位移、逐个判断。int转为string的函数是to_string，用find函数判断是否含有7。

具体做法：

#include<iostream>
#include<sstream>

using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        int count=0;
        for(int i=1;i<=n;++i)//枚举所有数字
        {
            string str;
            str=to_string(i);//转为字符串
            if(i%7==0 || str.find('7')!=str.npos)//判断是否和7相关
            {
                count++;
            }
        }
        cout<<count<<endl;
 }
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，需要枚举n个数字。
空间复杂度： $O (1)$ ，只用了常数空间。

题解 | #挑7#

题目的主要信息：

方法一：

方法二：