題目描述 帕弊客網(wǎng)
- 輸入一個(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 共計(jì)出現(xiàn)了 5 次
題目解讀
- 劍指Offer 221
- 思路一欺嗤，常規(guī)方法参萄，不考慮時(shí)間效率
- 思路二，看偶灞客討論區(qū)的方法讹挎，很優(yōu)秀，點(diǎn)我
代碼
- 思路一，常規(guī)方法，不考慮時(shí)間效率
#include<iostream>
using namespace std;
class Solution {
public:
int numberof1(int x){
int len = 0;
while(x != 0){
if(x%10 == 1){
len ++;
}
x /= 10;
}
return len;
}
int NumberOf1Between1AndN_Solution(int n)
{
int numof1 = 0;
for(int i=1; i <= n; i++){
numof1 += numberof1(i);
}
return numof1;
}
};
int main(){
Solution ss;
cout<<ss.NumberOf1Between1AndN_Solution(12)<<endl;
}
- 思路二冲簿，看牛客討論區(qū)的方法怜奖，很優(yōu)秀，點(diǎn)我
主要思路：設(shè)定整數(shù)點(diǎn)（如1翅阵、10歪玲、100迁央、1000、等10的倍數(shù)）作為位置點(diǎn) i（對應(yīng)n的個(gè)位滥崩、十位岖圈、百位、千位等）夭委，分別對每個(gè)數(shù)位上有多少包含1的點(diǎn)進(jìn)行分析幅狮。根據(jù)設(shè)定的整數(shù)位置，對n進(jìn)行分割株灸，分為兩部分崇摄，高位 a = n/i，低位 b = n%i. 下面是三個(gè)實(shí)例慌烧。
1逐抑、當(dāng) i 表示百位，且百位對應(yīng)的數(shù)字>=2時(shí)屹蚊，如 n=31456厕氨，i=100，則 a = 314, b = 56汹粤，此時(shí)百位為1的次數(shù)有 a/10 + 1= 314/10 + 1 = 32（最高兩位0~31）命斧，每一次都包含100個(gè)連續(xù)的點(diǎn)，即共有( a / 10 + 1 ) * 100 個(gè)點(diǎn)的百位為 1
2嘱兼、當(dāng) i 表示百位国葬，且百位對應(yīng)的數(shù)字為 1 時(shí)，如 n=31156芹壕，i=100汇四，則 a=311, b=56，此時(shí)百位對應(yīng)的就是1踢涌，則共有 a / 10 (最高兩位0-30)次包含 100 個(gè)連續(xù)點(diǎn)通孽，當(dāng)最高兩位為31（即a=311），本次只對應(yīng)局部點(diǎn)00~56睁壁，共b+1次背苦，所有點(diǎn)加起來共 ( a / 10 ) * 100 + (b + 1)，這些點(diǎn)百位對應(yīng)為1
3潘明、當(dāng)i表示百位糠惫，且百位對應(yīng)的數(shù)為0, 如n = 31056, i = 100，則a=310, b=56钉疫，此時(shí)百位為1的次數(shù)有a/10=31（最高兩位0~30）， 所有點(diǎn)加起來共 ( a / 10 ) * 100
綜合上述三種情況巢价，我們就可以知道 百位為 1 的時(shí)候共有多少個(gè)數(shù)字了牲阁，固阁，其他位的情況類似可得
#include<iostream>
using namespace std;
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
int ones = 0;
for(int i=1; i <= n; i*=10){
int a= n / i;
int b= n % i;
if(a% 10 == 0){
ones += (a / 10) * i;
}
else if(a% 10 == 1){
ones += (a / 10) * i + ( b + 1);
}
else{
ones += ((a / 10) + 1) * i;
}
}
return ones;
}
};
int main(){
Solution ss;
cout<<ss.NumberOf1Between1AndN_Solution(12)<<endl;
}
總結(jié)展望
- 講道理，第二種方法應(yīng)該比第一種要快的城菊，但是疟溉迹客運(yùn)行時(shí)間竟然一樣，真是服氣凌唬，應(yīng)該是挪⑵耄客測試數(shù)據(jù)量小吧.
