主題

LeetCode - 1680. Concatenation of Consecutive Binary Numbers 解題心得

Not In My Back Yard | 2021-09-08 00:00:03 | 巴幣 0 | 人氣 46

題目連結:


題目意譯:
給定一整數 n ,回傳將 1 到 n 的二進位表示法依序串接在一起所得到的二進位字串,其所代表的十進位數字模 10 ^ 9 + 7 之值。

限制:
1 ≦ n ≦ 10 ^ 5



範例測資:
範例 1:
輸入: n = 1
輸出: 1
解釋: "1" 於二進位中對應著十進位中 1 的值。

範例 2:
輸入: n = 3
輸出: 27
解釋: 二進位中,1 、 2 、 3 對應著 "1" 、 "10" 和 "11" 。
將它們串接在一起,我們得到 "11011",其對應著十進位數字 27 。

範例 3:
輸入: n = 12
輸出: 505379714
解釋: 串接結果為 "1101110010111011110001001101010111100" 。
該十進位值為 118505380540 。
模 10 ^ 9 + 7 後,結果為 505379714 。


解題思維:
我們可以先建表(Leetcode 建表方式可以參見這題)。

假設我們的所求存在陣列 D 中。則我們從 D[0] = 0 開始,當每次我們計算到 D[i] 時,先將 D[i - 1] 左移 X + 1 位元(因為是在建表,所以請不要真的動到 D[i - 1] 之值),然後把此時的 D[i - 1] 加上 i 之值。其中 X 為 i 在二進位表示法中的長度(例如數字 14 為 1100 ,長度為 4)。

然後每計算一次請記得把 D[i] 之值模(取餘數)10 ^ 9 + 7 避免溢位。而建表完之後,對於任意 n 值,只要回傳 D[n] 即可。




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

創作回應

相關創作

更多創作