0-1字典树解决[不含连续1的非负整数]

不含连续1的非负整数

在该链接的基础上添加自己的理解https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/solution/suan-fa-xiao-ai-wo-lai-gei-ni-jie-shi-qi-4nh4/

class Solution {
public:
    int findIntegers(int n) {
        //初始化一棵树，直接使用动态规划计算每一层的 所求整数
        vector<int> dp(31);
        dp[0] = dp[1] = 1;
        for (int i = 2; i < 31; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        //pre用于记录上一层的值:0或1
        //res用于返回
        int pre = 0, res = 0;
        for (int i = 29; i >= 0; --i) {
            int val = 1 << i;    //取某一位
            if ((n & val) != 0) {    //判断是否与这一位有关，即该层是否有右子树
                
                n -= val;    //清除这一位
                res += dp[i + 1];    //有右子树的时候，把左子树的相关值添加到res
                
                //如果上一层为1且该层为1，则直接结束遍历
                if (pre == 1) {
                    break;
                }
                pre = 1;
            } else {        //若无右子树，则进入左子树，到下一层继续判断
                pre = 0;
            }

            if (i == 0) {
                ++res;
            }
        }

        return res;
    }
};

关于如何使用graphviz绘制二叉树

下载方式

linux:

1	`sudo apt-get install graphviz`

windows:

https://www.graphviz.org/download/

绘制方式

测试程序：

digraph binaryTree{
    node[shape=circle,color=red,fontcolor=blue,fontsize=10];
    root[color=blue,fontcolor=black,fontsize=20];
    root->a[style=dotted];
    root->b;
    a->c;
    a->d;
    b->e;
    b->f;
}