给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。

例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。

输入N(1 <= N <= 10^9)

输出包含1的个数

暴力的做法是：直接枚举 1−>n的数字，逐一统计其中 1的数量。每次统计 1 的数量复杂度为 O(log(n))，总共需要统计 n 次，这样总的复杂度为 O(nlog(n))。数据范围 1e9，肯定会超时。

反过来，我们枚举每 1位是 1 的数字，其中有多少个是小于 n 的，例如： n=163。

个位为 1 的数包括： 1,11,21...161 。共 17个。

十位为 1 的数包括： 10,11,12...19,110,111...119。共 20个。

百位为 11 的数包括： 100,101.。。163。共 64 个。

按照这种方式， 111 恰好会被统计 3 次，因为它包含 3 个 1 。

我们对 n 的每一位进行处理，统计有多少这 1位为 1 且小于 n 的数字。算法的复杂度为 O(log(n)) 。

本体包含一定的数位DP的思想，可以自行去了解一下