[LeetCode]233.Number of Digit One

题目

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

思路

[算法系列之三十二]1的数目

代码

/*---------------------------------------
*   日期：2015-07-19
*   作者：SJF0115
*   题目: 233.Number of Digit One
*   网址：https://leetcode.com/problems/number-of-digit-one/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int countDigitOne(int n) {
        if(n == 0){
            return 0;
        }//if
        int result = 0;
        int lowerNum = 0,curNum = 0,highNum = 0;
        int base = 1;
        int num = n;
        while(num){
            // 低位部分
            lowerNum = n - num * base;
            // 当前部分
            curNum = num % 10;
            // 高位部分
            highNum = num / 10;
            // 如果为0则这一位1出现的次数由更高位决定 (更高位数字*当前位数)
            if(curNum == 0){
                result += highNum * base;
            }//if
            // 如果为1则这一位1出现的次数不仅受更高位影响还受低位影响(更高位数字*当前位数+低位数字+1)
            else if(curNum == 1){
                result += highNum * base + (lowerNum + 1);
            }//else
            // 大于1则仅受更高位影响((更高位数字+1)*当前位数)
            else{
                result += (highNum + 1) * base;
            }//else
            num /= 10;
            base *= 10;
        }//while
        return result;
    }
};

int main(){
    Solution s;
    int n;
    while(cin>>n){
        cout<<s.countDigitOne(n)<<endl;
    }//while
    return 0;
}

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>