今天原本想到的標題是『一目十行就是指解一道題目你只需要寫十行！』但總覺得這標題有點碼天狗的感覺呢(XD)…好久沒看到碼天狗的技術週刊了說，不知道大家都去哪了QQ

Exercise 37: Leetcode 898 - Bitwise ORs of Subarrays

題目連結

https://leetcode.com/problems/bitwise-ors-of-subarrays/

題目敘述

給你一個陣列 A，對於連續的子序列，請問所有可能的 bitwise-OR 起來的值有幾種。

解題思考

這題的關鍵是注意到對於每一個位置，往前看的連續 bitwise-OR 值最多只有 32 種。因此我們可以維護「到目前為止，往前看能夠形成的 bitwise-OR 值」，更新的時候只要把集合內的東西 OR 看到的新的值就可以了！

參考程式碼 (Python3)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:            
        answers = set()
        current = {0}
        for x in A:
            current = {x} | {val | x for val in current}
            answers |= current
        return len(answers)

Exercise 38: Leetcode 940 - Distinct Subsequence II

題目連結

https://leetcode.com/problems/distinct-subsequences-ii/

題目敘述

給你一個小寫英文字母字串 S，請問 S 有多少個相異的子序列呢？請輸出答案除以 1e9+7 的餘數。

解題思考

我們想要把每一個相異的子序列「對應至字串 S 的某處」。要怎麼判斷一個字串是不是 S 的子序列呢？我們可以採用貪婪演算法(Greedy Algorithm)，依序找出下一個字元出現的地方，然後把它對應上去。這對於我們的子序列計數相當有幫助！

我們可以令 dp(i) 表示根據上述貪婪演算法的描述，剛好結束在 S[i] 位置的子序列數量。假設 S[i] = a，那麼此時結束在 S[i] 的子序列，可以是「結束在前一個 a 位置，然後多放一個 a」、或者是「在前一個 a 位置之後才結束匹配，然後多放一個 a」。因此假設 j* = max{j : j < i and S[j] = S[i]} 我們可以得到答案為 dp(i) = dp(j*) + dp(j*+1) + ... + dp(i-1)。

所以就得到一個 O(n^2) 的方法囉。

參考程式碼 (Python3)

class Solution:
    def distinctSubseqII(self, S: str) -> int:
        MOD = int(10**9+7)
        dp = [0] * len(S)
        prev = [None] * 26
        for i, c in enumerate(S):
            val = ord(c) - 97
            if prev[val] == None:
                dp[i] = 1
            pos = (prev[val] or 0)
            for j in range(pos, i):
                dp[i] = (dp[i] + dp[j]) % MOD
            prev[val] = i
        return sum(dp) % MOD

然後這個方法可以輕易地被延伸到 O(n) 時間的方法：畢竟是連續和，我們可以用另一個前綴和把他們記錄下來。程式碼就交給大家想想看囉！