【数位dp】【C++算法】600. 不含连续1的非负整数

作者推荐

【矩阵快速幂】封装类及测试用例及样例

涉及知识点

数位dp

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

给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。
示例 1:
输入: n = 5
输出: 5
解释:
下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数 3 违反规则（有两个连续的 1 ），其他 5 个满足规则。
示例 2:
输入: n = 1
输出: 2
示例 3:
输入: n = 2
输出: 3
提示:
1 <= n <= 109

数位dp

直接使用封装好的类。
结果:int 最小值:‘0’ 最大值：‘1’
当前值为’1’时,前值必须为‘0’。
当前值为’0’时，前值‘0’ ‘1’ 皆可。

代码

封装类

template<class ELE, class ResultType, ELE minEle, ELE maxEle>
class CLowUperr
{
public:
	CLowUperr(int iResutlCount):m_iResutlCount(iResutlCount)
	{
	}
	void Init(const ELE* pLower, const ELE* pHigh, int iNum)
	{
		m_vPre.assign(4, vector<ResultType>(m_iResutlCount));
		if (iNum <= 0)
		{
			return;
		}
		InitPre(pLower, pHigh);
		iNum--;
		while (iNum--)
		{
			pLower++;
			pHigh++;
			vector<vector<ResultType>> dp(4, vector<ResultType>(m_iResutlCount));
			OnInitDP(dp);
			//处理非边界
			for (auto tmp = minEle; tmp <= maxEle; tmp++)
			{
				OnEnumOtherBit(dp[0], m_vPre[0], tmp);
			}
			//处理下边界
			OnEnumOtherBit(dp[1], m_vPre[1], *pLower);
			for (auto tmp = *pLower + 1; tmp <= maxEle; tmp++)
			{
				OnEnumOtherBit(dp[0], m_vPre[1], tmp );
			}
			//处理上边界
			OnEnumOtherBit(dp[2], m_vPre[2], *pHigh );
			for (auto tmp = minEle; tmp < *pHigh; tmp++)
			{
				OnEnumOtherBit(dp[0], m_vPre[2], tmp );
			}
			//处理上下边界
			if (*pLower == *pHigh)
			{
				OnEnumOtherBit(dp[3], m_vPre[3], *pLower);
			}
			else
			{
				OnEnumOtherBit(dp[1], m_vPre[3], *pLower );
				for (auto tmp = *pLower + 1; tmp < *pHigh; tmp++)
				{
					OnEnumOtherBit(dp[0], m_vPre[3], tmp );
				}
				OnEnumOtherBit(dp[2], m_vPre[3], *pHigh );
			}
			m_vPre.swap(dp);
		}
	}
	/*ResultType Total(int iMinIndex, int iMaxIndex)
	{
		ResultType ret;
		for (int status = 0; status < 4; status++)
		{
			for (int index = iMinIndex; index <= iMaxIndex; index++)
			{
				ret += m_vPre[status][index];
			}
		}
		return ret;
	}*/
protected:
	const int m_iResutlCount;
	void InitPre(const ELE* const pLower, const ELE* const pHigh)
	{
		for (ELE cur = *pLower; cur <= *pHigh; cur++)
		{
			int iStatus = 0;
			if (*pLower == cur)
			{
				iStatus = *pLower == *pHigh ? 3 : 1;
			}
			else if (*pHigh == cur)
			{
				iStatus = 2;
			}
			OnEnumFirstBit(m_vPre[iStatus], cur);
		}
	}

	virtual void OnEnumOtherBit(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE curValue) = 0;

	virtual void OnEnumFirstBit(vector<ResultType>& vPre, const ELE curValue) = 0;
	virtual void OnInitDP(vector<vector<ResultType>>& dp)
	{

	}
	vector<vector<ResultType>> m_vPre;
};

核心代码

class CCharLowerUper : public CLowUperr<char, int, '0', '1'>
{
public:
	using CLowUperr<char, int, '0', '1'>::CLowUperr;
	int Total(int iMinIndex, int iMaxIndex)
	{
		int ret = 0;
		for (int index = iMinIndex; index <= iMaxIndex; index++)
		{
			int cur = 0;
			for (int status = 0; status < 4; status++)
			{
				cur += m_vPre[status][index];
			}
			ret += cur;
		}
		return ret;
	}
protected:

	virtual void OnEnumFirstBit(vector<int>& vPre, const char curValue)
	{
		const int index = curValue - '0';
		vPre[index]++;
	}
	virtual void OnEnumOtherBit(vector<int>& dp, const vector<int>& vPre, char curValue)
	{
		const int index = curValue - '0';
		if (1 == index)
		{
			dp[index] += vPre[0];
		}
		else
		{
			dp[index] += vPre[0] + vPre[1];
		}		
	}

};

class Solution {
public:
	int findIntegers(int n) {
		 string strN ;
		 while (n > 0)
		 {
			 strN += ((n & 1) ? "1" : "0");
			 n /= 2;
		 }
		 std::reverse(strN.begin(), strN.end());
		const int len = strN.length();
		int iRet = 0;
		for (int i = 1; i < len; i++)
		{
			CCharLowerUper lu(2);
			lu.Init(("1" + string(i - 1, '0')).c_str(), string(i, '1').c_str(), i);
			iRet += lu.Total(0, 1);
		}

		CCharLowerUper lu(2);
		lu.Init(("1" + string(len - 1, '0')).c_str(), strN.c_str(), len);
		iRet += lu.Total(0, 1);
		return 1 + iRet;
	}	
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}


int main()
{
	int n;
	{
		Solution sln;
		n = 5;
		auto res = sln.findIntegers(n);
		Assert(5, res);
	}
	{
		Solution sln;
		n = 1;
		auto res = sln.findIntegers(n);
		Assert(2, res);
	}
	{
		Solution sln;
		n = 2;
		auto res = sln.findIntegers(n);
		Assert(3, res);
	}
	{
		Solution sln;
		n = 10;
		auto res = sln.findIntegers(n);
		Assert(8, res);
	}
	{
		Solution sln;
		n = 100;
		auto res = sln.findIntegers(n);
		Assert(34, res);
	}
}

2013年1月版

class Solution {
public:
int findIntegers(int n) {
if (1 == n)
{
return 2;
}
std::vector bits;
int tmp = n;
while (tmp > 0)
{
bits.insert(bits.begin(), tmp % 2);
tmp >>= 1;
}
const int iBitNum = bits.size();
//dp[i][0]表示i位 0结尾的可能数
vector<vector> dp(iBitNum, vector(2));//
dp[1][0] = 1;
dp[1][1] = 1;
for (int i = 2; i < dp.size(); i++)
{
dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
dp[i][1] = dp[i - 1][0];
}
int iNum = 0;// dp[iBitNum - 1][0] + dp[iBitNum - 1][1];
int iPreBit = 0;
for (int i = 0; i < iBitNum; i++)
{
const int iCurBit = bits[i];
if (i + 1 == iBitNum)
{
iNum += iCurBit ;
}
else
{
if (1 == iCurBit)
{
iNum += dp[iBitNum - i - 1][0] + dp[iBitNum - i - 1][1];
}
}
if (iCurBit & iPreBit)
{
break;
}
if (i + 1 == iBitNum)
{
iNum++;
}
iPreBit = iCurBit;
}
return iNum;
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 **C+

+17**
如无特殊说明，本算法用**C++**实现。