04.求从1到n整数中1出现次数

目录介绍

• 01.题目要求
• 02.问题分析
• 03.实例代码

01.题目要求

• 问题如下所示：
  • 输入一个整数n，求从1 到n这n个整数的十进制表示中1 出现的次数。
• 示例 :

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

02.问题分析

• 第一种：不考虑时间效率的解法
  • 累加1 到n 中每个整数中1出现的次数。我们可以每次通过对10 求余数判断整数的个位数字是不是1 。如果这个数字大于10，除以10 之后再判断个位数字是不是1 。
• 第二种：从数字规律着手明显提高时间效率的解法
  • 21345 作为例子来分析。我们把从1 到21345 的所有数字分为两段， 一段是从1 到1345，另一段是从1346 到21345。
  • 我们先看从01346 到21345 中1 出现的次数。1 的出现分为两种情况。首先分析1出现在最高位（本例中是万位）的情况。从01346 到21345 的数字中， 1出现在10000～19999 这10000 个数字的万位中， 一共出现了10000(10^4)个。
  • 值得注意的是， 并不是对所有5 位数而言在万位出现的次数都是10000 个。对于万位是1 的数字比如输入12345, 1 只出现在10000～ 12345 的万位，出现的次数不是10^4 次，而是2346 次，也就是除去最高数字之后剩下的数字再加上1 （即2345+1=2346 次）。
  • 接下来分析1出现在除最高位之外的其他四位数中的情况。例子中01346～21345 这20000 个数字中后4 位中1 出现的次数是2000 次。由于最高位是2，我们可以再把1346～21345 分成两段， 01346～11345 和11346～21345 。每一段剩下的4 位数字中， 选择其中一位是1 ，其余三位可以在0～9 这10 个数字中任意选择，因此根据排列组合原则，总共出现的次数是2*10^3=2000，一共有4位可以选择，所以一共是8000。
  • 至于从1 到1345 中1 出现的次数，我们就可以用递归求得了。这也是我们为什么要把1～21345 分成1～ 1345 和1346～21345 两段的原因。因为把21345 的最高位去掉就变成1345 ，便于我们采用递归的思路。

03.实例代码

• 如下所示

  public class Test {
  
      /**
       * 题目：输入一个整数n求从1 到n这n个整数的十进制表示中1 出现的次数。
       * @param n 最大的数字
       * @return 1-n中，各个数位1出现的次数
       */
      public static int numberOf1Between1AndN(int n) {
          if (n <= 0) {
              return 0;
          }
  
          String value = n + "";
          int[] numbers = new int[value.length()];
  
          for (int i = 0; i < numbers.length; i++) {
              numbers[i] = value.charAt(i) - '0';
          }
  
          return numberOf1(numbers, 0);
      }
  
      /**
       * 求0-numbers表的数字中的1的个数
       *
       * @param numbers 数字，如{1, 2, 3, 4, 5}表示数字12345
       * @param curIdx  当前处理的位置
       * @return 1的个数
       */
      private static int numberOf1(int[] numbers, int curIdx) {
  
          if (numbers == null || curIdx >= numbers.length || curIdx < 0) {
              return 0;
          }
          // 待处理的第一个数字
          int first = numbers[curIdx];
  
          // 要处理的数字的位数
          int length = numbers.length - curIdx;
  
          // 如果只有一位且这一位是0返回0
          if (length == 1 && first == 0) {
              return 0;
          }
  
          // 如果只有一位且这一位不是0返回1
          if (length == 1 && first > 0) {
              return 1;
          }
  
          // 假设numbers是21345
          // numFirstDigit是数字10000-19999的第一个位中的数目
          int numFirstDigit = 0;
          // 如果最高位不是1，如21345，在[1236, 21345]中，最高位1出现的只在[10000, 19999]中，出现1的次数是10^4方个
          if (first > 1) {
              numFirstDigit = powerBase10(length - 1);
          }
          // 如果最高位是1，如12345，在[2346, 12345]中，最高位1出现的只在[10000, 12345]中，总计2345+1个
          else if (first == 1) {
              numFirstDigit = atoi(numbers, curIdx + 1) + 1;
          }
  
          // numOtherDigits，是[1346, 21345]中，除了第一位之外（不看21345中的第一位2）的数位中的1的数目
          int numOtherDigits = first * (length - 1) * powerBase10(length - 2);
          // numRecursive是1-1234中1的的数目
          int numRecursive = numberOf1(numbers, curIdx + 1);
  
          return numFirstDigit + numOtherDigits + numRecursive;
      }
  
      /**
       * 将数字数组转换成数值，如{1, 2, 3, 4, 5}，i = 2，结果是345
       * @param numbers 数组
       * @param i 开始黑气的位置
       * @return 转换结果
       */
      private static int atoi(int[] numbers, int i) {
          int result = 0;
          for (int j = i; j < numbers.length; j++) {
              result = (result * 10 + numbers[j]);
          }
          return result;
      }
  
      /**
       * 求10的n次方，假定n不为负数
       * @param n 幂，非负数
       * @return 10的n次方
       */
      private static int powerBase10(int n) {
          int result = 1;
          for (int i = 0; i < n; i++) {
              result *= 10;
          }
          return result;
      }
  }