Re: [閒聊] 每日leetcode

[sixB (6B)]

※ 引述《sixB (6B)》之銘言：
: 2044. or找最大 然後 conut
: ##ㄙ路

報搜好快可是不太能接受==

看一看發現拿東西感覺很背包

改dp

class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        // find max
        unordered_map<int, int> or_val_cnt;
        // <or_val, cnt>
        or_val_cnt[0] = 1;

        int maxi = 0;
        for(int i: nums){
            maxi |= i;
            unordered_map<int, int> new_cnt = or_val_cnt;
            for(auto [val, cnt]: new_cnt){
                or_val_cnt[ val | i ] += cnt;
            }
        }
        return or_val_cnt[maxi];
    }

};

用int arr比hashmap慢好多

因為num range很寬 可是len很小

剛剛看到一個佐助的solution用bitmask

太潮惹==

--
很姆的咪

姆之咪

http://i.imgur.com/5sw7QOj.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729218270.A.E62.html
推 Sougou: 為啥說是佐助
→ sixB: 他的頭貼是撒ㄙ給
→ sixB: https://leetcode.com/problems/count-number-of-maximum-bi
→ sixB: twise-or-subsets/solutions/1525216/c-bitmask-dp
→ sixB: 看完還是覺得太tricky惹== bitwise好難