首页 > 其他分享 >600. 不含连续1的非负整数

600. 不含连续1的非负整数

时间:2024-08-10 09:53:33浏览次数:11  
标签:pre 600 非负 int res 整数 dp

600. 不含连续1的非负整数


题目链接:600. 不含连续1的非负整数

代码如下:

//参考链接:https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/solutions/1750941/by-endlesscheng-1egu
class Solution
{
public:
	int findIntegers(int n)
	{
		vector<int> dp(31);
		dp[0] = dp[1] = 1;
		for (int i = 2; i < 31; i++)
		{
			dp[i] = dp[i - 1] + dp[i - 2];
		}

		int pre = 0, res = 0;
		for (int i = 29; i >= 0; --i)
		{
			int val = 1 << i;
			if ((n & val) != 0)
			{
				res += dp[i + 1];
				if (pre == 1) { break; }
				pre = 1;
			}
			else { pre = 0; }

			if (i == 0) { res++; }
		}
		return res;
	}
};

标签:pre,600,非负,int,res,整数,dp
From: https://blog.csdn.net/weixin_45256307/article/details/141086528

相关文章