Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

題目:
找出有幾個不同的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
→ SydLrio: 屁眼
→ oin1104: 屁眼
→ SydLrio: 芋圓可愛
→ oin1104: 屁眼
→ SydLrio: 芋圓晚安
→ oin1104: 晚安