• 這一題是滿有趣的一題，我的靈感來自於 zkw 的線段樹(但沒有用到線段樹)。
  • 觀察 1 ~ n 的樹，並將它排成 zkw 的線段樹，可以發現以下規則：
    • 滿足樹的子葉，則必定可以滿足其父節點，例如：找到 "1010"，則可以滿足 "101"、"10"、"1"。
    • 所以可以得到一個數學結論是：我們只需要找到 n ~ n/2+1 的數即可。
                          [1]                           len = 1
              [10]                      11              len = 2
       100         [101]         110         111        len = 3
    1000  1001  [1010]  1011  1100  1101  1110  1111    len = 4
    (8)          num                            mask
     ^ 1<<3
  • solution:
class Solution {
public:
    bool queryString(string s, int n) {
        if (n > 1979) return false;            // 剪枝：當 n 太大時必為 false, 證明在下面
        int len = 32 - __builtin_clz(n);       // n 的位元長度
        if (s.size() < len) return false;      // s 長度連 window 都不夠時 return false
        int mask = (1 << len) - 1;             // 遮罩 用來控制 window 長度
        unordered_set<int> seen;               // 用來記錄數字是否出現過
        int valid = n - n/2;                   // 總共需要收集到的數目
        
        // init
        int curr = 0;
        for (int i = 0; i < len; i++) {
            curr = ((curr << 1) | (s[i] & 1));
            if (curr <= n && curr > n/2) seen.insert(curr);
            if (seen.size() == valid) return true;
        }
        
        // rolling
        for (int i = len; i < s.size(); i++) {
            curr = ((curr << 1) | (s[i] & 1)) & mask;
            if (curr <= n && curr > n/2) seen.insert(curr);
            if (seen.size() == valid) return true;
        }
        
        return false;
    }
};
  • 剪枝的證明： 我來說明 1979 這個臨界值的計算過程：

當字串長度 = 1000 時，我們需要找到滿足以下條件的最大 n：

  1. 對於任意數字 n：
需要的位元數(bits) = ⌊log₂(n)⌋ + 1
需要表示的數字數量 = ⌊n/2⌋ + 1   (從 n/2+1 到 n)
  1. 在字串中可用的位置數：
available_pos = L - bits + 1

其中 L 是字串長度(1000)

  1. 要滿足：
需要表示的數字數量 ≤ available_pos
⌊n/2⌋ + 1 ≤ L - (⌊log₂(n)⌋ + 1) + 1
n/2 + 1 ≤ 1000 - log₂(n)

用程式來找這個值：

def check(n):
    bits = n.bit_length()  # 等同於 ⌊log₂(n)⌋ + 1
    need_nums = n//2 + 1   # 需要表示的數字數量
    available = 1000 - bits + 1
    return need_nums <= available

# 二分搜尋找最大的 n
left, right = 1, 10000
while left + 1 < right:
    mid = (left + right) // 2
    if check(mid):
        left = mid
    else:
        right = mid

# left 就是答案 1979

驗證 1979：

n = 1979
bits = 11 (因為 1979 < 2048 = 2¹¹)
need_nums = 990 (從 990 到 1979)
available = 1000 - 11 + 1 = 990

驗證 1980：

n = 1980
bits = 11
need_nums = 991 (從 991 到 1980)
available = 1000 - 11 + 1 = 990
此時 need_nums > available，所以 1980 不行

這表示：

  1. 1979 是最大可能的 n
  2. 因為剛好需要 990 個位置來表示所有需要的數字
  3. 如果 n = 1980，則需要 991 個位置，但我們只有 990 個可用位置

所以 1979 就是這個精確的臨界值。