挑7

描述

输出小于 n 的与 7 有关数字的个数，包括 7 的倍数，还有包含 7 的数字（如 17 ，27 ，37 ... 70 ，71 ，72 ，73...）的个数（一组测试用例里可能有多组数据，请注意处理）
输入描述：
多组输入每组输入 1 个正整数 N 。( N 不大于 30000 )
输出描述：
不大于N的与7有关的数字个数，例如输入20，与7有关的数字包括7,14,17.
示例
输入：20
10
输出：3
1

方法一

思路分析

直接的思路为：如果给定的数小于7，则直接输出0；否则遍历，如果遍历的数是7的倍数或者数字中含有7（直接利用python中的判断字符串中是否存在’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(1)$

方法二

思路分析

同方法一，如果给定的数小于7，则直接输出0；否则遍历，如果遍历的数是7的倍数或者数字中含有7，此时判断数中是否含有7是通过判断给定的数中个位十位百位千位以及以上的位数中是否存在7.

图解


核心代码 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n=0;
    while(cin>>n)
    {
        int sum=1;
        if(n<7) sum=0;
        else{
            for(int i=8;i<=n;i++)
            {
                int index_1=0;
                int index_2=0;
                if(i%7==0)
                    index_1=1;//判断是否为7的倍数
                while(i>0)
                {
                    if(i%10==7) index_2=1;//判断是否包括7
                    else i=i/10;
                }
                if(index_1||index_2)//如果i为7的倍数或者7出现在位数上
                    sum++;
            }
        }
        cout<< sum<<endl;
        
    }
    return 0;
}
此代码时间超出，因此进行改进。 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n=0;
    while(cin>>n)
    {
        int sum=1;
        if(n<7) sum=0;
        else{
            for(int i=8;i<=n;i++)
            {
                if(i%7==0||i%10==7||(i%100)/10==7||(i%1000)/100==7||(i%10000)/1000==7)//如果i为7的倍数或者7出现在位数上
                    sum++;
            }
        }
        cout<< sum<<endl;
        
    }
    return 0;
}
复杂度分析
  • 时间复杂度：时间复杂度为$O(n)$
  • 空间复杂度：空间复杂度为$O(1)$