第七十题
方法一：直接遍历，并且按位统计
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        
        // 方法1：直接遍历n个数，每个数判断有几个1
        int num = 0;
        // 遍历到n
        for (int i = 1; i <= n; ++i)
        {
            // 直接按位判断是不是结果
            for (int a = i ; a > 0; a = a/10)
            {
                if (a%10 == 1)
                    ++num;
            }
        }
        
        return num;
    }
};


方法二：按位的价值统计
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        
        // 方法2：思路：200-300 和 300-400 出现的次数应该是一样的
        // 所以。我只要知道这一位出现过多少次就好了，
        // 比如说1-1000 在个位出现过几次100次1-9 所以总共第一位只会有一100次1，价值为1
        // 在十位的 出现过10次，每次价值为10 （11,12,13。。。）
        int ans = 0;
        int value=1;
        int num=n;
        while(num!=0)
        {
            int temp=num/10*value;
            // 判断边界
            // 如果说当前的数字大于1，说明是会出现过完整的一次
            // 假设是124 看的是十位的1，因为到了24 说明 前面的10、11、12都是全的，所以要直接加上
            if(num%10>1) 
                temp=temp+value;
            // 看到上面124 就要想到 115 这种情况，十位是1，那么出现的次数就不是value了
            // 就要看最后一位是5，说明 十位出现过5次
            // 在比如说 2158，看百位是1，就要加上最后两位的值58
            if(num%10==1)
                temp=temp+(n%value)+1;
            num/=10;
            value*=10;
            ans+=temp;
        }
        return ans;
    }
};