作者推荐
涉及知识点
数位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;
}
};
