重庆电商网站建设费用,做网站推广要注意的事项,wordpress inove,网站建设哪便宜作者推荐
【动态规划】C算法312 戳气球
本文涉及的基础知识点
动态规划 数位dp
LeetCode:233数字 1 的个数
给定一个整数 n#xff0c;计算所有小于等于 n 的非负整数中数字 1 出现的个数。 示例 1#xff1a; 输入#xff1a;n 13 输出#xff1a;6 示例 2#xff…作者推荐
【动态规划】C算法312 戳气球
本文涉及的基础知识点
动态规划 数位dp
LeetCode:233数字 1 的个数
给定一个整数 n计算所有小于等于 n 的非负整数中数字 1 出现的个数。 示例 1 输入n 13 输出6 示例 2 输入n 0 输出0 提示 0 n 109
数位dp的封装类
本题比较简单主要讲封装类。m_vPre记录上一位所有状态程序结束时记录的是最后一位的所有状态。 m_vPre是二维向量一维长度4分别表示4种边界状态下标0记录 非上下界下标1记录下界下标2记录上界3记录同时上下界。二维长度由构造函数的参数iResutlCount决定。ResultType类记录状态。
ELE枚举的元素类型minEle元素最小值maxEle元素最大值pLower下界pHigh上界iNum上下界的长度
使用的时完成OnEnumFirstBit和OnEnumOtherBitOnEnumFirstBit会不重复不遗漏的枚举第一位的 元素和边界状态。 OnEnumOtherBit此函数会不重复不遗漏的依次枚举其它位的元素和边界状态。 只会枚举在范围内的状态不会枚举非法状态。 pre和dp 是对应边界状态的状态所以是一维向量。 注意 : 同一位 同一元素 同一状态 可能枚举两次这不会造成重复计算。因为是两层枚举第一层枚举前一元素的边界状态第二层枚举当前元素。
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;
};本题代码
核心代码
//pairint, int first记录在范围内符合要求的子串数量 second 记录1的数量
class CCharLowerUper : public CLowUperrchar, pairint, int, 0, 9
{
public:using CLowUperrchar, pairint, int, 0, 9::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].second;}ret cur;std::cout index: index cur std::endl;}return ret;}
protected:virtual void OnEnumFirstBit(vectorpairint, int vPre, const char curValue){const int index curValue - 0;vPre[index].first 1 ;vPre[index].second 1 index;}virtual void OnEnumOtherBit(vectorpairint,int dp, const vectorpairint, int vPre, char curValue){const int index curValue - 0;for (int i 0; i 10; i){dp[index].first vPre[i].first;dp[index].second vPre[i].second;if (1 index){dp[index].second vPre[i].first;}} }};
class Solution {
public:int countDigitOne(int n) {const string strN std::to_string(n);const int len strN.length();int iRet 0;for (int i 1; i len; i){CCharLowerUper lu(10);lu.Init((1 string(i - 1, 0)).c_str(),string(i,9).c_str(),i);iRet lu.Total(0, 9);}CCharLowerUper lu(10);lu.Init((1 string(len - 1, 0)).c_str(), strN.c_str(), len);iRet lu.Total(0, 9);return 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()
{vectorint nums;{Solution sln;int n 30;auto res sln.countDigitOne(n);Assert(13, res);}{Solution sln;int n13;auto res sln.countDigitOne(n);Assert(6, res);}{Solution sln;int n 0;auto res sln.countDigitOne(n);Assert(0, res);}}2023年1月版
class Solution { public: int countDigitOne(int n) { int iNum 0; int iMul 1; for (int i 0; i 9; i) { iNum n / (iMul * 10) *iMul; int tmp n % (iMul * 10); if (tmp iMul) { if (tmp iMul * 2) { tmp iMul * 2 - 1; } iNum tmp - (iMul - 1); } iMul * 10; } if (1000 * 1000 * 1000 n) { iNum; } return iNum; } };
2023年8月
class CTest : public CLowUperrchar,int,‘0’,‘9’ { public: CTest():CLowUperr(10) { } // 通过 CLowUperr 继承 virtual void OnDo(vectorvector dp, int preStatus, int curStatus, int cur) override { dp[curStatus][cur] m_vPreCan[preStatus]; m_vCurOneNum[curStatus] m_vPreOneNum[preStatus]; } virtual void OnInitDP(vectorvector dp) { for (int i 0; i 4; i) { m_vPreCan[i] std::accumulate(MACRO_BEGIN_END(m_vPre[i]), 0); m_vPreOneNum[i] m_vCurOneNum[i] m_vPre[i][1]; } memset(m_vCurOneNum, 0, sizeof(m_vCurOneNum)); } int Total() { int iRet 0; for (int i 0; i 4; i) { iRet m_vCurOneNum[i] m_vPre[i][1]; } return iRet; } int m_vPreCan[4] { 0 };//前四中状态的可能 int m_vPreOneNum[4] { 0 };//前面4种状态1的数量 int m_vCurOneNum[4] { 0 };//前面4种状态1的数量 };
class Solution { public: int countDigitOne(int n) { string str std::to_string(n); int len 1; for (; len str.length(); len) { Do(“1” string(len - 1, ‘0’), string(len, ‘9’)); } Do(“1” string(len - 1, ‘0’), str); return m_iRet; } void Do(string s1, string s2) { CTest test; test.Init(s1.data(), s2.data(), s1.length()); m_iRet test.Total(); } int m_iRet; }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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**实现。
