[LeetCode] Number of Digit One

客官°小女子只卖身不卖艺 2022-08-04 09:26 140阅读 0赞

题意：计算从 1~n 中所有的数的 1 的个数总和。

题目链接：[Number of Digit One][]

思路：代码来自《编程之美》2.4

1位数：

n >= 1, f(n) = 1,

n = 0, f(n) = 0

2位数：f(n) = 个位数1的个数 + 十位数1出现的个数；

个位数1的个数：个位数值>=1，1的个数为十位数数值加1；个位数为0，1的个数则为十位数数值；

十位数1的个数：十位数值=1，1的个数为个位数数值加1；十位数>1,1的个数为10；

3位数：f(n) = 个位数1的个数 + 十位数1出现的个数 + 百位数1出现的个数；

4位数：

5位数：

。

以此类推

代码如下：

/**
     * 1、找规律；2、注意越界。
     */ 
    public class Solution {
        public int countDigitOne(int n) {
            if(n <= 0) {
                return 0 ;
            }
            long iCount = 0 ;
            long iFactor = 1 ;
            long iLowerNum = 0 ;
            long iCurrNum = 0 ;
            long iHigherNum = 0 ;
        	while(n / iFactor != 0) {
                iLowerNum = n - (n / iFactor) * iFactor ;
                iCurrNum = (n / iFactor) % 10 ;
                iHigherNum = n / (iFactor * 10) ;
                
                System.out.println(iHigherNum + ", " + iCurrNum + ", " + iLowerNum);
                
                switch((int) iCurrNum) {
                    case 0:
                    	iCount += iHigherNum * iFactor ;
                   		break ;
                    case 1:
                    	iCount += iHigherNum * iFactor + iLowerNum + 1 ;
                    	break ;
                    default:
                    	iCount += (iHigherNum + 1) * iFactor ;
                    	break ;
                }
                iFactor *= 10 ;
            }
            return (int) iCount ;
        }
    }

[Number of Digit One]: https://leetcode.com/problems/number-of-digit-one/