从1到n整数中1出现的次数(Java)

题目

给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。 

示例:

输入: 13
输出: 6 
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        if(n <= 0){
            return  0;
        }
        if(n < 10){
            return 1;
        }
        String str = String.valueOf(n);
        int len = str.length();
        int first = str.charAt(0)-'0';
        String after = str.substring(1,len);
        int firstCount = 0;
        int SecondCount = 0;
        int third = 0;
        if(first== 1){
            firstCount = Integer.valueOf(after)+1;
        }else{
            firstCount = (int) Math.pow(10,len-1);
        }
        SecondCount = (int) ((first)*(len-1)*Math.pow(10,len-2));
        third = NumberOf1Between1AndN_Solution(Integer.valueOf(after));
        return firstCount+SecondCount+third;
    }
}

 

 思考一

注:(这里的 X∈[1,9] ,因为 X=0 不符合下列规律,需要单独计算)。

首先要知道以下的规律: 

从 1 至 10,在它们的个位数中,任意的 X 都出现了 1 次。 

从 1 至 100,在它们的十位数中,任意的 X 都出现了 10 次。 

从 1 至 1000,在它们的百位数中,任意的 X 都出现了 100 次。

依此类推,从 1 至 10^ i ,在它们的左数第二位(右数第 i 位)中,任意的 X 都出现了 10^(i-1) 次。
 

以21354为例,寻找1出现的次数:

个位:从1至21350中包含了2135个10,因此1出现了2135次,21351,21352,21353,21354其中21351包含了一个1,故个位出现1的次数为:2135*10(1-1) + 1 = 2136次;

公式:( 2135+1)* 10^(1-1) = 2136;

十位:从1到21300中包含了213个100,因此1出现了213 * 10^(2-1) = 2130次,剩下的数字是21301到21354,它们的十位数字是5 > 1;因此它会包含10个1;故总数为2130 + 10 = 2140次;

公式:(213 + 1)* 10^(2-1) = 2140次;

百位:从1到21000中包含了21个1000,因此1出现了21 * 10^(3-1) = 2100次,剩下的数字是21001到21354,它们的百位数字是3 > 1;因此它会包含100个1;故总数为2100 + 100 = 2200次;

公式:(21 + 1)* 10^(3-1) = 2200次;

千位:从1到20000中包含了2个10000,因此1出现了2 * 10^(4-1) = 2000次,剩下的数字是20001到21354,它们的千位数字是1 = 1;情况稍微复杂些,354 + 1 = 355;故1的总数为2000 + 355 = 2355次;

公式:2 * 10^(4-1) + 354 + 1 = 2355次;

万位:万位是2 > 1,没有更高位;因此1出现的次数是1 * 10^(5-1) = 10000次;

公式:(0 + 1)*10^(5-1) = 10000次;

故总共为:2136+2140+2200+2355+10000=18831次;

故总结:

1、取第 i 位左边的数字(高位),乘以 10 ^(i−1) ,得到基础值 a 。
2、取第 i 位数字,计算修正值: 
1、如果大于 X,则结果为 a+ 10 ^(i−1) 。
2、如果小于 X,则结果为 a 。
3、如果等 X,则取第 i 位右边(低位)数字,设为 b ,最后结果为 a+b+1 。


代码一

public class Main1 {
 
	public int numberOf1Between1AndN(int n, int x){
		if(n < 0 || x < 1 || x > 9){
			return 0;
		}
		int curr, low, temp, high = n, i = 1, total = 0;
		while(high!=0){
			high = n / (int)Math.pow(10, i); //获取第i位的高位
			temp = n % (int)Math.pow(10, i); //
			curr = temp / (int)Math.pow(10, i-1); //获取第i位
			low = temp%(int)Math.pow(10, i-1); //获取第i位的低位
			if(curr == x){ //等于x
				total += high*(int)Math.pow(10, i-1)+ low + 1;
			}else if(curr < x){ //小于x
				total += high*(int) Math.pow(10, i-1);
			}else{ //大于x
				total += (high + 1) * (int)Math.pow(10, i-1);
			}
			i++;
		}
		return total;
	}
	
	public static void main(String[] args) {
		Main1 m1 = new Main1();
		int nums = m1.numberOf1Between1AndN(21354, 1);
		System.out.println(nums);
	}
}

思考2

 解法一 找规律

  • 第一步,最高位带来的1的个数。
  • 第二步,非最高位带来的1的个数
  • 第三步,第一段数字带来的1的个数

以2123为例。

将2123转成字符串s=”2123″。方便处理。

为了便于统计1的个数,将1到2123分成几段。

第一段:1~123

第二段:1000~1999

第三段:2000~2123 x124~x999。其中x124~x999就是原先124~999,将其移动2123之后的。

第一步,最高位带来的1的个数。


这对应上面的第二段数字。

s[0]=2 > 1。此时一定含有最高位是1的数。

最高位是1的数有:1000~1999,共1000个。

这段数据形如1xxx。

数字总个数与最高位之后的数位个数有关。共3个数位,每个数位可放0-9。

总个数 = 10^( 最高位之后的数位个数 ) = 10 ^ 3=1000

但是,当最高位刚好是1时,步能这么算。例如1123.

此时,总个数 = 去掉最高位剩余的数字+1

对于1123,总个数 = 123+1=124

第二步,非最高位带来的1的个数


这对应上面的第三段数字。 2000~2123 x124~x999

不考虑最高位,这段数字形如:Y000~Y999。

非最高位共有三个数位。每个数位都可放1。会得到多少1了?

Y100~Y199,共10^2=100个。

Y010~Y919,共10^2=100个。

Y001~Y991,共10^2=100个。

总个数 = 非最高数位个数 * 10 ^ ( 非最高数位个数 – 1)

第三步,第一段数字带来的1的个数


1~123总共有多少个1?

这个跟1~2123总共有多少个1,没有任何区别。因此,可以递归解决。

综上

count(s,i){
    if(i>=s.length) 返回0;
    ans=0;
    //第一步
    if(s[i] == 1){
        sub=s[i+1:];
        if(sub不空) ans += sub转数字;
        ans += 1;
    }else if(s[i] > 1){
        非最高位数位个数 = s.length-i-1;
        ans += 10 ^ 非最高位数位个数;
    }
    //第二步
    非最高位数位个数 = s.length-i-1;
    ans += 非最高位数位个数 * 10 ^ (非最高位数位个数-1);
    //第三步
    ans += count(s,i+1);
    返回ans;
}

 

 代码2

 

public int numberOf1Between1AndN(int n){
        if(n<=0) {
            return 0;
        }
        String strNumber = String.valueOf(n);
        //将数字转换成字符串
        int length = strNumber.length();
        int firstDigit = strNumber.charAt(0) - '0';
        //将字符串转换成数字,Returns the char value at the specified index.
        //只有个位
        if(length == 1 && firstDigit == 0) {
            return 0;
        }
        if(length ==1 && firstDigit > 0) {
            return 1;
        }
        //除首位外,剩下的数字
        String remainedString = strNumber.substring(1);
        //从1开始到最后的位置,返回一个子字符串;substring(int beginIndex);
        // Returns a new string that is a substring of this string.
        int remainedNumber = Integer.parseInt(remainedString);
        //字符串转换成十进制数字,parseInt(String s),
        // Parses解析 the string argument as a signed decimal integer.

        //1出现在首位的次数
        int countOfFirstDigit;
        if(firstDigit == 1){
            //如果首位数字等于1,比如从10000~12345,则最高位出现1的次数为2345+1=2346次,
            countOfFirstDigit = remainedNumber +1;
            //(2)是把除高位外的字符串转化为整数。10000~12345中最高位出现1个次
            // 数为除去最高数字滞后于剩下的数字再加1.
        } else{
            //(1)1345~21345中,万位上出现1的数字在10000~19999中,有10^4个。
            // 如果n的长度为length,则共有10^(length-1)次。
            countOfFirstDigit = (int)Math.pow(10,length-1);
        }

        //(length-1):任选一位为1;10^(length0-2):其余位从0-9中选;
        //firstDigit:首位可选的数字
        //除了第一位的数之外,其他位上有1的次数:再把1346~21345分成2段,1346~11346,11236~21346,
        //每一段中除去其中的一个数为1之外,其他的每位均可以取0~9,所以有2*10^3次。即共有first*10^(length-2)次

        int countOfOtherDigit = firstDigit *(length -1)*(int)Math.pow(10, length-2);

        // 递归求在剩下数字中1出现的次数
        int remainedCount = numberOf1Between1AndN(remainedNumber);
        int result = countOfFirstDigit + countOfOtherDigit + remainedCount;
        return result;
    }