主題

LeetCode - 600. Non-negative Integers without Consecutive Ones 解題心得

Not In My Back Yard | 2021-12-16 00:00:06 | 巴幣 100 | 人氣 83

題目連結:


題目意譯:
給定一正整數 n,回傳範圍 [0, n] 當中,其二進位表示法不包含連續的 1 之數字的數量。

限制:
1 <= n <= 10 ^ 9



範例測資:
範例 1:
輸入: n = 5
輸出: 5
解釋:
以下為 ≦ 5 的非負整數以及它們的二進位表示法:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
在它們當中,只有整數 3 違反規則(有兩個連續的 1)而其他 5 個則符合規則。

範例 2:
輸入: n = 1
輸出: 2

範例 3:
輸入: n = 2
輸出: 3


解題思維:
先定義一個二維陣列 DP[i][j] ,其代表著長度 i 的數字且為 j 開頭(j = 0 或 1)之不含連續 1 的數字數量。

本題動態規劃(Dynamic Programming)的遞迴式很直觀,先設立初始條件
DP[0][0] = 1 、 DP[0][1] = 0
(長度 0 視為一個「0」,這是為了等等方便,而且剛好是「正確的」)

當 i ≠ 0 時,可以看到其為
DP[i][0] = DP[i - 1][0] + DP[i - 1][1] (開頭 0 可以接任何開頭)
DP[i][1] = DP[i - 1][0] (開頭 1 只能接開頭 0)

可以看到這樣,每個長度會包含著一連串 0 開頭的數字。例如 0000 、 00100 等等。但是這等等會很方便。



以 n = 5 為例,其二進位表示法為 "101"。我們從左至右(高位到低位)掃過一次:
101
因為當前位元為 1,而其右有 2 個位元,所以我們可以確定它至少包含了
DP[2][0] + DP[2][1] = 3
個無連續 1 數字。即 "000" 、 "001" 、 "010" 這三個,而這就是為什麼我們需要包含有著前導零的數字們,因為這邊的三個數字全部都是有著前導零的數字。而它們等價於 0 、 1 和 10。

101
因為當前位元為 0,因為無法產生新的貢獻,所以無視。

101
因為當前位元為 1,而其右有 0 個位元,所以我們可以確定它至少包含了
DP[0][0] + DP[0][1] = 1
個無連續 1 數字。而這個比較特殊,其代表是 "100"。因為紅色的「0」右邊沒有東西了,所以只可能有本身這一個數字。而這就是為什麼初始條件是 DP[0][0] = 1 、 DP[0][1] = 0。

最後因為 n 自身就是一個不含連續 1 的數字,所以還需要將其加入所求之中。因此最終所求 ≦ n 的不含連續 1 之數字數量總計為
3 + 1 + 1 = 5 個。



再以 n = 6 為例,其二進位表示法為 "110"。同樣地,從左至右掃過一次:
110
因為當前位元為 1,而其右有 2 個位元,所以我們可以確定它至少包含了
DP[2][0] + DP[2][1] = 3
個無連續 1 數字。即 "000" 、 "001" 、 "010" 這三個。

110
因為當前位元為 1,而其右有 1 個位元,所以我們可以確定它至少包含了
DP[1][0] + DP[1][1] = 2
個無連續 1 數字。即 "100" 、 "101" 這兩個。而因為此時已經將所有可能的組合求出來了,因此可以中斷過程(再繼續只會多加)。

這個現象只要 n 有連續的 1 出現時就會發生,例如 "10110" 、 "1101" 等紅色 1 之位置。因為從該數字之後,不可能再會有新的無連續 1 出現(因為當前就已經違反條件)。

因此最終所求 ≦ n 的不含連續 1 之數字數量總計為
3 + 2 = 5 個。

值得注意的是 n = 6 不符合題意,所以不能算進所求數量中。



而其他 n 值也與上同理。因此只要掃過一次 n 的位數便可以知道所求數量,因此時間複雜度為 O(log n),但是記得還有預處理的 O(1) 時間。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作