剑指offer第二版——面试题43（java）

面试题：1~n整数中1出现的次数

题目：

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

如输入12,1~12这些整数中包括1的数字有1、10、11和12，1一共出现了5次

【思路】

剑指offer上的解释有点看不懂囧，参考：https://www.cnblogs.com/wangkundentisy/p/8946858.html

对于一个形如xxxx的数，如要计算1出现在十位的数的个数，即xx1x的个数，分为三种情况

① xxab，a>1

a>1时，令a=1，则无论前面的两位xx取什么，都有相应的10个数可与之组合（如前面取23，后面可有10~19与其组合为2310~2319）

此时的数的取值为（xx+1）*10^(2-1)  ——xx+1是因为，若xx为22，则可从0开始取值，一直到22，实际是23个取值；10^(2-1）是因为在十位上时，位置标志为2，然而与之相对应的只有10个数，需要2-1

② xxab，a=1

a=1时，a只有一种取值，即1，且受后面b的影响，与①的区别主要在于：当xx取到最高时（如2315时，23固定后，只能从10~15=6个数，而2325可从10~19=10个数），不再是10个数都是可取的，因此，分开计算

此时数的取值为(xx)*10^(2-1)+(b+1) ——前面xx其实是代表的xx-1+1，指的是从0开始取值，直到最高位-1（xx-1），当xx取最高位时，后面只能取10~1b——b+1个数

③ xxab，a=0

a=0时，xx0b，此时xx只能取到0~(xx-1)——共xx种取值，每种取值对应10^(2-1）个数

此时数的取值为（xx）*10^(2-1) ,当xx取最高位时，十位上无法出现1（因为超过了数本身）

【方法】

所以总的来说，对于从右到左数的第i位（位上数为x），出现1的次数为：

① x>1，(高位+1)*10^(i-1) 

② x=1，(高位)*10^(i-1)+(低位+1)

③ x=0，(高位)*10^(i-1)

public class Q43 { public static void main(String[] args) { int a = 10000; System.out.println(howManyOne(a)); } public static int howManyOne(int x) { // 如果是个位数，只出现1次 if(x<10) { return 1; } int left = 0; double count = 0; int re = x; int sum = 0; while(re!=0) { left = re; re = re/10; // 当前位的数字==1 if(left==1) { sum = (int) (sum + re*Math.pow(10, count)+x%Math.pow(10, count+1)); // 当前位的数字==0 }else if(left==0) { sum = (int) (sum + re*Math.pow(10, count)); // 当前位的数字>1 }else { sum = (int) (sum + (re+1)*Math.pow(10, count)); } count++; } return sum; } }

【其他】

如果要计算其他数字出现的次数也是相同的，只是把用于比较的1改为该数（1~9）即可

如果要计算0出现的次数，会有所不同，在最后需要把当0出现在第一位的次数减掉

public static int howManyZero(int x) { // 如果是个位数，只出现1次 if(x<10) { return 1; } int stad = 0; int left = 0; double count = 0; int re = x; int sum = 0; while(re!=0) { left = re; re = re/10; // 当前位的数字==0 if(left==stad) { sum = (int) (sum + re*Math.pow(10, count)+x%Math.pow(10, count+1)); // 当前位的数字!=0 }else { sum = (int) (sum + (re+1)*Math.pow(10, count)); } count++; } return sum-(int) ((re+1)*Math.pow(10, count-1)); }