在网上看到大神的四行解法https://discuss.leetcode.com/topic/18054/4-lines-o-log-n-c-java-python

算法复杂度o(logn)，英文看着不习惯，仔细研究了下，文中举个例子：如果n为3141592

对于 m=1，表示个位， 个位为1出现的可能为0~314159 + 1（此处+表示连接，不是数学意义上的加号）的情况, 次数为（314159+1）
对于 m=10, 表示十位， 十位为1出现的可能为0~31415 + 10~19的情况，次数为（31415+1）*10 
对于 m=100, 表示百位， 百位为1出现的可能为0~3141 + 100~199的情况，次数为（3141+1）*100
对于 m=1000, 表示千位， 千位为1出现的可能为0~313 + 1000~1999 以及 314 + 1000~1592 两种情况，次数为 314 *100 + 593
以此类推

可见当所关注位数为1时，需要分为两种情况，(n/m + 8) / 10 * m 和尾部 ((n/m % 10 == 1)?1:0) * (n%m + 1)，此处+8很巧妙的
实现 当前分位上数字小于等于1的不进1，否则进1。如果为1，还需要加上尾部的(n%m + 1)种出现次数
代码如下，非常简洁：

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
         int ones = 0;
         for (long m = 1; m <= n; m *= 10)  //m用来标记位数
            ones += (n/m + 8) / 10 * m + ((n/m % 10 == 1)?1:0) * (n%m + 1);       
         return ones;
    }
}