题目描述

求出1~ 13的整数中1出现的次数,并算出100 ~ 1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

思路解析

没得思路，又是一道让人崩溃的题目。能想到的就是十位百位的一个个分割开，看看是不是1。但是转念一想，这么暴力。。。。面试问着，不是铁定凉凉。我甚至去想了转换为2进制进行运算，也许能出现好效果？然后并没有，却发现了将一个十进制数直接&1可以判断是否是奇偶函数）。没有更好的办法，于是直接看了别人解答，发现了一个LeetCode上面的大佬解决这个问题，很详细又是动画又是图片的，生怕我这个傻孩子看不懂。唉，菜鸡の叹息！
点击去往大佬的去处。。。。。

代码

public class Solution {public int NumberOf1Between1AndN_Solution(int n) {int digit = 1, res = 0;int high = n / 10, cur = n % 10, low = 0;while(high != 0 || cur != 0) {if(cur == 0) res += high * digit;else if(cur == 1) res += high * digit + low + 1;else res += (high + 1) * digit;low += cur * digit;cur = high % 10;high /= 10;digit *= 10;}return res;}
}