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

                             从1到n整数中1出现的次数（Java）

题目

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

示例:

输入: 13
输出: 6 
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

 思考一

注：（这里的 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;
    }