contributed by < RusselCK
>
RusselCK
dynamic programming & bitwise 操作 & linked list & 非連續記憶體操作 練習題
Given
n
representing the number of courses at some university labeled from 1
to n
dependencies[i] = [xi, yi]
represents a prerequisite relationship
xi
must be taken before the course yi
.k
courses as long as you have taken all the prerequisites for the courses you are taking.Return the minimum number of semesters to take all courses.
Example:
recursive-nos1.c
)#25
: pre[cap]
: 課程 cap
的前導課程的 bit mask
cap
=
pre[]
中代表課程的 index ( 實際上只會用到 0
~ n-1
)dp[]
中代表已修過的課程的 bit mask#26
: (初始) 全為 0
pre[0] |
0...0 1110 |
---|---|
pre[4] |
0...0 0001 |
pre[o.w.] |
0 |
#30
: dp[cap]
: 完成cap
所需要的最少學期數
#31~33
: (初始) dp[0] = 0
,其餘為 INT_MAX
(infinity 的實作)s0
: 已修過的課程的 bit masks1
: 目前可選擇的新課程#39~42
: 求s1
((s0 >> i) & 1)
: 課程i
是否已經修過了(pre[i] & s0) == pre[i])
: 課程i
的先修是否已經修完了#42
: 若課程i
滿足可選擇的條件,則加入s1
#44
: 從 s1
中找出至多 門可選擇的課程,其 bit mask 為 s
(從課程 i = 0
開始找起)
solve(int i = 0, int s = 0, int k, int n, int s0, int s1, int *dp)
若還有可以選擇課程的 quota 且 還有課程可以檢查 (即 !((k == 0) || (i == n))
) :
#12
: solve(i + 1, s, k, n, s0, s1, dp);
從完成 dp 的精神 – 建置表格
s1
中找出至多 門可選擇的課程,其 bit mask 為 s
(從課程 i+1
開始找起)#14~15
: 若 課程i
在 s1
的選項中 (即 (s1 >> i) & 1
),則將課程i
納入s
,並減少一個可選擇的 quota (即 k - 1
),接著找尋下一個可選擇的課程 (從課程 i + 1
開始找起)
solve(i + 1, s | 1 << i, k - 1, n, s0, s1, dp);
若沒有可以選擇課程的 quota 或 沒有課程可以檢查 (即 ((k == 0) || (i == n))
) :
#8
: dp[s0 | s] = min(dp[s0 | s], dp[s0] + 1);
#47
: dp[cap - 1];
即為修完所有課程至少需要的學期數
iterative-nos1.c
)#9
:prerequisite[n];
: 課程 n
的前導課程的 bit mask
1 <= n <= 15
,因此使用 uint16_t
就足夠了#15
: dp[cap]
: 完成cap
所需要的最少學期數
1 <= k <= n <= 15
,因此使用 uint8_t
就足夠了
甚至還太多,4 bits 就可以了
#16
: memset(dp, 1 << 6, cap);
1 << 6
可以換成 14
,只要是 bit mask 有效範圍以外的數值即可
leetcode 的測試的答案最多只到 13 ,所以最小換到
13
也能過
memset(dp, 1 << 6, sizeof(dp));
,但為何 memset(dp, 1 << 6, cap);
也可以?sizeof(dp)
= cap
* 8 bits = cap
* 1 bytes = cap
bytesvoid *memset(void *s, int c, size_t n);
n
bytes of the memory area pointed to by s
with the constant byte c
.#20~24
: 求 s1
(目前可選擇的新課程)
i
= s0
(某個已修過的課程的 bit mask)ready_for_take
= s1
#26~30
: 非遞迴版本的 solve(int i = 0, int s = 0, int k, int n, int s0, int s1, int *dp);
#26
: ready_for_take &= ~i;
: 在尚未修完的課程中,所有符合前導規定且可選擇的新課程的 bitmask#27
: 由 j = ready_for_take & (j - 1)
來一個一個找尋選課數量不超過 k
的 bitmaskiterative-nos2.c
)#20
: memset(dp, INIT, sizeof(dp));
14
即可0x5F
#23
: count[cap];
: cap
代表的修課數量
#26~28
換成 count[i] = __builtin_popcount(i);
可以更快#37~40
: 求 s1
(目前可選擇的新課程)
b
= s1
i
= s0
(某個已修過的課程的 bit mask)j
(課程編號)!(i & (1 << j))
#41~42
: 若 b
可選的數量不超過 k
,代表 b
挑出的課程都能用 1 學期就修完
if...else...
可以省去第二種方法中一些多餘的執行步驟#43~48
: 反之,就要從 b
中挑出至多 k
個課程的 bit mask j