计数问题
题目：输入一个整数 n，求从1到n这n个整数的十进制表示中1出现的次数。 例如输入 12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。 分析：这是一道广为流传的 google面试题。用最直观的方法求解并不是很难，但遗憾的是效率不是很高；而要得出一个效率较高的算法，需要比较强的分析能力，并不是件很容易的事情。当然，google的面试题中简单的也没有几道。 一、直觉法 首先我们来看最直观的方法，分别求得 1到n中每个整数中1出现的次数， 然后把它们加起来就行了。 然而， google 的面试不是这么容易 让你过关的。 因为这种方法的复杂度是 O( n ) ,对较大的整数，运算时间太长 二、 新方法 我们通过分析数字的规律，找出加快计算速度的方法。 0 - 9 之间 所有数字中 出现的 1 为 1 个 0 –99 十位的1 有 10个 去掉十位后， 有10组 0~9 所以 共有 10 + 10 个 0 ~ 999 之间 百位的1 有 100 ...