编程之美2.4——“1”的数目

2024-09-01 05:32

文章标签 2.4 编程数目之美

本文主要是介绍编程之美2.4——“1”的数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：给定一个正整数N，写出1到N（包含N）的所有正整数，然后数一下其中出现的所有N的个数。
举个例子，假设你输入的是11，则1到11的所有正整数为：
1，2，3，4，5，6，7，8，9，10，11
其中1出现了四次（1，10，11），请编写一个程序完成这个任务。
最暴力的解法这里不用说，因为如果面试的话肯定会死，微软的面试要是写出这种代码就能活下来也太容易了。
当我第一次看到这道题时，我先自己想了一下。不过没想出来，后来看了答案发现是我自己的思路有问题。我的思路是由最高位开始算，可解法偏偏是由最低位开始算。后来仔细想一下，从最低位开始算的这种思路实在是精妙。

问题分析

暴力循环不行，所以换个角度来看。可以把问题这样分解，从1到N的所有数字中，各位上有多少个1，十位上有多少个1，百位上有多个1.。。。。。。。
对于每一个位数字，可以分类讨论

1：该位数字大于1

2：该位数字等于1

3：该位数字等于0

之所以要分为3种情况，是因为“1”是一个特殊数字。

对于213。

如果十位数字是1，则十位上1的个数不仅和高位数字2有关，也和低位数字3有关——110-119，210-213
如果十位数字是2（大于1）即223，则此时十位上出现1的次数只与高位数字有关——110-119，210-219。
如果十位数字是0（小于1）即203，则此时十位上出现1的次数也只与高位数字有关——110-119
上述就是问题的关键

下面是一个简单的实现：

/*
get the number of 1
*/
#include <iostream>
#include <string>
using namespace std;
int calc(int n){auto count=0;int factor=1;int lowerNum=0;int currentNum=0;int highNum=0;while(n/factor!=0){lowerNum=n-(n/factor)*factor;currentNum=(n/factor)%10;highNum=n/(factor*10);switch(currentNum){case 0:count+=highNum*factor;break;case 1:count+=highNum*factor+lowerNum+1;break;case 2:count+=(highNum+1)*factor;break;}factor*=10;}return count;
}
int main(int argc,char **argv){int num=0;cout<<"cin num: "<<endl;cin>>num;int count=calc(num);cout<<count<<endl;return 0;
}