leetcode 600. Non-negative Integers without Consecutive Ones 非负整数不包括连续的1 + DP动态规划

た入场券 2022-06-03 05:11 140阅读 0赞

Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.

Example 1:  
Input: 5  
Output: 5  
Explanation:  
Here are the non-negative integers <= 5 with their corresponding binary representations:  
0 : 0  
1 : 1  
2 : 10  
3 : 11  
4 : 100  
5 : 101  
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.  
Note: 1 <= n <= 109

题意很简单，但是做起来真的很难，很明显直接暴力求解肯定超时，感觉这个可以使用DP来做，但是不会做递推式的推导，所以只能网上找答案了。

计算该字符串长度的二进制数所有无连续1的数字个数，然后我们从倒数第二个字符开始往前遍历这个二进制数字符串，如果当前字符和后面一个位置的字符均为1，说明我们并没有多计算任何情况，不明白的可以带例子来看。如果当前字符和后面一个位置的字符均为0，说明我们有多计算一些情况，就像之前举的100这个例子，我们就多算了101这种情况。我们怎么确定多了多少种情况呢，假如给我们的数字是8，二进制为1000，我们首先按长度为4算出所有情况，共8种。仔细观察我们十进制转为二进制字符串的写法，发现转换结果跟真实的二进制数翻转了一下，所以我们的t为”0001”，那么我们从倒数第二位开始往前遍历，到i=1时，发现有两个连续的0出现，那么i=1这个位置上能出现1的次数，就到one数组中去找，那么我们减去1，减去的就是0101这种情况，再往前遍历，i=0时，又发现两个连续0，那么i=0这个位置上能出1的次数也到one数组中去找，我们再减去1，减去的是1001这种情况

主要参考这个教程[\[LeetCode\] Non-negative Integers without Consecutive Ones 非负整数不包括连续的1][LeetCode_ Non-negative Integers without Consecutive Ones _1]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int findIntegers(int num)
        {
            int n = num;
            string t = "";
            while (n > 0)
            {
                t += (n & 1) == 1 ? "1" : "0";
                n = n >> 1;
            }
    
            vector<int> zero(t.length() , 0), one(t.length(), 0);
            zero[0] = one[0] = 1;
            for (int i = 1; i < t.length(); i++)
            {
                zero[i] = zero[i - 1] + one[i -1];
                one[i] = zero[i - 1];
            }
    
            int res = zero[t.length() - 1] + one[t.length() - 1];
            for (int i = t.length() - 2; i >= 0; i--)
            {
                if (t[i] == '1' && t[i + 1] == '1')
                    break;
                if (t[i] == '0' && t[i + 1] == '0')
                    res -= one[i];
            }
            return res;
        }
    };

[LeetCode_ Non-negative Integers without Consecutive Ones _1]: http://www.cnblogs.com/grandyang/p/6959585.html