位运算题单

基础题

img

1486. 数组异或操作

直接模拟（）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution 
{
public:
    int xorOperation(int n, int start) 
    {
        int ans = 0;
        for (int i = 0; i < n; ++i) 
        {
            ans ^= (start + i * 2);
        }
        return ans;
    }
};

2595. 奇偶位数

水题啊

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> evenOddBit(int n) 
    {
        vector<int> ans(2);
        for (int i = 0; n != 0; i ^= 1, n >>= 1)
            ans[i] += n & 1;
        return ans;
    }
};

231. 2 的幂

小技巧

1
2
3
4
5
6
7
8
class Solution 
{
public:
    bool isPowerOfTwo(int n) 
    {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

342. 4的幂

可以通过 n 除以 3 的余数是否为 1 来判断 n 是否是 4 的幂。

1
2
3
4
5
6
7
8
class Solution {
public:
    bool isPowerOfFour(int n)
    {
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
};

476. 数字的补数

位运算大法好

1
2
3
4
5
6
7
8
9
10
11
12
class Solution 
{
	public int findComplement(int num) 
    {
		int res = 1;
		while (res < num) {
			res = res << 1;
			res++;
		}
		return num ^ res;
	}
}

191. 位1的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
        int ret = 0;
        for (int i = 0; i < 32; i++) 
        {
            if (n & (1 << i)) 
            {
                ret++;
            }
        }
        return ret;
    }
};

338. 比特位计数

显然扫一遍每次log，就是nlogn，但这显然不是正解

考虑dp，转移的话由他的前面一位转移过来

nlogn

n & n-1 的值是 去掉二进制n最右边1的值；

比如 1010 & 1001 = 1000；用这个可以非常优雅的计算一个数里面的1的个数！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }

    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        for (int i = 0; i <= n; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    }
};

n

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution 
{
public:
    vector<int> countBits(int n) 
    {
        vector<int> res(n+1); 
        for (int i = 1; i <= n; ++i) {
           
            res[i] = res[i >> 1] + (i & 1);
        }
        return res; 
    }
};

1356. 根据数字二进制下 1 的数目排序

只要你会了上一题的O(n)做法，本题简直是探囊取物

本题题解写的有些冗余，改了一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution 
{
public:
    vector<int> sortByBits(vector<int>& arr) 
    {
        vector<int> bit(10001, 0);
        for (int i = 1; i <= 10000; ++i) 
        {
            bit[i] = bit[i >> 1] + (i & 1);
        }
        sort(arr.begin(), arr.end(), [&](int x, int y)
             {
            if (bit[x] == bit[y]) 
            {
            return x < y;
            }
         return (bit[x] < bit[y]) ;

        });
        return arr;
    }
};

461. 汉明距离

由于上述结论，异或求1即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution 
{
public:
    int hammingDistance(int x, int y) 
    {
        int ret = x^y;      
        int ans = 0;        
        while(ret)
        {        
            ret&=(ret-1);  
            ans++;
        }
        return ans;
    }
};

2220. 转换数字的最少位翻转次数

与上面一道题一致

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution 
{
public:
    int minBitFlips(int start, int goal) 
    {
        int res = 0;
        int tmp = start ^ goal;
        while (tmp) 
        {
            res += tmp & 1;
            tmp >>= 1;
        }
        return res;
    }
};

868. 二进制间距

一眼题了，只需要记录上一个即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution 
{
public:
    int binaryGap(int n) 
    {
        int last = -1, ans = 0;
        for (int i = 0; n; ++i) 
        {
            if (n & 1) {
                if (last != -1) 
                {
                    ans = max(ans, i - last);
                }
                last = i;
            }
            n >>= 1;
        }
        return ans;
    }
};

2917. 找出数组中的 K-or 值

模拟一下基本的判1操作即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution 
{
public:
    int findKOr(vector<int>& a, int k) 
    {
        int n=a.size(),ans=0,x;
        vector<int> s(35);
        for(int i=0;i<n;i++)
        {
            x=a[i];
            for(int j=0;j<31;j++)
                if(x&(1<<j)) s[j]++;
        }
        for(int j=0;j<31;j++)
            if(s[j]>=k) ans+=(1<<j);
        return ans;
    }
};

今天的最后一题：

693. 交替位二进制数

直接模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution 
{
public:
    bool hasAlternatingBits(int n) 
    {
        int prev = 2;
        while (n != 0) {
            int cur = n % 2;
            if (cur == prev) 
            {
                return false;
            }
            prev = cur;
            n /= 2;
        }
        return true;
    }
};

位运算力扣基础题单中阶

2980. 检查按位或是否存在尾随零

判断两个偶数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool hasTrailingZeros(vector<int>& nums) {
        int num = 0;
        for(auto i : nums){
            if(i % 2 == 0){
                num++;
                if(num >= 2){
                    return true;
                }
            }
        }
        return false;
    }
};

1318. 或运算的最小翻转次数

很水的题目，分类讨论一下即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minFlips(int a, int b, int c) {
        int ans = 0;
        for (int i = 0; i < 31; ++i) {
            int bit_a = (a >> i) & 1;
            int bit_b = (b >> i) & 1;
            int bit_c = (c >> i) & 1;
            if (bit_c == 0) {
                ans += bit_a + bit_b;
            }
            else {
                ans += (bit_a + bit_b == 0);
            }
        }
        return ans;
    }
};

2419. 按位与最大的最长子数组

思路太直接了，找到最大值，算最大子个数，用个最长连续就写完了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution 
{
public:
    int longestSubarray(vector<int>& nums) 
    {
        int n = nums.size();
        // 求数组中的最大值
        int mx = 0;
        for (int x : nums) mx = max(mx, x);
        int ans = 1, cnt = 0;
        for (int x : nums) {
            if (x == mx) cnt++;
            else ans = max(ans, cnt), cnt = 0;
        }
        ans = max(ans, cnt);
        return ans;
    }
};

2871. 将数组分割成最多数目的子数组

也是脑经急转弯的题目，其实也是不难的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
  int maxSubarrays(vector<int>& nums) {
      int mask = nums[0];
      for(int x : nums) 
          mask &= x;
      if(mask != 0) 
          return 1;
      int cnt = 0;
      int cur = nums[0];
      for(int i = 0; i < nums.size();)
      {
          cur &= nums[i];
          if(cur == mask)
          {
              cnt++;
              if(i == nums.size() - 1) break;
              else cur = nums[i + 1];
          }
          i++;
      }
      return cnt;
  }
};

2401. 最长优雅子数组

此题比较有难度，需要结合滑动窗口，也就是双指针的思想，具体一个数进来需要或起来，因为如果不或是没办法知道这个位有没有数字出现过的，至于怎么样左滑移出去，这个操作就是异或了，由于已经保证了数字之前的位数的不重复性，因此只需要异或就可以达到一个弹出的作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution 
{
public:
    int longestNiceSubarray(vector<int>& nums) 
    {
        int n = nums.size();
        int i = 0;
        if (n == 1) return 1;
        int j = i + 1;
        int ans = 1;
        long long now = nums[i];
        while (i < n && j < n) {
            while ((i < j) && ((now & nums[j]) != 0)) 
            { 
                now ^= nums[i]; 
                ++i;
            }
            now |= nums[j]; 
            ans = max(ans, j - i + 1); 
            ++j;
        }
        return ans;
    }
};

3097. 或值至少为 K 的最短子数组 II

也是滑动窗口不过是哈希加上滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution 
{
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        if(k == 0) return 1;
        int ans = INT32_MAX, n = nums.size(), cur = 0;
        vector<int> mem(32);// 用于累计窗口中各数位有多少个1
        int l = 0, r = 0;
        while(l <= r && r < n)
        {
            // 移动右指针增大窗口
            for(int j = 0; j < 32; ++j){
                if((nums[r] >> j) & 1)
                {
                    ++mem[j];
                    if(((cur >> j) & 1) == 0)// 只有原来没有置1时才置1，注意不要重复累加
                        cur += (1 << j);
                }
            }
            ++r;
            // 在窗口和 >= k时，移动左指针到 窗口和 < k，或者
            // 右指针已经移动到最右端时，移动左指针到最右端
            while((cur >= k || r == n) && l < r)
            {
                if(cur >= k) ans = min(ans, r - l);
                for(int j = 0; j < 32; ++j)
                {
                    if((nums[l] >> j) & 1)
                    {
                        --mem[j];
                        if(mem[j] == 0) cur -= (1 << j);
                    }
                }
                ++l;
            }
        }
        return ans == INT32_MAX ? -1 : ans;
    }
};

3133. 数组最后一个元素的最小值

从低到高开始填充数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using ll=long long;
class Solution 
{
public:
long long minEnd(int n, int x) {
    	int i,j;
        ll res=x;
        n--;
        for(i=0,j=0;i<=30;i++,j++)
        {
        	while((res>>j)&1) 
                j++;
        	if(!((n>>i)&1)) 
                continue;
        	res|=(1LL<<j);
		}
        return res;
    }
};
//应该是直接往没有1的数字里面填就可以了
//但是有多少个数字要填就又是一个问题了

2680. 最大或值

找最高位的1去异或，而且只选择一个数字，因此只需要处理一下后缀和，前缀和直接计算进行预处理即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution 
{
public:
    long long maximumOr(vector<int> &nums, int k) 
    {
        int n = nums.size(), suf[n + 1];
        suf[n] = 0;
        for (int i = n - 1; i; i--)
            suf[i] = suf[i + 1] | nums[i];
        long long ans = 0;
        for (int i = 0, pre = 0; i < n; i++) 
        {
            ans = max(ans, pre | ((long long) nums[i] << k) | suf[i + 1]);
            pre |= nums[i];
        }
        return ans;
    }
};

2411. 按位或最大的最小子数组长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//求最远的1
class Solution 
{
    public int[] smallestSubarrays(int[] nums) 
    {
        int n = nums.length;
        int[] dp = new int[32];
        Arrays.fill(dp, -1);
        int[] ans = new int[n];
        for (int i = n-1; i >= 0; i--) 
        {
            int max = 1;
            for (int j = 0; j < 32; j++) 
            {
                if (((nums[i] >> j) & 1) == 1) 
                {
                    dp[j] = i;
                }
                if (dp[j] != -1) 
                {
                    max = Math.max(max, dp[j]-i+1);
                }
            }
            ans[i] = max;
        }
        return ans;
    }
}