這是小川的第379次更新，第407篇原創
01 看題和準備
今天介紹的是LeetCode算法題中Easy級别的第241題（順位題号是1018）。給定0和1的數組A，考慮
N_i
：從
A[0]
到
A[i]
的第
i
個子數組被解釋為二進制數（從最高有效位到最低有效位）。
傳回布爾值
answer
清單，當且僅當
N_i
可被5整除時，
answer[i]
為
true
。
例如：
輸入：[0,1,1]
輸出：[true，false，false]
說明：二進制輸入數字為
,
01
011
，轉為十進制數，分别為0,1和3。隻有第一個數字可以被5整除，是以
answer[0]
true
輸入：[1,1,1]
輸出：[false，false，false]
輸入：[0,1,1,1,1,1]
輸出：[true，false，false，false，true，false]
輸入：[1,1,1,0,1]
輸出：[false，false，false，false，false]
注意：
- 1 <= A.length <= 30000
-
A[i]
02 解題
題目的意思是
A
中都是二進制位的0和1，依次從左到右，判斷二進制組成的十進制數能否被5整除，将每次的判斷結果存入
List
按照正常的操作，循環A中的元素，組成一個二進制字元串，再轉成十進制數，再對5取餘，将判斷結果存入
List
中，但是有個問題需要考慮，
A
的長度上限是30000，如果組合成的二進制字元串長度過長，是否還能被轉成整數？答案存疑，那我們需要換另外一種思路來解決問題了。
結合例子來看，
[1,1,1,0,1]
，從左往右看：
第一次計算，二進制數為
1
，轉為十進制為1，
1%5
=1。
第二次計算，二進制數為
11
，轉為十進制為3，
(1*2+1)%5
= 3%5 =3。
第三次計算，二進制數為
111
，轉為十進制為7，
(3*2+1)%5
= 7%5 =2。
第四次計算，二進制數為
1110
，轉為十進制為14，
(2*2+0)%5
= 4%5 = 14%5 =4。
第五次計算，二進制數為
11101
，轉為十進制為29，
(4*2+1)%5
= 9%5 = 29%5 =4。
從例子中可以看到，新的二進制數是在前一次二進制數的基礎上左移一位得到的，即
num[i+1] = (A[i]<<1) + A[i+1]
，
A[i]
為前一次的十進制整數，
A[i+1]
為在前一次二進制數尾部新加的0或1，題目隻是需要我們判斷每次新組成的二進制數能否被5整除，我們可以利用前一次取餘的結果左移，因為其中能被整除的部分是不太需要關心的，這樣可以避免數字過大超出範圍的風險。
public List<Boolean> prefixesDivBy5(int[] A) {
List<Boolean> answer = new ArrayList<Boolean>();
int num = 0;
for (int i=0; i<A.length; i++) {
// 寫成 num = (num<<1) + A[i]; 也是一樣的效果
num = num*2 + A[i];
num %= 5;
answer.add(num == 0);
}
return answer;
}
小結
算法專題目前已連續日更超過七個月，算法題文章247+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。
以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！