Number of Digit One

原题: https://leetcode.com/problems/number-of-digit-one/description/

题意: 给定一个整数n,计算所有小于等于n的非负整数中数字1出现的次数。

例子: 

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

标签: digit、occurred、number、numbers、非负、面试
猜你感兴趣的圈子:
LeetCode交流圈
  • Bingo
    2017-08-18 16:53:30 1楼#1层
    Python解法一:
    class Solution:
        # @param {integer} n
        # @return {integer}
        def countDigitOne(self, n):
            if n < 0:
                return 0
            ones, x = [0], 0
            while 10 ** x <= 0x7FFFFFFF:
                ones.append(ones[x] * 10 + 10 ** x)
                x += 1
            cnt, size = 0, len(str(n))
            for digit in str(n):
                digit = int(digit)
                size -= 1
                n -= digit * 10 ** size
                if digit > 1:
                    cnt += digit * ones[size] + 10 ** size
                elif digit == 1:
                    cnt += n + ones[size] + 1
            return cnt
  • Bingo
    2017-08-18 16:53:44 2楼#1层
    Python解法二:
    def countDigitOne(self, n):
        ones, m = 0, 1
        while m <= n:
            ones += (n/m + 8) / 10 * m + (n/m % 10 == 1) * (n%m + 1)
            m *= 10
        return ones
  • Bingo
    2017-08-18 16:54:08 3楼#1层
    C++解法一:
    class Solution {
    public:
        int countDigitOne(int n) {
            int res = 0, a = 1, b = 1;
            while (n > 0) {
                res += (n + 8) / 10 * a + (n % 10 == 1) * b;
                b += n % 10 * a;
                a *= 10;
                n /= 10;
            }
            return res;
        }
    };
  • Bingo
    2017-08-18 16:54:22 4楼#1层
    C++解法二:
    class Solution {
    public:
        int countDigitOne(int n) {
            int res = 0;
            for (long k = 1; k <= n; k *= 10) {
                long r = n / k, m = n % k;
                res += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
            }
            return res;
        }
    };
  • Bingo
    2017-08-18 16:55:11 5楼#1层
    Java:
    public int countDigitOne(int n) {
        int ones = 0;
        for (long m = 1; m <= n; m *= 10)
            ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
        return ones;
    }
  • 回复
隐藏