欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

整数中1出现的次数(从1到n整数中1出现的次数)(剑指offer第32题)

程序员文章站 2022-07-10 13:31:10
...

一、题目描述

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

二、题目解析

看了别人的思路,简单易懂,图文并茂,讲解细致。链接如下:

https://blog.csdn.net/yi_afly/article/details/52012593

三、java代码

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

	public int NumberOf1Between1AndN_Solution(int n) {
          if(n<1){
        	  return 0;
          }
          int count = 0;
          int base = 1;   //记录每个位置的位数(个十百千万等)
          int round = n;  //记录位的数量,n是几位数
          while(round>0){
        	  int weight = round%10;
        	  round/=10;
        	  count += round*base;
        	  if(weight==1){
        		  count += (n%base)+1;
        	  }else if(weight >1){
				  count += base;
			 }
        	 base *= 10;
          }
		return count;
	}
}