Ex43 1~n整数中1出现的次数

题目描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

解题思路

代码

class Solution
{
public:
  int
  countDigitOne (int n)
  {
    std::string str = std::to_string (n);
    return count_digit_one (str, 0);
  }

private:
  int
  count_digit_one (std::string &str, int start)
  {
    if (start >= str.size ())
      return 0;
    int first = str[start] - '0';
    int length = str.size () - start;
    if (length == 0 && first == 0)
      return 0;
    if (length == 1 && first > 0)
      return 1;
    int num_first_digit = 0;
    if (first > 1)
      num_first_digit = (int)std::pow (10, length - 1);
    else if (first == 1)
      num_first_digit
          = std::stoi (std::string (str.begin () + start + 1, str.end ())) + 1;
    int num_other_digits
        = first * (length - 1) * (int)std::pow (10, length - 2);
    int number_recursive = count_digit_one (str, start + 1);
    return num_first_digit + num_other_digits + number_recursive;
  }
};

结果

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.5 MB, 在所有 C++ 提交中击败了5.05%的用户