面试题 43. 1 ～ n 整数中 1 出现的次数

输入：n = 12
输出：5

输入：n = 13
输出：6

from functools import lru_cache

class Solution:
    @lru_cache
    def countDigitOne(self, n: int) -> int:
        if n < 1:
            return 0
        s = str(n)
        high = int(s[0])
        base = pow(10, len(s) - 1)
        lows = n % base
        return self.countDigitOne(base - 1) + lows + 1 + self.countDigitOne(lows) if high == 1 else high * self.countDigitOne(base - 1) + base + self.countDigitOne(lows)

class Solution {
    public int countDigitOne(int n) {
        if (n < 1) {
            return 0;
        }
        String s = String.valueOf(n);
        int high = s.charAt(0) - '0'; // 最高位
        int base = (int) Math.pow(10, s.length() - 1); // 基数
        int lows = n % base; // 低位
        return high == 1
            ? countDigitOne(base - 1) + countDigitOne(lows) + lows + 1
            : high * countDigitOne(base - 1) + countDigitOne(lows) + base;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var countDigitOne = function (n) {
  let res = 0;
  let i = 1;
  while (i <= n) {
    let high = ~~(n / i / 10);
    let cur = ~~(n / i) % 10;
    let low = n - ~~(n / i) * i;
    switch (cur) {
      case 0:
        res += high * i;
        break;
      case 1:
        res += high * i + low + 1;
        break;
      default:
        res += (high + 1) * i;
    }
    i *= 10;
  }
  return res;
};

class Solution {
public:
    int countDigitOne(int n) {
        long long digit = 1;
        int count = 0;
        int high = n / 10;
        int cur = n % 10;
        int low = 0;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                count += high * digit;
            } else if (cur == 1) {
                count += high * digit + low + 1;
            } else {
                count += (high + 1) * digit;
            }
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return count;
    }
};