本文主要是介绍leetcode No233. Number of Digit One，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Question:
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.
Algorithm:
举个例子：532
我们称个位从1到9是一轮记为round1
个位出现1的次数，假设我们从1开始，一轮后出现一次1，那么从1到530的过程中，个位一共有53轮，530到532的过程中也出现了一次1，那么我们可以得出个位的规律，如果个位大于等于1的话，那么出现round1+1次，否则，round次。
十位从1到9是一轮记为round2
十位出现1的次数，从1到500的过程中，round2=5，那么有5*10次，又十位为3大于1，那么从501到532的过程中，又出现了1*10次（如果是502，那501到502，就没有出现1）
百位，1到532，出现了100次。
总结一下就是：
设当前位为第i位，比当前位高一位为i+1位，比当前位低的位数的大小为lowernum（比如532当前位数为5，则lowernum=32）
当前位为0：nums[i+1]*pow(10,i-1)
当前位为1：nums[i+1]*pow(10,i-1)+lowernum
其他：nums[i+1]*pow(10,i-1)+pow(10,i-1)
Accepted Code:
class Solution {
public:int countDigitOne(int n) {if(n<=0)return 0;int higherDigit=0; //比当前位高一位的位，当前位轮了多少次0到9int curDigit=0; //当前位int lowerNums=0; //低位的大小long long total=0;long long factor=1;while(n/factor){higherDigit=n/(factor*10);curDigit=(n/factor)-(n/(factor*10))*10;lowerNums=n-(n/factor)*factor;switch(curDigit){case 0:total+=higherDigit*factor; break;case 1:total+=higherDigit*factor+lowerNums+1;break;default:total+=(higherDigit+1)*factor;}factor*=10;}return total;}
};这篇关于leetcode No233. Number of Digit One的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
