思路是依次计算每个位上的1的个数。算法复杂度O(logN)

首先拿n = 190举例，理解这么做是可行的，然后再想办法用代码实现它。

1）首先，求个位上出现1的个数，即个位固定为1，那么就是1，11，21，31，...... ，181，这里个位上共有19个1。

2）接下来，求十位上出现的1的个数，即十位固定为1，那么就是11，12，13，...... ，19；111,112,113，...... ， 119,这里十位上共有20个1。注意，这里算的是十位上为1的个数，因此例如“11”这个数，个位上的1已经在上一轮统计过；同理，“111”这个数，百位上的1将在下一轮进行统计。因此我们只需关注当前位数的1。

3）最后，求百位上出现1的个数，即百位固定为1, 那么就是100，101，102，103，...... ，189，190，百位上从共91个1。 最终，将个位、十位、百位上的1的出现个数全部加起来，即为所求。

然后是编码方面，理解了上面的思路，我们就没必要一个一个去统计了。这里有两点关键的。

首先，是用value变量记录当前统计位的价值，比如个位时，当前位的价值value为1；十位时，当前位的价值value为10；百位时，当前位的价值value为100，以此类推。这样一来，计算个位的时候，cur_count = num / 10 * value = 190 / 10 * 1 = 19，即个位上出现19次1。

其次，要额外考虑当前位等于1的情况。比如 n = 190，此时百位固定为1，从100到190，共91个，并不等于100，即并不等于value的值。只有当前位大于1时，如n = 202，此时当百位固定为1时，从100到202中，100到199是完全存在的，即共100个，等于value的值。因此，要额外考虑当前位等于1的情况，此时1出现的次数不一定等于value。

最后上代码，主要是根据两个关键点，理解while循环中的语句。可以自己举一些三位数的例子，脑跑一边代码，记录中间变量，即可理解。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int base = 1;//当前位的价值
        int count = 0;
        int num = n;
        while(num != 0){
            int cur_count = num / 10 * base;
            if(num % 10 > 1) cur_count = cur_count + base;
            if(num % 10 == 1) cur_count = cur_count + (n % base) + 1;
            num = num / 10; 
            base = base * 10;
            count = count + cur_count;
        }
        return count;
    }
};