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

从1到n整数中1出现的次数

程序员文章站 2024-03-07 18:26:03
...

给出一个具体数,计算得到从1开始到该数中出现1的次数

常规实现

1、遍历从1到该数字,计算每一个数字中1出现的次数
2、通过对n = n / 10,如果 每一次n%10等于1,则表明包含1,计数器加一,跳出条件为n=0
3、时间复杂度:O(logn)

/**
	 * 遍历数字得到结果,时间复杂度O(nlogn)
	 * 
	 * @param n
	 * @return
	 */
	public int NumberOf1Between1AndN_Solution(int n) {
		int count = 0;
		for (int i = 1; i <= n; i++) {
			count += Num(i);
		}
		return count;
	}

	private int Num(int num) {
		int res = 0;
		while (num != 0) {
			int temp = num % 10;
			if (temp == 1) {
				res++;
			}
			num /= 10;
		}
		return res;
	}

StringBuffer实现

1、遍历从1到n的数据,每一次将数据添加到StringBuffer中
2、将Stringbuffer转化为字符串,判断每一个字符串对应位置是否为1,如果为1,则计数器+1

/**
	 * 字符串查找
	 * 
	 * @param n
	 * @return
	 */
	public int NumberOf1Between1AndN_Solution2(int n) {
		StringBuffer s = new StringBuffer();
		for (int i = 0; i < n; i++) {
			s.append(i);
		}
		String reString = s.toString();
		int count = 0;
		for (int i = 0; i < reString.length(); i++) {
			if (reString.charAt(i) == '1') {
				count++;
			}

		}
		return count;
	}

数据规律

1、针对每一个数,可以判断个位、十位、百位中1出现的次数
2、首先来看一下个位:
个位中数字的变化规律是0-9,比如534,此时就可以将534拆分为53和4,此时在个位就会出现count = 53 * 1
之后需要看个位的数字:
(1)>1 :count+1
(2)=0:count
(3)=1:count+1
对于个位中出现>1和=1等于一的情况好像是冗余了,其实是为了迎合更高位
3、继续来看十位,变化规律依旧是0-9,比如:534,由于已经将个位数字已经计算过,此时只需要将53拆分为5和3,count = 5 * 10
此时就需要关注十位的数字:
(1)>1 :count = count+10
(2)=0:count = count
(3)=1:count = count + 个位数字+1(因为当十位等于1的时候,各位数字有多少个就表明此时十位数字1出现了多少次,比如12,表明10,11,12出现3次;16表明10,11,12,13,14,15,16出现7次,所以各位数字+1)
4、百位数字,变化规律依旧是0-9,比如534,由于已经计算过十位数字,此时就剩一个孤零零的5,那么就将5拆分为0和5,count = 0 * 100(如果有千位数字情况就不一样了)
(1)>1 :count = count+100
(2)=0:count = count
(3)=1:count = count + 十位数字+1
5、同理计算千位、万位数字

注意:要正确理解former的含义,比如当前计算为是各位,则former = 0
当前计算为是十位,former=个位数字,严格来讲是n%10,
13,则表示十位出现former+1=4次,10,11,12,13
当前计算为百位,former = 十位+个位数字,严格来讲是n%100
112,则百位出现1为112%100 = 12+1次,100,101,102,103…112

6、将所有计数器求和得到结果
7、总结
此处引用博客:https://blog.csdn.net/yi_Afly/article/details/52012593
从1到n整数中1出现的次数

public int NumberOf1Between1AndN_Solution3(int n) {
		if (n < 1) {
			return 0;
		}
		int roud = n;
		int base = 1;
		int weight = 0;
		int count = 0;
		while (roud != 0) {
			weight = roud % 10;
			roud = roud / 10;
			count += roud * base;
			if (weight == 1) {
				//将个位的情况调整与十位百位相同,事实上各位不需要区分
				count += (n % base) + 1;
			} else if (weight > 1) {
				count += base;
			}
			base *= 10;
		}
		return count;
	}

Over