题解 | #整数中1出现的次数#

暴力解法，毫无感情

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
      int res = 0;
      
      for (int i = 1; i <= n; ++i) {
        int num = i;
        while (num) {
          int tmp = num % 10;
          num = num / 10;
          if (tmp == 1) {
            ++res;
          }
        }
      }
      
      return res;
    }
};

按位计算

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
      int base = 1;
      int res = 0;
      
      while (base <= n) {
        int cur = (n / base) % 10;
        int low = n % base;
        int high = n / base / 10;
        
        //  当前位为 0  1  大于1的三种情况
        if (cur == 0) {
          res += high * base;
        } else if (cur == 1) {
          //  当前位为1 不借位和借位两种情况
          //  这里单纯low+1不理解
          res += low + 1 + high * base;
        } else {
          res += (high + 1) * base;
        }
        
        //  基数增加
        base *= 10;
      }
      
      return res;
    }
};