/* 給定由若干 0 和 1 組成的數組 A。我們定義 N_i：從 A[0] 到 A[i] 的第 i 個子數組被解釋為一個二進制數（從最高有效位到最低有效位）。返回布爾值列表 answer，只有當 N_i 可以被 5 整除時，答案 answer[i] 為 true，否則為 false。 示例 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]提示： 1 <= A.length <= 30000 A[i] 為 0 或 1來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/binary-prefix-divisible-by-5 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。 */

　

方法1:

由于1 <= A.length <= 30000 顯然直接做二進制位移很容易溢出,不能直接做移位操作或乘2操作，必然溢出。
對于取余操作有如下恒等式

$(A*2+B)%5 == ( (x+5*y)*2 + B) % 5 == (x*2+B)%5 == ((A%5)*2 + B)%5$

代碼如下：

bool* prefixesDivBy5(int* A, int ASize, int* returnSize) {bool* ret_val = NULL ;int i = 0 ;int j = 0 ;unsigned int temp_sum = 0 ;do{if( (A==NULL)||(ASize<=0)||(returnSize==NULL)){*returnSize = 0;break;}ret_val = (bool*)malloc(sizeof(bool)*ASize);if(ret_val == NULL){break; }else{for(i=0;i<ASize;i++){ret_val[i] = false; }for(i=0;i<ASize;i++){temp_sum = (temp_sum << 1)+A[i]; /*這里需要注意優先級*/if(temp_sum%5==0){ret_val[i] = true;}temp_sum = temp_sum%5; }}*returnSize = ASize;}while(0);return ret_val; }

提交結果如下：

/* 執行結果：通過 顯示詳情 執行用時 :36 ms, 在所有 C 提交中擊敗了92.59%的用戶 內存消耗 :11.5 MB, 在所有 C 提交中擊敗了6.52%的用戶 */

　　

?

方法2：

[0,4]*2+[0,1]? 的結果的范圍在[0,9]之間，我們可以建立一個10個數據長度數組，用來存儲0～9對5取余數的結果，對取余操作進行優化。

bool* prefixesDivBy5(int* A, int ASize, int* returnSize) {bool* ret_val = NULL ;int i = 0 ;unsigned int temp_sum = 0 ;const unsigned int arr[] = {0,1,2,3,4,0,1,2,3,4};do{if( (A==NULL)||(ASize<=0)||(returnSize==NULL)){*returnSize = 0;break;}ret_val = (bool*)malloc(sizeof(bool)*ASize);if(ret_val == NULL){break; }else{for(i=0;i<ASize;i++){ret_val[i] = false; }for(i=0;i<ASize;i++){temp_sum = arr[((temp_sum << 1)+A[i])]; /*這里注意優先級*/if(temp_sum==0){ret_val[i] = true;} }}*returnSize = ASize;}while(0);return ret_val; }

　　

/* 執行結果：通過 顯示詳情 執行用時 :28 ms, 在所有 C 提交中擊敗了98.77%的用戶 內存消耗 :11.7 MB, 在所有 C 提交中擊敗了6.52%的用戶 */

　　

?

轉載于:https://www.cnblogs.com/alimy/p/11169815.html

總結

以上是生活随笔為你收集整理的[力扣]1018_可被5整除的二进制前缀的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。