整数中1出现的次数

2018-04-28

编程练习

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

思路：拿到题目以后，不难发现题目要求输入一个n，然后得到0~n之间所有整数中1的个数。难点在于如果n非常大，一个整数里就可能含有多个1，比如n为4位数，则1111中就含有4个1。由此可见，需要将每个整数分割，分割成一位一位的格式，再与1做比较。怎么分割？很容易想到利用字符串来过渡。先将每一个整数转换成字符串格式，然后再将该字符串转换成字符数组，然后再利用一个ArrayList来盛装这些字符数组，之后遍历ArrayList，取出每个字符数组，再遍历每个字符数组，统计其中含有的’1’的个数，最后将统计结果返回即可，可见需要利用两层for循环嵌套解决。

java代码如下：

import java.util.ArrayList;

public class NumberOf1Between1AndN {
    public static int NumberOf1Between1AndN_Solution(int n) {
        //异常情况，返回-1
    	if(n<0) {
    		return -1;
    	}
    	//初始化由输入的数产生的int数组
    	int [] arr=new int [n+1];
    	for(int i=0;i<n+1;i++) {
    		arr[i]=i;
    	}
    	//通过将每个数组里的元素转换成字符串再转化成字符数组，方便后续比较
    	ArrayList<char []> list=new ArrayList<char []>();
    	for(int c:arr) {
    		String str=String.valueOf(c);
    		char [] each=str.toCharArray();
    		list.add(each);
    	}
    	int number=0;
    	//两层for循环，第一层取出list中的每一个字符数组，第二层进行每个字符数组中‘1’的个数的统计
    	for(int i=0;i<list.size();i++) {
    		for(int j=0;j<list.get(i).length;j++) {
    			if(list.get(i)[j]=='1') {
    				number++;
    			}
    		}
    	}
    	return number;
    }
    
    public static void main(String[] args) {
		int a=10;
		System.out.println(NumberOf1Between1AndN_Solution(a));
	}
}