找规律，数学问题，求公式就对了

1. 我们把0-n(0-n和1-n结果一样)位数字低位对齐排列，为了更直观一点，我们将高位的0也补全，例如：
   
2. 不难发现，如上图蓝色标记，个位的数字是0-9（出现1次）循环的，10个数一个周期，那么十位呢？ 0-9（出现10次）循环的，100个数一个周期;百位0-9（出现100次）循环的，1000个数一个周期......
3. 对于一个周期内有多少个1，很容易得出，即为周期数的1/10。但稍等，上面浅蓝色的部分不足一个周期，这部分有多少个1？其实也很容易，毕竟1全部分布在周期的1/10-2/10之间了，只要知道不完整周期最大的位置在哪就行了，我们以n=13来看：个位，1个完整周期，不完整周期最大到3，3>=2，有1个1；十位，0个完整周期，不完整周期最大到13，13<20且13>=10，有13-10+1=4个1。
4. 总结一下：

• 对于每一位，它的周期为p10，周期的1/10为p1，我们求它的完整周期数和不完整周期最大位置：
• 完整周期数 = n 整除 p10（即10,100,1000,...），那么这些周期内的1的数量=每个周期内的数量×完整周期数：p1×(n//p10)
• 不完整周期的位置可以用取模获取，即m=n%p10，m的位置有三种情况：
  m大于所有1出现的位置，即m>2p1，1的数量相当于一个完整周期p1； m处于1出现的位置，即m<2p1且m>=p1，1的数量=m-p1+1； m小于所有1出现的位置，即m<p1，没有1。
• 计算每一位1出现的数量，停止条件为某一位没有完整周期。

5. 总结个公式（整除//，取模%，i表示位数从低到高，p10为周期，p1为1所在位置）：
6. Python3代码如下：

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        num,p1,p10 = 0,1,10
        while n//p1:
            m = n % p10
            if m >= 2*p1: num += p1*(n//p10) + p1
            elif m >= p1: num += p1*(n//p10) + m-p1+1
            else: num += p1*(n//p10)
            p1,p10 = p10,p10*10
        return num

7. 时间复杂度：O(i) 输入为几位就是循环几次。
   空间复杂度：O(1) 4个常数num,p1,p10,m。