从1到n整数中1出现的次数-剑指offer-Java

拼搏现实的明天。 2021-12-09 22:25 255阅读 0赞

## 题目描述 ##

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

### 解题思路： ###

求1的个数，要知道数的增加都是0-9，然后每次增加0-9就会有一个1。增加过程中，出现1的个数，就是1-该数中1的个数

例如534，1的个数为：个位1的个数+十位1的个数+百位1的个数=（53\*1+1）+（5\*10+10）+（0\*100+100）=214

详情解释请看：https://blog.csdn.net/yi\_Afly/article/details/52012593

本机测试代码：

> 1.  package pratice714;
> 2.  public class num1ofInt714 \{
> 3.      public static int NumberOf1Between1AndN\_Solution(int n) \{
> 4.          int count = 0;
> 5.          for(int i=1;i<=n;i\*=10)
> 6.          \{
> 7.              int a = n/i; int b = n%i;
> 8.              System.out.println("a: "+a+" ");
> 9.              System.out.println("b: "+b+" ");
> 10.             count += (a+8) / 10 \* i + ((a % 10 == 1)? b + 1 : 0);
> 11.             System.out.println("count: "+count+" ");
> 12.         \}
> 13.         return count;
> 14.     \}
> 15. //https://blog.csdn.net/yi\_Afly/article/details/52012593
> 16.     public static int NumberOf1Between1AndN\_Solution2(int n) \{        
> 17.         if(n<1) return 0;
> 18.         int count = 0; int base = 1; int round = n;
> 19.         while(round>0)
> 20.         \{
> 21.             int weight = round%10; //当前的个位数
> 22.             round /= 10; //下次运行做准备
> 23.             count += round \* base; //当前去除个位，前几位乘base，base表示当前位数，十位\*10，百位\*100；
> 24.             if(weight == 1)
> 25.                 count += (n%base) + 1;
> 26.             else if(weight > 1)
> 27.                 count += base;
> 28.             base \*= 10;
> 29.         \}
> 30.         return count;
> 31.     \}
> 32.     public static void main(String\[\] args) \{
> 33.         int data = 13;
> 34.         int result = NumberOf1Between1AndN\_Solution(data);
> 35.         System.out.print("result: "+result+" ");
> 36.         
> 37.         int result2 = NumberOf1Between1AndN\_Solution2(data);
> 38.         System.out.print("result: "+result2+" ");
> 39.     \}
> 40. \}

### **扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20211209/28dd2778f1bf49cfa2029a9a9c920601.png