2020q3 Homework7 (quiz7)

contributed by < RusselCK >

tags: `RusselCK`

bitwise 操作＆遞迴呼叫＆編譯器最佳化練習題

Q1. 判斷是否為 Tail Recursion













int funcA(int i)
{
    if (i == 0)
        return 0;
    return 5 * funcA(i - 1);
}

int funcB(int i)
{
    if (i == 0)
        return 0;
    return funcB(i - 1);
}

Tail call 指的是一個函式的最後一條語句也是一個返回呼用函式的語句
- 即這個呼叫的返回值直接被當前函式返回的情形
- 在函式體末尾被返回的可以是對另一個函式的呼叫，也可以是對自身呼叫
若這個函式在尾位置呼叫本身（或是一個尾呼叫本身的其他函式等等），則稱這種情況為 Tail Recurtion

程式碼解析

#12: funcB(i) 的最後一句是 return funcB(i - 1);
- 呼叫本身，符合 Tail Recurtion 的定義
- 編譯器可以做 Tail Call Optimization, TCO
  - function call 原本的佔用 stack 情形
  - 以 funcB(i) 來說，執行到 return funcB(i - 1) 後，接下來只要等 funcB(i - 1) 的回傳值就可以了
    - 也就是說 funcB(i) 已經做完了，不需要再留 stack space 給 funcB(i)
    - 藉此達到省 stack space 的效果

#5 : funcA(i) 的最後一句為 return 5 * funcA(i - 1);
- 需要等 funcA(i - 1) 回傳再乘上 5 ，才是真正的返回值
- 不符合 Tail Recurtion 的定義
- 編譯器無法對其做 TCO

Q2.

Q3. LeetCode 226. Invert Binary Tree

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →





















struct TreeNode {
   int val;
   struct TreeNode *left;
   struct TreeNode *right;
};

struct TreeNode *invertTree(struct TreeNode *root)
{ 
    if (!root)
        return NULL;

    if (!root->left && !root->right)
        return root;

    struct TreeNode *tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

程式碼解析：


    if (!root)
        return NULL;

若為空樹，回傳 NULL


    if (!root->left && !root->right)
        return root;

若左右都無子樹，可直接回傳 root



    struct TreeNode *tmp = root->left;
    root->left = root->right;
    root->right = tmp;

將左、右子樹交換位置


    invertTree(root->left);
    invertTree(root->right);

左、右子樹分別遞迴作 invertTree
- 先後順序不影響結果

Q4. LeetCoee 201. Bitwise AND of Numbers Range

Given a range
$[m, n]$ where
$0 \leq m \leq n \leq 2147483647$ , return the bitwise AND of all numbers in this range, inclusive.

解法 I :








int rangeBitwiseAnd(int m, int n)
{ 
    if (m == 0) return 0;

    int diff = n - m;
    int count = diff ? 32U - __builtin_clz(diff) : 0;
    return m & n & MASK;  // MASK = ~((1U << count) - 1)
}

	Decimal	Binary
m	100	0110 0100
n	120	0111 1000
m & n		0110 0000
n - m	20	0001 0100
Mask	`~((1U << 5) - 1)`	1110 0000

Decimal	Binary	Decimal	Binary	Decimal	Binary
		8	0000 1000	16	0001 0000
1	0000 0001	9	0000 1001	17	0001 0001
2	0000 0010	10	0000 1010	18	0001 0010
3	0000 0011	11	0000 1011	19	0001 0011
4	0000 0100	12	0000 1100	20	0001 0100
5	0000 0101	13	0000 1101
6	0000 0110	14	0000 1110
7	0000 0111	15	0000 1111

題目要求為
$m$ &
$(m + 1)$ & … &
$(n - 1)$ &
$n$
m & n 可以得知結果之較大位數的 bits ( 第一個表格畫螢光的部份 )
接著我們還缺少的是，剩餘的 bits 應該為多少？
- 以上方例子來看， m、n 相差 20
- 由第二個表格可知 1 & 2 & …& 20 = 0000 0000
  - 且能保證後 5 個 bits 結果必為 0
  - 8 - __builtin_clz(20) = 8 - 3 = 5
因此，我們還須要一個 Mask = 1110 0000 = ~( 0001 1111 )
= ~( (0010 0000) - 1 ) = ~( (1 << 5) - 1 )
- 故 MASK = ~((1U << count) - 1)

Q5. LeetCode 97. Interleaving String

解法 I : Dynamic Programming


























bool isInterleave(char * s1, char * s2, char * s3){
    
    size_t n = strlen(s1), m = strlen(s2);
    if ((n + m) != strlen(s3))
        return false;
    
    bool dp[n+1][m+1];
    for (int i = 0; i < (n + 1); ++i )
        memset(dp[i], false, (m + 1));
    dp[0][0] = 1;
    
    for(int i = 1; i < (n + 1); ++i)
        dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
    
    for(int j = 1; j < (m + 1); ++j)
        dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]);
    
    for(int i = 1; i < (n + 1); ++i){
        for(int j = 1; j < (m + 1); ++j){
            dp[i][j] = (dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1])) ||
                       (dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1]));
        }
    }
    
    return dp[n][m];    
}

$s_{1}$ \ $s_{2}$		d	b	b	c	a
	1	0	0	0	0	0
a	1	0	0	0	0	0
a	1	1	1	1	1	0
b	0	1	1	0	1	0
c	0	0	1	1	1	1
c	0	0	0	0	0	1

DP[i][j] : s1[0:i-1] 與 s2[0:j-1] 是否能組成 s3[0:i+j-1]
程式碼解析：



    size_t n = strlen(s1), m = strlen(s2);
    if ((n + m) != strlen(s3))
        return false;

先確定 s1 + s2 的長度是否等於 s3 的長度




    bool dp[n+1][m+1];
    for (int i = 0; i < (n + 1); ++i )
        memset(dp[i], false, (m + 1));
    dp[0][0] = 1;

建立 DP 表格，並設置 dp[0][0] 為 1，其餘為 0
效能評估：

解法 II : DP with 1D Array


























bool isInterleave(char *s1, char *s2, char *s3)
{
    size_t n = strlen(s1), m = strlen(s2);
    if ((n + m) != strlen(s3))
        return false;

    bool dp[m + 1];
    memset(dp + 1, false, m * sizeof(bool));
    dp[0] = true;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 && j == 0)
                continue;
            int p = RRR; // RRR = i + j - 1
            if (i == 0)
                dp[j] = dp[j - 1] & (s2[j - 1] == s3[p]);
            else {
                dp[j] &= (s1[i - 1] == s3[p]);
                if (j > 0)
                    dp[j] |= dp[j - 1] & (s2[j - 1] == s3[p]);
            }
        }
    }
    return dp[m];
}

對解法 I 進行的修改：
- dp array 由 2D 改為 1D
  - 將解法 I 的表格一列一列計算完成並覆蓋舊資料
- 將三個 for 迴圈合併成一個
程式碼解析：














    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 && j == 0)
                continue;
            int p = RRR; 
            if (i == 0)
                dp[j] = dp[j - 1] & (s2[j - 1] == s3[p]);
            else {
                dp[j] &= (s1[i - 1] == s3[p]);
                if (j > 0)
                    dp[j] |= dp[j - 1] & (s2[j - 1] == s3[p]);
            }
        }
    }

#16、#17 等價於解法 I 的


    for(int j = 1; j < (m + 1); ++j)
        dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]);

#19 等價於解法 I 的


    for(int i = 1; i < (n + 1); ++i)
        dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);

#20、#21 等價於解法 I 的


        dp[i][j] = (dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1])) ||
                   (dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1]));

故 RRR = i + j - 1
效能評估:
- 與解法 I 沒什麼區別
- 或許可將 dp 改用 Bit Array 儲存

Q5. 進階題

解法 III : DP with Bit Array

__uint128_t MAX = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF;

bool isInterleave(char *s1, char *s2, char *s3)
{
    size_t n = strlen(s1), m = strlen(s2);
    if ((n + m) != strlen(s3))
        return false;

    __uint128_t dp = 1;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 && j == 0)
                continue;
            int p = i + j -1; 
            __uint128_t mask = MAX ^ ((__uint128_t)1 << j);
            if (i == 0){
                __uint128_t set = (1U & (dp >> (j - 1))) & (s2[j - 1] == s3[p]);
                dp = (dp & mask) | (set << j);
                // dp[j] = dp[j - 1] & (s2[j - 1] == s3[p]);
            } else {
                __uint128_t set = (s1[i - 1] == s3[p]);
                dp &= mask | (set << j);
                // dp[j] &= (s1[i - 1] == s3[p]);
                if (j > 0){
                    set = (1U & (dp >> (j - 1))) & (s2[j - 1] == s3[p]);
                    dp |= (set << j);
                    // dp[j] |= dp[j - 1] & (s2[j - 1] == s3[p]);
                }
            }
        }
    }
    return (dp >> m);
}

效能評估：

2020q3 Homework7 (quiz7)

tags: RusselCK

Q1. 判斷 是否為 Tail Recursion

Q2.

Q3. LeetCode 226. Invert Binary Tree

Q4. LeetCoee 201. Bitwise AND of Numbers Range

Q5. LeetCode 97. Interleaving String

解法 I : Dynamic Programming

解法 II : DP with 1D Array

Q5. 進階題

解法 III : DP with Bit Array

Read more

VSCode 套件安裝

ARGB To BW

深入淺出物件導向分析與設計 筆記

TCL 讀書會(?

tags: `RusselCK`

Q1. 判斷是否為 Tail Recursion

深入淺出物件導向分析與設計筆記