题解 | #挑7#

HJ55 挑7

题目描述

输出小于等于 n 的与 7 有关数字的个数，包括 7 的倍数，还有包含 7 的数字（如 17 ，27 ，37 ... 70 ，71 ，72 ，73...）的个数（一组测试用例里可能有多组数据，请注意处理）

方法一：暴力算法

解题思路

对于方法一，我们直接使用暴力的方法进行判断，如果给定的数小于7，则直接输出0。否则遍历，如果遍历的数是7的倍数或者数字中含有7，则将其记录下来，最终输出结果。

解题代码

while True:
    try:
        n=int(input())
        sum=0
        if n<7:print(sum)# 预判断
        else:
            sum=1
            for i in range(8,n+1):
                if i%7==0 or'7' in str(i):# 7的倍数或者7在数字中
                    sum=sum+1
            print(sum)
    except:
        break

复杂度分析

时间复杂度：一层循环，时间复杂度为$O(N)O(N)$。

空间复杂度：对于暴力求解，没有引入新的地址空间，因此空间复杂度为$O(1)O(1)$

方法二：字符串方法

解题思路

对于方法一，我们对其进行改进，在进行是否和7相关的数字判断的时候，我们将其转化为字符串进行判断。这充分利用了字符串的find函数，来辅助我们对是否包含7进行判断。

解题代码

#include<bits/stdc++.h>
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)O(N)$

空间复杂度：常数级空间，因此空间复杂度为$O(1)O(1)$