LeetCode 1018(Daily)題解

內文包括許多Latex語句，使用閱讀器等工具閱讀可能造成閱讀障礙。

題目描述

給定由0和1組成的int陣列nums，定義$x_i$為以nums第0到第i個元素組成的二進位數字，請回傳一個長度和nums相同的bool陣列answer，其中answer[i]表示$x_i$是否能被5整除。

思考路徑

因為

\[x_i = 2x_{i-1} + nums[i]\]

直接以題目要求的做法思考，會得出以下流程：

1. 紀錄一個整數n
2. 用for走過nums
   1. 將n左移一位（可以直接*=2或是會位元的人可以n<<=1，速度上差不多）為右邊留下空間
   2. 將nums[i]加到n上（補上最右邊那位）
   3. 判斷n是否能被5整除，並將結果存入answer
3. 回傳answer

將思路整理成程式如下

Runtime Error
7 / 24 testcases passed

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& nums) {
        vector<bool> v(nums.size());
        int n = 0;
        for(int i = 0; i < nums.size(); i++){
            n *= 2;
            n += nums[i];
            v[i] = (n%5)==0;
        }
        return v;
    }
};

Testcase過了，但是運算上出錯了…？

Line 7: Char 15: runtime error: signed integer overflow: 1247803472 * 2 cannot be represented in type ‘int’ (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:16:15

看來是int存不進去了，但這時候你不該嘗試long long，而是想更有效的計算方式。

優化思路

我們可以觀察到題目只要求能否被5整除，因此應該回到數學的角度來思考。記得餘式定理嗎？由

\[a \div b = c...d\]

可以得到

\[a = bc + d\]

我們的操作上，可以得到

\[x_i = 2x_{i-1} + nums[i] = 2(5c_{i-1} + d_{i-1}) + nums[i] = 10c_{i-1} + 2d_{i-1} + nums[i]\]

接著把$x_i$對5取餘數，會發現$10 \cdot c_{i-1}$對5取餘數為0，因此只需要考慮$d_{i-1} + nums[i]$，也就是

\[d_i = (2 \cdot d_{i-1} + nums[i]) \mod 5\]

最後，只要判斷$d_i$是否為0即可。

完整題解

Accepted
Runtime: 0ms Beats 100.00%
Memory: 18.37MB Beats 69.40%

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& nums) {
        vector<bool> v(nums.size());
        int n = 0;
        for(int i = 0; i < nums.size(); i++){
            n *= 2;
            n += nums[i];
            n %= 5;
            v[i] = n==0;
        }
        return v;
    }
};