整数中1出现的次数

• 思路1
  将n按照位数分段进行计算。例如，对41133的求解划分成：
  40000,5位数
  1000，4位数
  100，3位数
  30，2位数
  3，1位数
  五个段来求解，每个段需要求两个部分Tk_1、O(curValue)：

1.Tk_1,当前位数k的下一级位数k_1中1的个数Tk_1。例如40000，当前为k=5位数，求k_1=4位数中1的个数。当前位值为5，则表示有5个4位数，求这5个4位数的1的总和，即curValue x Tk_1.
2.O(curVlue)，当前位数值curValue本身出现1的次数。第1步求出了5个4位数的1的总和，但是没有考虑最高位第5位中1出现的个数，需求一下。如果当前位值>1，则当前位的1出现了10^(k-1)次，如40000,10000-19999一共是10000=10^4个数，最高位1也就出现了10^4次；如果当前位值==1，则当前位出现1的次数为“零头”的值+1，例如41133中的1xxx，当前位为1，则第4位出现1的次数为xxx+1=133+1，即41133%1000+1；如果当前位值==0，则当前位出现1的次数为0。
每段1出现的总次数为：curValue*Tk_1+O(curValue).
Tk = 10 x Tk_1+10^(k-1)
O(curValue) = 10^(k-1) if curValue >1; n%(10^(k-1))+1 if curValue==1;0 if curValue == 0.

代码：

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        if(n<=0) return 0;
        int iN = n;
        int sumT = 0;
        int res = 0;
        int k = 1;
        int preValue = 0;
        int curTk = 0;
        while(iN>0){
            int curValue = iN%10;
            //1.O(curValue)计算iCountOfCurValue
            int iCountOfCurValue = 0;
            if(curValue == 0) {iCountOfCurValue = 0;}
            else if(curValue == 1) {
                iCountOfCurValue = 1+n%((int)Math.pow(10,k-1));
            }
            else{  
                iCountOfCurValue =(int)Math.pow(10,k-1);
            }
            //2.Tk_1
            curTk =CountOfNWei(k-1,curTk);//k位数的1的个数和1-999
            //sumT += curTk;
            int iCountOfCurRight = curValue*curTk;
            res+=(iCountOfCurRight+iCountOfCurValue);
            iN/=10;
            ++k;//k位数
            preValue = curValue;
        }
        return res;
    }

    int CountOfNWei(int NWei,int sumTk){
        if(NWei ==0) return NWei;
        int k = NWei;
        //sumTk =sumTk*9+(int)Math.pow(10,k-1);
        sumTk =sumTk*10+(int)Math.pow(10,k-1);
        return sumTk;
    }
}

防止吞格式
防止吞格式
防止吞格式
防止吞格式
防止吞格式
防止吞格式
防止吞格式
防止吞格式
防止吞格式
防止吞格式
防止吞格式
防止吞格式