leetcode-剑指43-OK

// language c
// 剑指43
// https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/


int countDigitOne(int n){
    if(n==0)
        return 0;
    if(n<10)
        return 1;
	int GetWeishu(int n){
		int count = 0;
		while(n>0){
			count++;
			n /=10;
		}
		return count;
	}

	int shiDEnCIFANG(int n){
		int ans = 1;
		for(int i = 0; i<n; i++)
			ans *=10;
		return ans;
	}
	int WEISHU = GetWeishu(n);
	int ans[WEISHU];	// an[i]代表i位数中所有1的个数
	ans[1] = 1;
	for(int i = 2;i<WEISHU; i++){
		ans[i] = ans[i-1]*10+ shiDEnCIFANG(i-1);
	}


	int GetFirstNum(int jiwei){	// 本函数去头，然后返回第一个数
		int beichu = shiDEnCIFANG(jiwei-1);
		int ans = n/beichu;
		n = n%beichu;
		return ans;
	}

	ans[0] = 0;
	for(int k = WEISHU; k >0; k--){
		int tou = GetFirstNum(k);
        if(k!=1)
		    ans[0] += tou*ans[k-1];
		if(tou ==1){
			ans[0] += n+1;
        }else if(tou==0){
        }else{
			ans[0] +=shiDEnCIFANG(k-1);
	    }
    }
	return ans[0];
}

leetcode-剑指43-OK

原文：https://www.cnblogs.com/gallien/p/14356001.html