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

方法一：暴力求解

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count=0;
        for(int i=1;i<=n;i++){//一个一个试
            int j=i;
            while (j!=0){
                if(j%10==1)count++;
                j=j/10;
            }
        }
        return count;
    }
}
//时间O(NlogN) 空间O(1)
//暴力求解进行了大量的重复计算

方法二：找规律

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count =0;
        for(int i=1; i<=n; i*=10){//i每次*10，而不是+1 //复杂度O(logN) //i=1、10、100...分别对应个位、十位、百位的"1" //包含n（因为每一轮都代表一个数字位，例如10包含个位和十位）
            int a = n/(i*10);//当前位之前的数
            int b = n%i;//当前位之后的数
            int c = (n/i)%10;//当前位
            //整批
            count += a*i;
            //末尾零散
            if(c==1) count += (b+1);
            else if(c>=2) count += i;
        }
        return count;
    }
}//时间O(logN) 空间O(1)
//ps:网上方法，将count+=语句压缩到一行，会严重影响可读性