LeetCode-233.|LeetCode-233. 数字1的个数***
题目描述 [数字1的个数]
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例
输入: 13
输出: 6
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。
解题思路
转自 https://segmentfault.com/a/1190000015805741
例如103这样的数字：
个位数是1的有001，011，021，031，041，051，061，071，081，091，101，共11个
十位数是1的有010，011，012，013，014，015，016，017，018，019，共10个
百位数是1的有100，101，102，103
所以对于每一位来说，这一位数字是1的情况是由这一位本身、这一位的所有高位、这一位的所有低位，共同决定的，总结一下，对于abXcd来说：
【LeetCode-233.|LeetCode-233. 数字1的个数***】X=0时，如果ab=01，那么就有00100~00199这100个数字都是X位是1的数字
X=1时，如果ab=01，那么就有00100~00199这100个数字 + ab100~ab1cd这个cd个数字
X>=2时，如果ab=01，那么就有00100~00199这100个数字 + 01100~01199这100个数字
代码
class Solution {
public:
int countDigitOne(int n) {
int lowerNum = 0;
int upperNum = 0;
int curNum = 0;
int num = 0;
int iFactor = 1;
while(n/iFactor){
lowerNum = n - (n / iFactor) * iFactor;
curNum = (n / iFactor) % 10;
upperNum = n / (iFactor * 10);
switch(curNum){
case 0:
num += iFactor * upperNum;
break;
case 1:
num += iFactor * upperNum + lowerNum+ 1;
break;
default:
num += iFactor * (upperNum + 1);
break;
}
iFactor *= 10;
}
return num;
}
};
推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量