2020q3 sysprog Homework14 (quiz15)

tags: sysprog

contributed by < sciyen >

• 2020q3 sysprog Homework14 (quiz15)
  • Q1 [LeetCode 835. Image Overlap](https://leetcode.com/problems/image-overlap
  • Q2
  • Q3
    • 解題思路

作答表單

Q1 [LeetCode 835. Image Overlap](https://leetcode.com/problems/image-overlap

解題關鍵：

if (j >= 0) {
    for (int k = n - j - 1; k >= 0; k--) 
        res[k + j] = res[k];
    for (int k = 0; k < j; k++)
        res[k] = 0;
} else {
    j = -j;
    for (int k = j; k < n; k++) 
        res[k - j] = res[k];
    for (int k = n - j; k < n; k++)
        res[k] = 0;
}

• 當 j >= 0 表示往下移動 j 步，因此切成兩部分看：
  • 移動：因為資料有因果關係，從後面 (n-1) 開始替換
    • 舊資料範圍：n-j-1~0
    • 新資料範圍：n-1~j (為舊資料範圍 +j)
  • 填 0：
    • 新資料範圍：0~j-1
  ​​​​if j == 2:
  
  ​​​​00 01 02 03 ... 0(n-1)
  ​​​​10 11 12 13 ... 1(n-1)
  ​​​​20 21 22 23 ... 2(n-1)
  ​​​​30 31 32 33 ... 3(n-1)
  
  ​​​​ 0  0  0  0 ...      0
  ​​​​ 0  0  0  0 ...      0
  ​​​​00 01 02 03 ... 0(n-1)
  ​​​​10 11 12 13 ... 1(n-1)
  

• 當 j < 0 表示往上移動 j 步，因此切成兩部分看：
  • 移動：因為資料有因果關係，從前面 0 開始替換
    • 舊資料範圍：n-1~j
    • 新資料範圍：n-j-1~0 (為舊資料範圍 -j)
  • 填 0：
    • 新資料範圍：n-1~n-j
  ​​​​if j == -2:
  
  ​​​​00 01 02 03 ... 0(n-1)
  ​​​​10 11 12 13 ... 1(n-1)
  ​​​​20 21 22 23 ... 2(n-1)
  ​​​​30 31 32 33 ... 3(n-1)
  
  ​​​​20 21 22 23 ... 2(n-1)
  ​​​​30 31 32 33 ... 3(n-1)
  ​​​​ 0  0  0  0 ...      0
  ​​​​ 0  0  0  0 ...      0
  

Q2

Q3

解題思路

重點在從 file 切割字串的 index 範圍，從 function definition

static void htable_insert(size_t fpos, size_t len);

可以得知前者是 開始 index ，後者是 字串長度

• 決定字串長度：
  字串應包含 開始 index(prev_start) ，因此長度為 目前 index(i) - 開始 index + 1，也就是 i - prev_start + 1。
• 更新 prev_start：
  目前 i 應為 \n ，因此下一個起點應為 i+1