牛客網|整数中1の出現回数(1からnの整数中1の出現回数)

1~13の整数のうち1が出現する回数を求め、100~1300の整数のうち1が出現する回数を算出する.そのため、1~13に含まれる1の数字を1、10、11、12、13と特別に数えて6回も現れたが、後の問題には仕方がない.ACMerはあなたたちが彼を助けることを望んで、そして問題をもっと普遍化して、すぐに任意の非負の整数区間の中で1の出現の回数を求めることができます.
参考文献:http://www.cnblogs.com/nailperry/p/4752987.html主に数字から法則を探すことです.
一、1の数
プログラミングの美しさで与えられた法則:
1.i番目のビット(右から左、1から始まる符号)の数字が0である場合、i番目のビットの出現回数は、より高い値によって決定され(高い値がなければ0とする)、より高い値Xの現在のビット数の重み10 i−1に等しい.
2.第i位の数字が1である場合、第i位に1が出現する可能性がある回数は、高位の影響だけでなく、低位の影響(低位がなければ0)も受け、高位の数字Xの現在の桁数の重み10 i-1+(低位の数字+1)に等しい.
3.i位の数字が1より大きい場合、i位に1が現れる可能性のある回数は、(高位がない場合は、高位を0と見なす)よりのみ決定され、(高位数字+1)X現在の桁数の重み10 i-1に等しい.
二、Xの数
ここの  X∈[1,9] ,なぜなら  X=0  以下の法則に合致しない場合は、単独で計算する必要があります.
まず、以下の法則を知る必要があります.
1から10まで,それらのビット数のうち,任意のXが1回出現した.
1から100まで,それらの10桁において,任意のXが10回出現した.
1から1000まで、それらの百桁数の中で、任意のXが100回現れた.
このように1から  10 i ,左から2番目(右から2番目)  i  の中に、任意のXが現れた.  10 i−1  回です.
この法則は検証しやすいので,ここではあまり説明しない.
次に  n=2593,X=5  例として、数学の公式をどのように得るかを説明します.1から2593では、数字5の合計が813回現れ、そのうち259回が個位、260回が10位、294回が百位、0回が千位に現れた.
次に、これらのデータを順次分析し、まずビットです.1〜2590には259個の10が含まれているため,任意のXが259回出現した.最後の残りの3つの数2591,2592,2593は、それらの最大のビット数3そして10名です.1から2500の中から、25個の100を含んで、そのため任意のXはすべて現れました 25×10=250  回です.残りの数字は2501から2593で、最大10桁の数字は9>Xなので、すべての5を含みます.最終合計250+10=260.(このように見ても、9>Xであれば、10ビット上に出現する可能性のあるXの回数は、より高いビットのみによって決定され、より高いビット数(25+1)X 102−1=260に等しい.
次は百位です.1から2000には2つの1000が含まれているので,任意のXが現れた. 2×100=200  回です.残りの数字は2001年から2593までで、それらの最大の100桁の数字は5==Xで、この時状況は少し複雑で、それらの100桁はきっと5を含むが、すべての100を含まない.100桁が5の数字を列挙すると、2500から2593までで、数字の個数は100桁と10桁の数字に関連し、93+1=94です.最終合計200+94=294.(5==Xであれば、100ビットでXが現れる可能性のある回数は、より高位の影響だけでなく、より高位の数字(2)X 103-1+(93+1)=294)にも影響される.
最後は千位です.現在はそれ以上の高位はないので、最大の千桁数字2ここまでに,全数字5の出現回数を算出した.
以上のアルゴリズムをまとめると、右の数字を計算すると  i  ビットに含まれるXの個数の場合:
第を取る  i  ビット左(上位)の数字に乗算  10 i−1 ,基礎値を得る  a .
第を取る  i  ビット数、修正値の計算:
Xより大きい場合、結果は  a+ 10 i−1 .
Xより小さい場合、結果は  a .
Xを待てば、第  i  ビット右(下位)の数字を、  b ,最終結果は  a+b+1 .

対応するコードは非常に簡単で、効率も非常に高く、時間の複雑さは  O( log 10 n) .
三、上コード
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 /**   * @param n   * @param x [1,9]   * @return   */ public int NumberOfXBetween1AndN_Solution( int n, int x) {      if (n< 0 ||x< 1 ||x> 9 )          return 0 ;      int high,low,curr,tmp,i =  1 ;      high = n;      int total =  0 ;      while (high!= 0 ){          high = n/( int )Math.pow( 10 , i); // i          tmp = n%( int )Math.pow( 10 , i);          curr = tmp/( int )Math.pow( 10 , i- 1 ); // i          low = tmp%( int )Math.pow( 10 , i- 1 ); // i          if (curr==x){              total+= high*( int )Math.pow( 10 , i- 1 )+low+ 1 ;          } else if (curr<x){              total+=high*( int )Math.pow( 10 , i- 1 );          } else {              total+=(high+ 1 )*( int )Math.pow( 10 , i- 1 );          }          i++;      }      return total;         }
以上は任意のX数字に対して 
この問題のacコード

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
    	if(n<0)
        	return 0;
    	int high,low,curr,tmp,i = 1;
    	high = n;
    	int total = 0;
    	while(high!=0)
        {
            high = n/(int)Math.pow(10, i);
            tmp = n%(int)Math.pow(10, i);
            curr = tmp/(int)Math.pow(10, i-1);
            low = tmp%(int)Math.pow(10, i-1);
            if(curr==1){
                total+= high*(int)Math.pow(10, i-1)+low+1;
            }else if(curr<1){
                total+=high*(int)Math.pow(10, i-1);
            }else{
                total+=(high+1)*(int)Math.pow(10, i-1);
            }
            i++;
    	}
    	return total;  
    }
}