leetcode 898. 子数组按位或操作 && 1521. 找到最接近目标值的函数值

题目链接 leetcode 898：https://leetcode-cn.com/problems/bitwise-ors-of-subarrays/

找到最接近目标值的函数值 https://leetcode-cn.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/

这两道题都是对于位运算的考察，分别是按位或 、按位与，拿按位或举例，如果对于一个数a，操作a = a | x 其中x可以为任意数，如果或上的x越多，那么a就越大。从二进制的角度去看，进行按位或运算，原来的二进制上的0可能变成1，但1不可能变成0，所以a就会变得越来越大

第二个点：对于任意一个小于1e9的数，你无论对他怎么按位或，他最后得到的结果最多只能有30多种，因为它二进制上的1是不会变得，而这个数的二进制最多只能有32位，所以考虑极限情况，最多也不会超过32种

第三个点：898这题让我这个野学党认识到map与unordered_map的区别。以前看过很多题解中出现unordered_map,当时就觉得应该和map差不多，其实不一样。map内部实现的是红黑树，而unordered_map内部实现的是哈希表，所以map的插入和查询的复杂度是O(lg N) (不是1！！我以前一直以为是1) 而unordered_map插入和查询是O(1)，如果你可以把898中的undered_map换成map就超时了。

//leetcode 898
const int maxn = 5e4+50;
class Solution {
public:
    vector<int> cnt[maxn];
    int subarrayBitwiseORs(vector<int>& A) {
        unordered_map<int,bool> M;
       int n = A.size();
       for(int i = 0; i <= n; i++) cnt[i].clear();

       for(int i = 1; i <= n; i++){
           cnt[i].push_back(A[i-1]);
           M[A[i-1]] = true;
           int last = A[i-1];
           for(int j = 0; j < cnt[i-1].size(); j++){
                int res = A[i-1] | cnt[i-1][j];
                if(res != last){
                    cnt[i].push_back(res);
                    M[res] = true;
                    last = res;
                }
           }
       }

        return M.size();
    }
};

//找到最接近目标值的函数值
const int maxn = 1e5+50;
class Solution {
public:
    vector<int> cnt[maxn];
    int closestToTarget(vector<int>& arr, int target) {
        int n = arr.size(),ans = 1e9;
        for(int i = 0; i < n; i++) cnt[i].clear();
        for(int i = 1; i <= n; i++){
            int now = i-1;
            cnt[i].push_back(arr[now]);
            int last = arr[now];
            ans = min(ans,abs(last-target));
            for(int j = 0; j < cnt[i-1].size(); j++){
                int res = cnt[i-1][j] & arr[now];
                if(res == last) continue;
                cnt[i].push_back(res);
                last = res;
                ans = min(ans,abs(res-target));
            }
        }
        return ans;
    }
};

总结：按位与：越与越小，按位或：越或越大。

unordered_map的查询插入才是1 ??

原文：https://www.cnblogs.com/Beic233/p/13361029.html