LeetCode-233. Number of Digit One

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.

Example:

Input: 13Output: 6 Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

题解：

暴力是O(nlgn)，寻找规律可降为O(lgn)。

例如：

对于百位，我们分析以下三种情况中百位带有1的数字个数：

百位 = 0：4211033：left = 42110, right = 33, digit = 100, 该数中百位为1的个数为4211 * 100;

百位 = 1：4211133：left = 42111, right = 33, digit = 100, 该数中百位为1的个数为4211 * 100 + 33 + 1;

百位 > 1：4211233：left = 42112, right = 33, digit = 100, 该数中百位为1的个数为4211 * 100 + 100;

以此类推每一位的情况。

class Solution {public: int countDigitOne(int n) { int cnt = 0; for (long digit = 1; digit <= n; digit *= 10) { long left = n / digit, right = n % digit; int num = left % 10; if (num == 0) { cnt += (left / 10) * digit; } else if (num == 1) { cnt += (left / 10) * digit + right + 1; } else if (num > 1) { cnt += (left / 10) * digit + digit; } } return cnt; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。