主題

LeetCode - 1018. Binary Prefix Divisible By 5 解題心得

Not In My Back Yard | 2021-03-10 00:00:01 | 巴幣 0 | 人氣 71

題目連結:


題目意譯:
給定一個只由 0 和 1 組成的陣列,現在考慮 N_i : 其定為第 i 個子陣列,從 A[0] 到 A[i] 並將該段詮釋為一個二進位制數字(從最高位位元到最低位位元)

回傳一個布林列表 answer,其中 answer 為真(True)若且唯若 N_i 可以被 5 整除。

注:
1 ≦ A.length ≦ 30000
A[i] 為 0 或是 1



範例測資:
範例 1:
輸入: [0,1,1]
輸出: [true,false,false]
解釋:
輸入之二進位數字為 0 、 01 、 011,其各自為十進位的 0 、 1 以及 3。只有第一個數字可被 5 整除,所以 answer[0] 為真。

範例 2:
輸入: [1,1,1]
輸出: [false,false,false]

範例 3:
輸入: [0,1,1,1,1,1]
輸出: [true,false,false,false,true,false]

範例 4:
輸入: [1,1,1,0,1]
輸出: [false,false,false,false,false]


解題思維:
可以利用餘數的特性(如這題)——先取餘還是後取餘,兩者結果皆同餘。

因此,如果我們已知 N_k 視為二進位數字後除以 5 的餘數為 R ,則 N_(k+1) 視為二進位數字後除以 5 的餘數 R' 恰好等於
(R × 2 + A[k + 1]) mod 5
當 R' 為 0 時就代表 N_(k+1) 可以被 5 整除,所以 answer[k + 1] 為真;反之,answer[k + 1] 為假。




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

創作回應

相關創作

更多創作