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

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

思路:

经过一个晚上的沉淀,我终于写出了惹~

这道题我愿意称之为hard。首先遍历n是不可行的,其次考虑发现高位上数字变化对地位并没有影响,产生的结果就是子问题的分解和无历史影响性。

我们可以试着讨论:dp[i][j]指出长度为i,且最高位为j的作为最大数字n,那么dp[i][j]=小于或等于 n 的非负整数中,其二进制表示不包含 连续的1 的个数。
$$
\begin{matrix}
dp[i][0] = dp[i - 1 ][0] + dp[i - 1][1] \
dp[i][1] = dp[i - 1][0]
\end{matrix}
$$
可以发现,dp[i][1]可以被消掉,化成:
$$
\begin{matrix}
dp[i] = dp[i - 1 ] + dp[i - 2]
\end{matrix}
$$
也就是斐波那契方程式。

那么如何求出对于n题解值呢?题解给出了更好的理解方式“数字字典树”。

这棵树是由所有小于等于 n所构成的字典树,其中dp[2]就是图中根节点下的左节点所能求出的 非连续 1的数字数量。

再观察可以发现,有效数字所构成的路径都是成簇状的,收敛到某一个 0节点的,而不是它的兄弟节点1。再进一步可以发现,有右节点的一定有左节点,反之则不一定。利用这个性质我们可以快速获取各个位上的有效路径数量。

我们对于 数字n,可以遍历n的各个位数,或者说遍历数字字典树的最右路线:

  1. k从 31开始遍历到 0。
    • 如果当前位b0,说明该位只有左节点,而且路径未定。k--
    • 如果当前位b1,说明该位必定有左节点,可以直接加上左节点所有有效路径。k--。如果有上一位也是1说明,右节点代表的数字无效,可以直接break
    • 如果k==0,说明遍历到了最低位,且n本身也有效,而且没有被技术,有效路径再加1

代码:

class Solution {
    using ll = long long;
    vector<int> dp;
public:
    int findIntegers(int n) {
        dp.resize(64);
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2; i < 34; i++) dp[i] = dp[i - 1] + dp[i - 2];
        
        int integerNumber = 0;
        int pre = 0;
        int k = 31;
        while(k >= 0) {
            if((1 << k) & n) {
                integerNumber += dp[k];
                // n-=(1<<k);
                if(pre == 1) {
                    break;
                }
                pre = 1;
            } else {
                pre = 0;
            }
            if(k == 0) integerNumber++; // add missing tail path of n, etc "100", "100101",excluding "10011"
            k--;
        }
       
        return integerNumber;
    }
};

Comments