📘 題目敘述
你會拿到一個大小為 m x n 的 2D 整數陣列
grid。你必須每一列剛好選出一個整數，回傳全部選值做
bitwise OR 後的最小可能值。
條件限制
1 <= m == grid.length <= 10^51 <= n == grid[i].length <= 10^5m * n <= 10^51 <= grid[i][j] <= 10^5
🧠 解題思路
我把「處理到第 i 列的所有可能 OR 值」存成集合。初始為
{0}，每加入一列就把上一輪集合中的每個值，和本列每個數做
OR，形成新集合。最後集合裡的最小值就是答案。
所有變數
s：目前所有可能 OR 結果集合ns：下一列的新集合ans：最終最小 OR 值
🪜 主要流程步驟
1. 初始化
s = {0}。
2. 逐列做狀態轉移
枚舉 s 與當列所有數，將 x | y 放進
ns，再令 s = ns。
3. 取最小值
掃過最後的 s 取最小值。
⏱️ 複雜度
- 時間複雜度：概念上
O(m * n * U) - 空間複雜度：
O(U)
💻 程式碼實作
class Solution {
public:
int minimumOR(vector<vector<int>>& grid) {
unordered_set<int> s;
s.insert(0);
for (auto& a : grid) {
unordered_set<int> ns;
for (int x : s) {
for (int y : a) {
ns.insert(x | y);
}
}
s = ns;
}
int ans = INT_MAX;
for (int z : s) {
ans = min(ans, z);
}
return ans;
}
};