剑指offer-70-43 1-n整数中1出现的次数

https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6?tpId=13&tqId=11184&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

不错的题

分几种来考虑

1、最高位首位为1的情况

2、最高位可以是1也可以不是1， 剩下几位中选一个位是1， 其他位可以是1也可以不是1，这样就能覆盖位数为当前位数的所有情况了。

3、递归，求去掉最高位剩下的1的个数。

class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
if (n <= 0) return 0;
char tmp[50];
sprintf(tmp, "%d",n );
string s = string(tmp);
return dfs( s, 0 );
}
int dfs(string &s, int ptr) {
if (ptr >= (int) s.size())
return 0;
if (ptr +1 == s.size() ) {
if (s[ptr] == '0' ) return 0;
else return 1;
}
int first = s[ptr] - '0';
int cnt_this_dig = 0;
if (first == 1) {
//if (ptr )
cnt_this_dig = atoi(s.substr(ptr+1).c_str()) + 1;
} else {
if (first > 1) {
cnt_this_dig = pow(10, s.size() - ptr - 1);
}
}
int num_of_other = first * (s.size() - ptr - 1) * pow(10, s.size() - ptr - 2);
int num_of_cur = dfs(s, ptr+1);
return cnt_this_dig + num_of_other + num_of_cur;
}
};

最后

以上就是幽默白羊为你收集整理的剑指offer-70-43 1-n整数中1出现的次数的全部内容，希望文章能够帮你解决剑指offer-70-43 1-n整数中1出现的次数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。