从1到N整数中1出现的次数--我的代码

问题： 输入一个整数n，求从1 到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1，10，11和12，1一共出现了5次。

这是《剑指offer 名企面试官精讲典型编程题》一书中的第32题。书中Herry给出了递归算法。我自己写的是循环算法。虽然有着不同写法，但大体上思路是一致的。我的算法并不比Herry的强。写下来只是提供另外的一个解法。

分析：要得到一个整数中出现的1的次数，其实就是算出1在个位，十位，百位等等中出现的次数总和。在个位上，1在0至9中出现的频率只是1次，其它023456789都和1无关。但是整个个位的循环次数是除去个位的整数值加1（或不加）。如，23， 个位的1出现的次数是3 （23去掉3再加1），即01，11，21；123个位的1出现次数是13（123去掉3加1），即01，11，21，31，41，51，61，71，81，91，101，111，121；以此类推。

再来看十位， 1在0至9中出现的频率也只是1次，但是和个位不同的是，十位中的1却要因为个位的原因至多循环10次（或不到10次），如10，11，12，13，14，15，16，17，18，19，所以整个十位的循环次数是除去个位和十位的整数值乘以10（或不乘）。

百位是也是如此，百位上的1要为十位和个位循环至多10*10次。

由此，我们就可以得出了算法。

时间复杂性是O(n)

       private int GetOneOccurence( int piNum ) {
            String lsNum = piNum.ToString();
            int liResult = 0;

            // calculate result from first digit to last one 
            for ( int i = lsNum.Length - 1; i >= 0; i-- ) {
                liResult += GetOneOccurence( lsNum, i );
            }

            return liResult;
        }

        private int GetOneOccurence( String psNum, int piLoopPosition ) {
            String lsSuffix;
            int liResult = 0;

            // current: digit in current position that is specified by piPos
            // Suffix: get following digits from current digit 
            // Prefix: get digits before current digit
            //      e.g. 456791, current number is 6, the lsSuffix is 791, prefix is 45.
            lsSuffix = psNum.Substring( piLoopPosition + 1 );

            int liCurNum = int.Parse( psNum.Substring( piLoopPosition, 1 ) ) ;
            int liPrefix = ( piLoopPosition == 0 ? 0 : int.Parse( psNum.Substring( 0, piLoopPosition )  ) );
            int liSuffix = ( String.IsNullOrEmpty( lsSuffix ) ? 0 : int.Parse( lsSuffix ) );

            // Get power suffix of current number 
            // e.g: 1,234 , power of suffix is 100 when current number is 2
            int liSufPow = (int)Math.Pow( 10, lsSuffix.Length );

            // if current number is great than 1, then 1 occurence in this position is ( prefix + 1 ) * power of suffix
            //   e.g: 12345, the current number is 3 now. then 1 occurence in third position is ( 12 + 1 ) * 100
            //          that is: 01100 to 12100, plus 100 to 199
            // if current number is equal to 1, then occurence is prefix * power of suffice + suffix + 1
            //   e.g: 21345, current number is 1. the value is 2 * 1000 + 345 + 1
            //          that is: 1000 to 1345, plus 11000 to 21000
            // the last situation is that current number is equal to 0. So, occurence is simple to prefix * power of suffix
            //   e.g: 12045. the result should be 12 * 100
            //          that is 00100 - 00199, 01100 - 01199, 02100 - 02199,... ,11100 - 11199.
            if ( liCurNum > 1 ) {
                liResult = ( liPrefix + 1 ) * liSufPow;
            } else if ( liCurNum == 1 ) {
                liResult = liPrefix * liSufPow + ( liSuffix + 1 ); 
            } else {
                liResult = liPrefix * liSufPow;
            }

            return liResult;
        }

从1到N整数中1出现的次数--我的代码

原文：http://blog.csdn.net/liberwang/article/details/19026361