LeetCode 233. 数字1的个数
描述
《编程之美》上这样说:
设N = abcde ,其中abcde分别为十进制中各位上的数字。
1,如果要计算百位上1出现的次数,它要受到3方面的影响:百位上的数字,百位以下(低位)的数字,百位以上(高位)的数字。
,2,如果百位上数字为0,百位上可能出现1的次数由更高位决定。比如:12013,
则可以知道百位出现1的情况可能是:100~199,1100~1199,2100~2199,,...,11100~11199,一共1200个。
可以看出是由更高位数字(12)决定,并且等于更高位数字(12)乘以 当前位数(100)。注意:高位数字不包括当前位
3,如果百位上数字为1,百位上可能出现1的次数不仅受更高位影响还受低位影响。比如:12113,
则可以知道百位受高位影响出现的情况是:100~199,1100~1199,2100~2199,,....,11100~11199,一共1200个。
和上面情况一样,并且等于更高位数字(12)乘以 当前位数(100)。
但同时它还受低位影响,百位出现1的情况是:12100~12113,一共14个,等于低位数字(13)+1。 注意:低位数字不包括当前数字
,4,如果百位上数字大于1(2~9),则百位上出现1的情况仅由更高位决定,比如12213,
则百位出现1的情况是:100~199,1100~1199,2100~2199,...,11100~11199,12100~12199,一共有1300个,
并且等于更高位数字+1(12+1)乘以当前位数(100)
解法一
public class CountDigitOne {
public static void main(String[] args) {
int a = 27;
int i = countDigitOne(a);
System.out.println(i);
}
public static int countDigitOne(int n) {
if (n < 1) {
return 0;
}
int res = 0;
long i = 1;
while (n >= i) {
res += (n / i + 8) / 10 * i + ((n / i) % 10 == 1 ? (n % i + 1) : 0);
i *= 10;
}
return res;
}
}
解法2
public class CountDigitOne2 {
public static void main(String[] args) {
int a = 27;
int i = countDigitOne(a);
System.out.println(i);
}
public static int countDigitOne(int n) {
if (n <= 0) {
return 0;
}
String stringN = n + "";
int ans = 0;
while (!stringN.isEmpty()) {
int tempLen = stringN.length();
String firstChar = stringN.charAt(0) + "";
if (Integer.parseInt(firstChar) >= 2) {
ans += 1 * Math.pow(10, tempLen - 1);
} else if (firstChar.equals("1")) {
if ("".equals(stringN.substring(1, tempLen))) {
ans += 1;
} else if (!"".equals(stringN.substring(1, tempLen))) {
ans += Integer.parseInt(stringN.substring(1, tempLen)) + 1;
}
}
if (tempLen > 1) {
ans += Integer.parseInt(firstChar) * (tempLen - 1) * Math.pow(10, tempLen - 2);
}
stringN = stringN.substring(1);
}
return ans;
}
}
最新评论