用自己的电脑建网站,怎么申请自己的企业邮箱,用什么软件做动漫视频网站,中国制造网外贸站作者推荐
【矩阵快速幂】封装类及测试用例及样例
涉及知识点
数位dp
LeetCode600. 不含连续1的非负整数
给定一个正整数 n #xff0c;请你统计在 [0, n] 范围的非负整数中#xff0c;有多少个整数的二进制表示中不存在 连续的 1 。 示例 1: 输入: n 5 输出: 5 解释: 下…作者推荐
【矩阵快速幂】封装类及测试用例及样例
涉及知识点
数位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’ 皆可。
代码
封装类
templateclass 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, vectorResultType(m_iResutlCount));if (iNum 0){return;}InitPre(pLower, pHigh);iNum--;while (iNum--){pLower;pHigh;vectorvectorResultType dp(4, vectorResultType(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(vectorResultType dp, const vectorResultType vPre, ELE curValue) 0;virtual void OnEnumFirstBit(vectorResultType vPre, const ELE curValue) 0;virtual void OnInitDP(vectorvectorResultType dp){}vectorvectorResultType m_vPre;
};核心代码
class CCharLowerUper : public CLowUperrchar, int, 0, 1
{
public:using CLowUperrchar, 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(vectorint vPre, const char curValue){const int index curValue - 0;vPre[index];}virtual void OnEnumOtherBit(vectorint dp, const vectorint 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;}
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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结尾的可能数 vectorvector 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 C17 或者 操作系统win10 开发环境 VS2022 **C
17** 如无特殊说明本算法用**C**实现。
