C艹这门语言有点奇怪

注意：这篇文章上次更新于950天前，文章内容可能已经过时。

求助

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数

我的第一版代码：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        if(n == 1) return 1;
        if(n == 0) return 0;
        return n&1 + hammingWeight(n>>1);
    }
};

这个我看起来问题不大啊，边界条件设置好，n&1 计算最低位是不是 1 ，再加上递归调用 n 的右移1 位。

可是一运行却无法通过？ ~~我不明白原因是什么，希望路过的大佬能留言指出。~~

于是我简单改了一下代码

class Solution {
public:
    int hammingWeight(uint32_t n) {
        if(n == 1) return 1;
        if(n == 0) return 0;
        int x = n&1;
        return x + hammingWeight(n>>1);
    }
};

点击提交。

疑惑。

2022 年 3 月 28日

天哪😥，竟然仅仅是因为运算符优先级的问题。

& 运算符没有 + 运算符优先级高

class Solution {
public:
    int hammingWeight(uint32_t n) {
        if(n == 1) return 1;
        if(n == 0) return 0;
        return (n&1) + hammingWeight(n>>1);
    }
};

还有一个

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如：

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

这题本身是一道简单的数据结构问题，按照常规的思路写了代码。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0) return nullptr;
        
        // 创建根节点
        TreeNode* root = new TreeNode();  
        
        // 根节点赋值先序遍历的第一个节点
        root->val = preorder[0];
        
        // 在中序序列中寻找根节点的位置
        auto it = find(inorder.begin(),inorder.end(),preorder[0]);
        
        // 计算左子树的长度
        int len = it - inorder.begin();
        
        // 递归调用本函数创建左子树和右子树
        // 问题就出在这里。
        root->left = buildTree(vector<int>(preorder.begin()+1,preorder.begin()+1+len),vector<int>(inorder.begin(),it));
        root->right = buildTree(vector<int>(preorder.begin()+1+len,preorder.end()),vector<int>(it+1,inorder.end()));
        return root;
    }
};

上面的代码大概是报了一个类型的错误，我也看不懂什么意思，检查了好多次是不是自己实现的有问题，还是无果。

于是我尝试把先序序列的左右子树序列先切割好，再作为参数传递。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0) return nullptr;
        TreeNode* root = new TreeNode();
        root->val = preorder[0];
        auto it = find(inorder.begin(),inorder.end(),preorder[0]);
        int len = it - inorder.begin();
        vector<int> preleft = vector<int>(preorder.begin()+1,preorder.begin()+1+len);
        vector<int> inleft = vector<int>(inorder.begin(),it);
        root->left = buildTree(preleft,inleft);
        vector<int> preright = vector<int>(preorder.begin()+1+len,preorder.end());
        vector<int> inright = vector<int>(it+1,inorder.end());
        root->right = buildTree(preright,inright);
        return root;
    }
};