題目描述
輸入一個(gè)整數(shù) n 蛤育，求1～n這n個(gè)整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)宛官。
例如，輸入12瓦糕，1～12這些整數(shù)中包含1 的數(shù)字有1底洗、10、11和12咕娄，1一共出現(xiàn)了5次亥揖。
示例
輸入：n = 13
輸出：6
思路
- 既然是1~n整數(shù)中1出現(xiàn)的次數(shù)，可以拆解為整數(shù)n各個(gè)位置上所以可能出現(xiàn)1的個(gè)數(shù)圣勒。
- 例如一個(gè)整數(shù)n為4位數(shù)费变，那么結(jié)果便是第一位、第二位圣贸、第三位以及第四位上可能出現(xiàn)1的次數(shù)之和挚歧。
- 每位上出現(xiàn)1的個(gè)數(shù)依賴(lài)于三個(gè)位置。
高于該位的數(shù)字
該位的數(shù)字
低于該位的數(shù)字
可以拿401吁峻、411以及412的十位做例子滑负。
// 401
// 010 011 012 013 014 015 016 017 018 019
// 110 111 112 113 114 115 116 117 118 119
// 210 211 212 213 214 215 216 217 218 219
// 310 311 312 313 314 315 316 317 318 319
// 411
// 010 011 012 013 014 015 016 017 018 019
// 110 111 112 113 114 115 116 117 118 119
// 210 211 212 213 214 215 216 217 218 219
// 310 311 312 313 314 315 316 317 318 319
// 410 411
// 421
// 010 011 012 013 014 015 016 017 018 019
// 110 111 112 113 114 115 116 117 118 119
// 210 211 212 213 214 215 216 217 218 219
// 310 311 312 313 314 315 316 317 318 319
// 410 411 412 413 414 415 416 417 418 419
- 從上面的例子中在张，設(shè)置當(dāng)前位為current，高位為high矮慕，低位為low帮匾；
可以總結(jié)出某位上出現(xiàn)1的次數(shù)的相關(guān)公式(i為10，因?yàn)楫?dāng)前位是十位)：
- 如果current=0痴鳄；則count = high * i
- 如果current=1瘟斜；則count = high * i + low + 1
- 如果current>1；則count = (high+1) * i
- 可以根據(jù)得出的公式夏跷，從個(gè)位開(kāi)始累加1出現(xiàn)的次數(shù)哼转，一直到最高位累加完成為止。
Java代碼實(shí)現(xiàn)
class Solution {
public int countDigitOne(int n) {
int i = 1;
int res = 0,high = n,current=0,low=0;
while(high > 0){
high = high/10;
current = (n/i)%10;
low = n - (n/i)*i;
if(current == 0){
res = res + high* i;
}else if(current == 1){
res = res + high * i + low + 1;
}else{
res = res + (high+1)*i;
}
i = i * 10;
}
return res;
}
}
Golang代碼實(shí)現(xiàn)
func countDigitOne(n int) int {
i := 1
high,current,low,res := n,0,0,0
for high > 0 {
high /= 10
current = (n/i)%10
low = n - n/i*i
if current == 0{
res = res + high * i;
}else if current == 1{
res = res + high *i + low + 1
}else{
res = res + (high+1) * i
}
i *= 10
}
return res
}
