LeetCode第233题数字1的个数

原题如下：

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例:

输入: 13
输出: 6
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

思路如下：

0.暴力破解法，依次遍历每个数中的1的个数，累加起来（算法题如果是挨个写到这题的话，这个想法在脑中也就是一闪而过）
1.递归法：
为了方便操作做了一些前导操作：把一个int拆分成vector，同时也写了一个vector转回int的函数
对于vector<int>nums 的i号元素（即原数的第i+1位）而言分为3种情况：
0）nums【i】==0；直接digui下一位；
1）nums【i】==1；比如说nums【i----nums.size（）-1】所构成的数是185那么他产生的1的总共个数有以下几个部分
（185是3位数）所以第一部分（数字低于3位，，1位or2位）他至少包括2个数所构成的最大1的个数（其实就0-99之间1的个数和ps：这个是完全2位数构成的）第二部分（数字必须是3位数（100-185））我们会发现首位是1，至少包括185-100+1个（但是这只是第一个位置上的1的个数，后面还有2位呢），所以再加上85所能得到1的个数（digui（85））

即最终结果为：：m【2】+（185-100+1）+digui（85）

2）nums【i】>=2;
这里拿485举例：==第一部分（数字低于3位，，1位or2位）==这个和上面的情况一样；第二部分（数字必须是3位数）
以1打头；这时候情况跟上面不太一样，因为我们可以达到199！！！，所以以1打头的为（199-100+1）+digui（99），ps：digui（99）其实就是完全2位数构成的1个数记为m【2】，即为：（199-100+1）+m【2】；
以2，3打头是可以达到，299，399的（所以和4不一样）
他们每个都是完全2位构成1的个数即2个*m【2】；
以4打头的（400-485）：这时候我们不能把他记为m【2】（digui（99）），应该单算一下digui（85）；

即最终答案为：（199-100+1）+m【2】+2个*m【2】+digui（85）；不把m【2】合并是为了方便理解

代码如下：

vector<int> makeDigitVector(int &n){
		vector<int>m;
		if (n <= 9)return{ n };
		while (n){
			int t = n % 10;
			vector<int>::iterator p = m.begin();
			m.insert(p,t);
			n /= 10;
		}
		return m;
	}
	int canGetMAX(int size ,vector<int>&m){
		int total=0;
		if (size == 1){ m[1] = 1; return 1; }
		int x = canGetMAX(size - 1,m);
		total = pow(10, size - 1)+10*x;
		m[size] = total;
		return total;
	}
	int vectorToInt(vector<int>&nums, int & begin){
		int total=0;
		for (int i = begin; i <= nums.size() - 1; i++)
			total += nums[i] * pow(10, nums.size() - 1 - i);
		return total;
	}
	int digui(vector<int>&nums,int begin,vector<int>&m){
		int total = 0;
		if (begin == nums.size() - 1) {
			if (nums[begin] == 0)return 0;
			else return 1;
		}
		if (nums[begin] == 0)return digui(nums, begin + 1, m);
		else if (nums[begin] == 1){
			int now_size = nums.size() - begin;
			int x = vectorToInt(nums, begin);
			int y = pow(10, now_size - 1);
			total = x - y + 1 + digui(nums, begin + 1, m) + m[now_size - 1];
			return total;
		}
		else{
			int now_size = nums.size() - begin;
			int z = pow(10, now_size - 1)+m[now_size-1];
			int x = (nums[begin] - 2)*m[now_size-1];
			total = z + x + digui(nums, begin + 1, m) + m[now_size - 1];
			return total;
		}
	}
	int countDigitOne(int n) {
		if (n <= 9){
			if (n <= 0)return 0;
			else return 1;
		}
		vector<int>nums=makeDigitVector(n);
		vector<int>m(nums.size()+1, 0);
		canGetMAX(nums.size() , m);
		return digui(nums, 0, m);
	}

最后

以上就是雪白缘分为你收集整理的LeetCode第233题数字1的个数的全部内容，希望文章能够帮你解决LeetCode第233题数字1的个数所遇到的程序开发问题。

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