递归+string

整数中1出现的次数(从1到n整数中1出现的次数)

http://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        if(n<=0) return 0;
        string str=to_string(n);

        return NumberOf1(str,0);
    }
    int NumberOf1(string& str,int startIndex){
        if(str.empty() ||str[startIndex]<'0'||str[startIndex]>'9'||str[startIndex]=='\0') return 0;

        unsigned int length=str.size()-startIndex;

        int first=str[startIndex]-'0';
        if(length==1 && first==0)
            return 0;
        if(length==1 && first>0)
            return 1;

        int numFirstDigit=0;
        if(first==1){
            string subStr=str.substr(startIndex+1);
            numFirstDigit=atoi(subStr.c_str())+1;
        }
        else if(first>1)
            numFirstDigit=PowerOf10(length-1);

        int numOtherDifit=first*(length-1)*PowerOf10(length-2);

        int numRecursive=NumberOf1(str, startIndex+1);

        return numFirstDigit+numOtherDifit+numRecursive;
    }
    int PowerOf10(unsigned int n){
        int result=1;
        for(unsigned int i=0; i<n; i++)
            result = 10*result;

        return result;
    }

};
全部评论

相关推荐

求offer的大角牛:不吃香菜
点赞 评论 收藏
分享
06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务