今天的題單：

• Counting Bits

• Same Tree

338. Counting Bits

思路：可以用右位移 1 與 1 做 AND operation （i.e., n >> 1 & 1）方式計算一個數字的 binary number 有幾個 1，計算一個數字所需時間是 O(logn)，n 個數字就是 O(nlogn)

class Solution {
public:
    vector<int> countBits(int n) {
        // O(nlogn)
        vector<int> bits(n+1, 0);
        for (int i = 0; i <= n; i++) {
            unsigned int num = i;
            while (num != 0) {
                if (num & 1) {
                    bits[i] ++;
                }
                num = num >> 1;
            }
        }
        return bits;
    }
};

Follow-up: 能否在 O(n) time 做完？

實作一：可以直接利用 __builtin_popcount() 直接得到數字的 binary 有幾個 1

class Solution {
public:
    vector<int> countBits(int n) {
        // O(nlogn)
        vector<int> bits(n+1, 0);
        for (int i = 0; i <= n; i++) {
            bits[i] = __builtin_popcount(i);
        }
        return bits;
    }
};

實作二：不使用 __builtin_popcount()

把 binary 全部寫出來可以觀察到規律：binary 在進位之後（1,2,4,8…）在低位會重複之前的規律，由於進位的關係，所以進位重置後 1 的數量會比前面重複的部分多 1：

n -> binary -> count_1
----------------------
0 -> 0000 -> 0
----------------------
1 -> 0001 -> 1
----------------------
2 -> 0010 -> 1
3 -> 0011 -> 2
----------------------
4 -> 0100 -> 1
5 -> 0101 -> 2
6 -> 0110 -> 2
7 -> 0111 -> 3
----------------------
8 -> 1000 -> 1
9 -> 1001 -> 2
10 -> 1010 -> 2
11 -> 1011 -> 3
12 -> 1100 -> 2
13 -> 1101 -> 3
14 -> 1110 -> 3
15 -> 1111 -> 4

由於只需要查找前面的 count 紀錄 +1，所以 loop 一遍就能完成。

因為要判斷進位，可以設一個 counter 來計數。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n+1, 0);
        int boundary = 1;
        int count = 0;

        for (int i = 1; i <= n; i++) {
            if (count < boundary) {
                bits[i] = bits[count] + 1;
                count++;
            }

            if (count == boundary) {
                boundary *= 2;
                count = 0;
            }
        }
        return bits;
    }
};

100. Same Tree

思路：兩顆樹如果一樣，tree traversal 的順序也會相同。

實作一：把兩棵樹都走一次，紀錄數值順序，再比較兩棵樹的紀錄是否相同。這裡我使用 preorder traversal

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        vector<int> trace_p;
        vector<int> trace_q;

        preorder(p, trace_p);
        preorder(q, trace_q);

        vector<int>::iterator it_p = trace_p.begin();
        vector<int>::iterator it_q = trace_q.begin();

        while (it_p != trace_p.end() && it_q != trace_q.end()) {
            if (*it_p != *it_q) {
                break;
            }
            it_p++;
            it_q++;
        }
        
        if (it_p == trace_p.end() && it_q == trace_q.end()) {
            return true;
        } else {
            return false;
        }
        
    }

    void preorder(TreeNode* node, vector<int>& trace) {
        if (node == nullptr) {
            trace.push_back(100000);
            return;
        }
        trace.push_back(node->val);
        preorder(node->left, trace);
        preorder(node->right, trace);
    }
};

實作二：邊走邊檢查是否相同，如果有不同直接 return，不用把樹全部走完。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        }
      
        if (p == nullptr ^ q == nullptr) {
            return false;
        } else {
            if (p->val != q->val) {
                return false;
            } else {
                return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
            }
        }
    }

};

一些感想

寫到這邊發現對於判斷「兩個物件的關係」的題目通常能有兩類作法

1. 兩邊分別全部看完再判斷

2. 邊做邊判斷

雖然以時間複雜度來說通常都是 O(n) ，但這是看 worst case。後者在做到一半的時候發現條件不符合就可以直接退出，不需要等到全部做完，所需時間會較少。在實際遇到的問題上，如果遇到 n 很大的 case，後者作法效率較好。