LeetCode刷题：233. Number of Digit One

LeetCode刷题：233. Number of Digit One

原题链接：https://leetcode.com/problems/number-of-digit-one/

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example:

Input: 13
Output: 6 
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

题目大意

计算所有小于等于n的正整数中数字1的个数。
比如比13小的正整数中包含1的有1,10,11,12,13，一共有6个1。

解题思路

假设n=52，那么52下含有的1实际上等于50~52 + 1~49中有的1，也就等价于0~2 + 1~49中含有的1。

当n<10时，只有1个1。因此0~2只有1个1。

再来拆解1~49。1~49其实等价于40~49 + 30~39 + 20~29 + 10~19 + 1~9中的1的个数。

通过分析会发现，40~49, 30~39 , 20~29, 0~9中的1的个数是相同的！

而特殊的情况是10~19，它的1的数量其实等于10 + 0~9。

总结一下我们知道：countDigitOne(52) = countDigitOne(2) + countDigitOne(9) * 5 + 10。

这里其实还有一个特殊情况，就是当最高位恰好为1的时候，举个例子135。

那么100~135等价于36+0~35个1，那么：

countDigitOne(135) = 36 + countDigitOne(35) + countDigitOne(99)。

算法设计

package com.bean.algorithmbasic;

public class NumberofDigitOne {

	/*
	 * 找数学规律
	 * */

	public static int countDigitOne(int n) {

		if (n <= 0)
			return 0;
		if (n < 10)
			return 1;
		int count = 1;

		while (n / count > 9) {
			count *= 10;
		}

		if (n / count == 1) {
			return n % count + 1 + countDigitOne(n % count) + countDigitOne(count - 1);
		} else {
			return countDigitOne(n % count) + count + (n / count) * countDigitOne(count - 1);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 1234;
		// int n=147;
		// int n=265; result = -1970444362
		int result = countDigitOne(n);
		System.out.println("result = " + result);
	}

}

当 n = 1234时，运行结果：

result = 689