Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

※ 引述 《Rushia (早瀬ユウカの体操服)》 之銘言：
: 　
: https://leetcode.com/problems/longest-nice-subarray
: 2401. Longest Nice Subarray
: 給你一個陣列nums，如果他的子陣列的任意兩個元素and後為0則他是一個nice陣列，求出
: 最長的nice陣列有多長(長度為1的陣列總是nice)。
: 　
: 思路:
: 雙指針，如果當前加入的元素跟之前加入的bit位置都沒重複就可以加入長度加一，否則
: 一直pop前面的數字(用xor刪掉前面加過的元素)，返回最長長度即可。
: 　


思路:
之前每日有一個類似的題目
好像是找abc不重複的字串
那題就是要看上一個目標字母最後出現的地方

如果用這種思路的話
就是看上一個bit出現的地方
但是有兩種可能
一種是這個bit是0
那就可以找上上個bit的下一個
一種是這個bit是1
那就是找上個bit的下一個

這樣複雜度應該一樣是n
但是是32n

0.0

```cpp
class Solution {
public:
    int longestNiceSubarray(vector<int>& nums)
    {
        int n = nums.size();
        vector<bitset<32>> paper(n);
        vector<vector<int>> last_bit(32);
        int res = 0;

        for(int i = 0 ; i < n ; i ++)
        {
            int num = nums[i];
            int last = 0;

            for(int b = 0 ; b < 31 ; b ++)
            {
                int bit = pow(2,b);
                if(num & bit)
                {
                    if(last_bit[b].size() > 0)last = max(last_bit[b].back()+1 ,
last);

                    last_bit[b].push_back(i);
                    // cout << 1 << "";
                }
                else
                {
                    if(last_bit[b].size() > 1)last = max(last_bit[b][last_bit[b]
.size()-2]+1 , last);
                    // cout << 0 << "";
                }
            }
            // cout << endl;
            // cout << i << " " << last << endl;
            res = max(res , i-last+1);
        }

        return res;
    }
};
```



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.246.154 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1742314612.A.F90.html
→ PogChampLUL: 大師
→ Rushia: 大師