题解 P1590 【失踪的7】

· · 题解

读完题目后,关于数字7我们可以知晓两种情况:

① 7,17,27.....这些数字需要舍去
② 71,72....这些数字需要舍去
等于说,只要出现了7,就舍去,我第一时间想到用字符串来处理,不多说,上代码:

#include<stdio.h>
/*思路:因为题目要求只要是7就pass,所以说71,72.....也是不符合要求的数,我们可以用字符串处理
原理:用到了sprintf函数,用这个函数把数字转换成字符串,这个函数包括三个参数:储存结果的字符串地址,格式化字符串,输入的数据地址
*/
int main() 
{
    int total, num;//定义两个变量,分别是总数字数和每次读入数据时的临时变量
    scanf("%d", &total);
    for (int i = 0; i < total; i++)//采用了边读取边处理的方法
    {
        scanf("%d", &num);
        int count = 0;

        for (int j = 1; j <= num; j++)
        {
            char num[100];//创建了一个保存结果的字符串数组
            int flag = 0;//开关
            sprintf(num, "%d", j);//将每一位数字都转换成字符串
            for (int k = 0; num[k]!='\0'; k++)//判断结束语句
            {
                if (num[k] == '7') //只要出现7,开关打开,退出循环
                {
                    flag = 1;
                    break;
                }
            }
            if (flag==1)//如果出现了7,就继续外层循环
                continue;
            else
                count++;//如果没有出现7,计数器++
        }
        printf("%d\n", count);
    }
    return 0;
}

出现的问题:超时,因为代码中使用了三层循环,当需要判断的目标数字很多时就会超时

上面的代码在最后三个测试点tle,所以说思路虽然可以但是费时间

于是乎我又想到了另外一种做法:进制转换

根据题意,只要遇到7就pass,有点像只要遇到9+1就进一位 ,十进制中 1234 = 1*10^3 + 2*10^2 + 3*10^1 + 4*10^0,这道题只需要把10变成9就可以了.

#include<stdio.h>
#include<math.h>
/*思路:十进制中,1234 = 1*10^3 + 2*10^2 + 3*10^1 + 4*10^0,去掉了一个数字7,变成了9进制,模拟进制转换
注意点:因为处理的数据范围是(n≤2^32-1),所以说需要用到long long int类型来储存,为了防止出错,全部设为lld类型
*/
int main() 
{
    long long int num, n;//定义临时变量num和总数字n
    scanf("%lld", &n);

    for (int i = 0; i < n; i++)//边读取边处理
    {
        scanf("%lld", &num);
        long long int sum = 0, count = 0,temp;//每次处理前将相关数据重新定义,赋值
        while(num)//当num不为0的时候进行处理
        {
            temp = num % 10;//取num的最右边位数字(第一次取的是个位)
            if (temp < 7)//分支判断,决定计算公式
                sum += temp * pow(9, count);
            else
                sum += (temp-1) * pow(9, count);
            num /= 10;//最右位的数字被处理后就舍去,倒数第二右位变成最右位
            count++;//指数自增
        }
        printf("%lld\n", sum);//输出结果
    }
    return 0;
}

刚学了几个月的小垃圾,什么都还不会,希望自己的思路能帮到大家,如果有错误欢迎指正,谢谢!