北京自适应网站建设,山东省建设部网站官网,网站动态背景欣赏,wordpress 外链#xff08;害#xff0c;做题是真的慢#xff0c;这面试给我这题我估计就傻了#xff09;
题目#xff1a; 给定一个整数 n#xff0c;计算所有小于等于 n 的非负整数中数字 1 出现的个数。
题解#xff1a; 首先看看整数范围 0 n 10^9 不能遍历#xff0…害做题是真的慢这面试给我这题我估计就傻了
题目 给定一个整数 n计算所有小于等于 n 的非负整数中数字 1 出现的个数。
题解 首先看看整数范围 0 n 10^9 不能遍历不过这也肯定不会简单到遍历
比如存在一个数 25103我们应该从哪里下手呢
我们是否可以考虑各个位置上个位十位…存在 1 的情况数量然后相加得到结果呢
我们先考虑一般情况 数字 xxx 4 yy百位上存在 1 的情况数量怎么算 想一想 100101102…199是不是百位上都是 1这种情况 100 种 在考虑一下百位前面的 xxx是不是总共有 (xxx 1) * 100 种 假设 xxx 是 123那么 123 1 yy 有 100 种122 1 yy 有 100 种 … 000 1 yy 有 100 种
接下来稍微扩展一下一般情况那数字 xxxx 4 y 十位上的情况是不是就是 (xxxx 1) * 10 种
接下来考虑特殊情况如果数字 xxx 1 yy 百位上是 1这怎么算呢 当前面是 xxx 时百位上为 1 的情况只有 yy 种但是当前面是 (xxx - n) 时情况有 100 种 所以是不是情况是 xxx * 100 yy 种 假设 xxx 是 123那么 123 1 yy 有 yy种但 122 1 yy则没有这种限制有 100 种
再一种特殊情况如果数字 xxx 0 yy 百位上是 0这怎么算呢 其实就是当前面是 xxx 时百位上为 1 的情况为 0 种当前面是 xxx - n) 时情况也都有 100 种 所以情况是 xxx * 100 种
接下来写代码就行了
class Solution {
public:int countDigitOne(int n) {int res 0;int f 1;int nn n / 10;while(nn ! 0) {nn nn / 10;f f * 10;}int flag 0;while(f ! 0) {int t n / f;n n % f;if(t 1) {res res n 1 flag * f;}else if(t 0) {res res flag * f;}else {res res (flag 1) * f;}flag flag * 10 t;f f / 10;}return res;}
};
