Re: [閒聊] 每日leetcode
題目:
找出有幾個不同的subarray裡面的值or出來的值
思路:
記錄之後下一個會出現的所有bit的位子
在每一個數字檢查的時候
都只要檢查下一次會出現哪些bit
然後or起來就好
因為是int進行or的關係
只要檢查32個就好
這大概是N log32吧
這題我思路好像蠻酷的
給你們看一下
```cpp
class Solution {
public:
int subarrayBitwiseORs(vector<int>& arr)
{
int n = arr.size();
vector<deque<int>> save(32,deque<int>());
unordered_set<int> savenum;
for(int i = 0 ; i < n ; i ++)
{
for(int b = 0 ; b < 32 ; b ++)
{
if((arr[i] >> b) & 1)save[b].push_back(i);
}
}
for(int i = 0 ; i < n ; i ++)
{
for(int b = 0 ; b < 32 ; b ++)
{
if(!save[b].empty() && save[b].front() <= i)
{
save[b].pop_front();
}
}
// idx pow
vector<pair<int,int>> now;
for(int b = 0 ; b < 32 ; b ++)
{
if(arr[i] >> b & 1)continue;
if(!save[b].empty())
{
now.push_back({save[b].front(),b});
}
}
sort(now.begin() , now.end());
if(savenum.find(arr[i]) == savenum.end())savenum.insert(arr[i]);
int cur = arr[i];
int nn = now.size();
int idxnow = i;
for(int j = 0 ; j < nn ; j ++)
{
idxnow = now[j].first;
while(j < nn && idxnow == now[j].first)
{
cur |= 1 << now[j].second ;
j++;
}
j--;
if(savenum.find(cur) == savenum.end())savenum.insert(cur);
}
}
// for(int k : savenum)cout << k << " ";
return savenum.size();
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 211.23.178.106 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1753981374.A.211.html
※ 編輯: oin1104 (211.23.178.106 臺灣), 08/01/2025 01:04:12
→
08/01 01:08,
4月前
, 1F
08/01 01:08, 1F
→
08/01 01:08,
4月前
, 2F
08/01 01:08, 2F
→
08/01 01:08,
4月前
, 3F
08/01 01:08, 3F
→
08/01 01:08,
4月前
, 4F
08/01 01:08, 4F
→
08/01 01:09,
4月前
, 5F
08/01 01:09, 5F
→
08/01 01:09,
4月前
, 6F
08/01 01:09, 6F
討論串 (同標題文章)
完整討論串 (本文為第 1487 之 1548 篇)：