求助

剑指 Offer 15. 二进制中1的个数

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

我的第一版代码：

Help Wanted

Number of 1 Bits

Write a function that takes an unsigned integer (in binary string form) and returns the number of ‘1’ bits in its binary representation.

My first version of the code:

1
2
3
4
5
6
7
8
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 位。

This looks fine to me. The base cases are set up, n&1 checks whether the lowest bit is 1, plus the recursive call on n shifted right by 1 bit.

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

image-20210923225717708

于是我简单改了一下代码

But it failed to pass when I ran it! I have no idea why, and I hope some expert passing by can leave a comment and point it out.

image-20210923225717708

So I slightly modified the code

1
2
3
4
5
6
7
8
9
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);
    }
};

点击提交。

image-20210923230046403

疑惑。

2022 年 3 月 28日

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

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

Click submit.

image-20210923230046403

Confused.

March 28, 2022

Oh my😥, it turned out to be just an operator precedence issue.

The precedence of the & operator is lower than that of the + operator

1
2
3
4
5
6
7
8
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. 重建二叉树

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

例如：

img

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

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

Another One

Construct Binary Tree from Preorder and Inorder Traversal

Given the preorder and inorder traversal results of a binary tree, build the binary tree and return its root node.
Assume that neither the preorder nor the inorder traversal results contain duplicate numbers.

For example:

img

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

This problem is a simple data structure exercise, so I wrote the code following the conventional approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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;
    }
};

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

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

The code above probably reported some type error. I couldn’t understand what it meant, and I checked many times whether my own implementation was wrong, but to no avail.

So I tried slicing the left and right subtree sequences from the preorder sequence first, and then passing them as parameters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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;
    }
};

竟然通过了！

也是很疑惑，C++的语法细节还挺多，这要是 Python ，应该没有这种乱七八糟的问题吧。

后来查了一下问题产生的原因，大概是由于错误的代码中，vector 的构造函数得到的是一个临时变量，应该是即将就销毁的，而我把临时变量以引用的方式传递给函数了，所以出错了。

It passed!

It’s also quite confusing. C++ has so many syntax details. If this were Python, there probably wouldn’t be such messy problems.

Later I looked up the cause of the problem. It’s probably because in the buggy code, the vector constructor produced a temporary variable that was about to be destroyed, and I passed that temporary variable to the function by reference, which caused the error.