LeetCode题解——Number of Digit One

本文主要是介绍LeetCode题解——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.

解题思路：想法一：从一到n依次计算每个数所含1的个数，然后求和。时间复杂度O(nlogn).  TLE

想法二： 任意给定一个数256我们可以很快判断出1-256含1的个数。首先将1-256分为两部分，1-199；200-256；接着先求解1-199所含一的个数：

百位为1的数字有100-199共100个数字。十位为1的数字有百位可以为0可以为1，个位从0-9任选1个，所有有2*10=20个。个位为1的数字有：十位从0-9任选，百位从0,1任选，共2*10=20个。所以1-199所含1的个数为140个。

接着求200-256所含1的个数，就等于1-56所含1的 个数。可以递归调用countDigitOne求解。

class Solution {
public:int countDigitOne(int n) {if(n<1) return 0;if(n<10) return 1;int m = n;int bit = 0;while(m>9){m/=10;bit++;}int high = m*pow(10,bit),low = n - high;return counthighBitone(m,bit)+countDigitOne(low)+(m==1?low+1:0);}int counthighBitone(int m, int bit){int count = (m==1?0:pow(10,bit));//计算最高位为1的数的个数count+= bit*m*pow(10,bit-1);return count;}
};

这篇关于LeetCode题解——Number of Digit One的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---