[LeetCode]233. Number of Digit One

https://leetcode.com/problems/number-of-digit-one/?tab=Description

1 ~ n一共多少个1

找每一位上面有多少个1，三种情况：该位为0、该位为1、该位大于1

标红部分先除后乘，如果当前位置是0或者1，那么加上8之后除10依然舍去，大于一才保留。如果当前位置是1，如192的最高位，那么出现次数为92 + 1次

public class Solution { 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; } }

http://www.lintcode.com/en/problem/digit-counts/

统计0 ~ n中有多少个数字k

与上题类似，注意处理k=0的几个特殊case

class Solution { public int digitCounts(int k, int n) { // write your code here if (k == 0 && n == 0) { return 1; } int res = 0; for (long m = 1; m <= n; m *= 10) { if (k == 0 && m * 10 > n) { break; } res += (n / m + 9 - k) / 10 * m + (n / m % 10 == k ? n % m + 1 : 0); } return res; } };