之前有个《位运算trick》的文章，也是讲位运算的。不过最近灵神发了个位运算的题单。这篇就按题单来了。
一、基础题
二、&/|
1. LC 2980 检查按位或是否存在尾随零
查是否能有至少两个偶数即可。
class Solution {
public boolean hasTrailingZeros(int[] nums) {
int cnt = 0;
for (int num : nums) {
if(num%2==0){
cnt++;
if(cnt==2){
return true;
}
}
}
return false;
}
}
2. LC 1318 或运算的最小翻转次数
这题就给了1383分，但我写得巨抽象。
开了俩哈希表记录每个位置上的1的出现次数，如果a|b和c的对应哈希表中某个位置上的1的个数有且仅有一个为0，那么就查谁是0，a|b的是0那就改一次变成1就行；否则得改cnt1[i]次变成0。
class Solution {
public int minFlips(int a, int b, int c) {
int[] cnt1 = new int[32];
int[] cnt2 = new int[32];
updateCnt(a,cnt1);
updateCnt(b,cnt1);
updateCnt(c,cnt2);
int ans = 0;
for (int i = 0; i < 32; i++) {
if((cnt1[i]*cnt2[i]==0)&&(cnt1[i]+cnt2[i]!=0)){
if(cnt1[i]==0){
ans++;
}else{
ans+=cnt1[i];
}
}
}
return ans;
}
private void updateCnt(int num, int[] cnt){
int i = 0;
while(num>0){
cnt[i++]+=(num&1);
num>>>=1;
}
}
}
看着写了一坨代码，实际上是32*4=128次常数次操作。O(1)的。
3. LC 2419 按位与最大的最长子数组
毁了，这题乱套公式常数时间垫底把自己道心干碎了。
总体来说&和|这俩都是越操作越xx的，比如&就是大，|就是小。所以照旧维护出现过的&值，并维护最小的左边界。遇到更大的&值就更新最大值和长度，遇到相同的就更新长度。
class Solution {
public int longestSubarray(int[] nums) {
int[][] and = new int[32][2];
int len = 0;
int max = 0;
int ans = 1;
for (int i = 0; i < nums.length; i++) {
and[len][0] = Integer.MAX_VALUE;
and[len++][1] = i;
int j = 0;
for (int k = 0; k < len; k++) {
and[k][0] &= nums[i];
if(and[j][0]!=and[k][0]){
and[++j][0] = and[k][0];
and[j][1] = and[k][1];
}else{
and[j][1] = Math.min(and[j][1],and[k][1]);
}
if(max==and[j][0]){
ans = Math.max(ans,i-and[j][1]+1);
}else if(max<and[j][0]){
max = and[j][0];
ans = 1;
}
}
len = j+1;
}
return ans;
}
}
但其实都看到越&越小的性质了，这个问题就变成了找最大值的连续串的最大长度的问题了。
class Solution {
public int longestSubarray(int[] nums) {
int max = 0;
int ans = 0;
int len = 0;
for (int num : nums) {
if(num>max){
max = num;
len = ans = 1;
}else if(num==max){
len++;
ans = Math.max(ans,len);
}else{
len = 0;
}
}
return ans;
}
}
其实复杂度都是O(n)，但后者常数好。
4. LC 2871 将数组分割成最多数目的子数组
先来说一个我的比较朴素的思路：
因为越&越小，所以我们先看一下整个数组&完的那个值是多少。假设&完为target，那么如果target不为0，说明答案肯定是1。因为这代表了任何一个子数组的分数不为0，所以但凡分割成超过一个子数组，那分数和一定到不了最小。
如果为0，就可以分组循环尝试把位与的值降到≤target。可能会担心说前面的都能降到≤target，后面的降不到怎么办？很简单，合并到前面的就可以了。
class Solution {
public int maxSubarrays(int[] nums) {
int target = Integer.MAX_VALUE;
for (int num : nums) {
target &= num;
}
if(target!=0){
return 1;
}
int i = 0;
int n = nums.length;
int ans = 0;
while(i<n){
int tmp = Integer.MAX_VALUE;
while(i<n&&tmp>target){
tmp &= nums[i];
i++;
}
ans++;
if(i==n&&tmp>target){
ans--;
}
}
return ans;
}
}
然后就有个优化的写法。你不是位与等于0才能下一段分组吗？我上来直接对全1串位与，如果遇到0给答案增一，不是0就直接一直往下跑，到最后返回答案就行，如果整个数组位与完都不是0，那么就返回1。
class Solution {
public int maxSubarrays(int[] nums) {
int a = -1;
int ans = 0;
for (int num : nums) {
a &= num;
if (a == 0) {
ans++;
a = -1;
}
}
return Math.max(ans, 1);
}
}
这里利用-1的补码是全1串，所以令a=-1。
这俩方法复杂度都是O(n)，但是后面的常数时间好。前面的思路更加清晰。
5. LC 2401 最长优雅子数组
这题我的想法一开始是分组循环。这里对任意两个元素位与为0的优化是利用一个bitmap来存储各个位是否是1，这样新来的数是否和之前的任意一个数位与不为0等价于他和这个bitmap位与不为0。但是这个和分组循环不同的是，你nums[i:j]是一个组的话，不代表nums[i+1:j+x]不是一个合法的组。所以外层循环的时候要把i=j改成i++。
class Solution {
public int longestNiceSubarray(int[] nums) {
int ans = 1;
int i = 0;
int n = nums.length;
while(i<n){
int j = i+1;
int bitmap = nums[i];
while(j<n){
if((bitmap&nums[j])!=0){
break;
}else{
bitmap |= nums[j];
}
j++;
}
ans = Math.max(j-i,ans);
i++;
}
return ans;
}
}
这样最坏其实是O(n²)的，按1e5基本上是T了，但不知道这题为啥没卡。
比较好的写法是，不定长的滑动窗口，维护一个左边界一个右边界，如果bitmap和新来的位与不为0就增加左边界。然后增加右边界，这样滑窗就行。
可能会担心一个位上有多个数的1，这不用担心，因为每次我们都是确保了和新来的位与不为0才把新来的|到bitmap的，所以不可能有多个重复的1。
class Solution {
public int longestNiceSubarray(int[] nums) {
int ans = 0;
for (int left = 0, right = 0, or = 0; right < nums.length; right++) {
while ((or & nums[right]) > 0) // 有交集
or ^= nums[left++]; // 从 or 中去掉集合 nums[left]
or |= nums[right]; // 把集合 nums[right] 并入 or 中
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
6. LC 2680 最大或值
这个是个贪心，但也不太明显。把左移机会全给一个数才有可能达到或值最大。这样维护前后缀或值然后枚举左移k次的数就可以。
class Solution {
public long maximumOr(int[] nums, int k) {
int n = nums.length;
if(n==1){
return ((long)nums[0])<<k;
}
long[] prefix = new long[n];
long[] suffix = new long[n];
prefix[0] = nums[0];
suffix[n-1] = nums[n-1];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i-1]|nums[i];
}
for (int i = n-2; i >= 0; i--) {
suffix[i] = suffix[i+1]|nums[i];
}
long ans = Math.max(((long)nums[0]<<k)|suffix[1],((long)nums[n-1]<<k)|prefix[n-2]);
for (int i = 1; i < n-1; i++) {
ans = Math.max(ans, ((long) nums[i] <<k)|prefix[i-1]|suffix[i+1]);
}
return ans;
}
}
假设存在序列I={i1,i2,i3,…,in}，其中∑I=k，且ip≥0(1≤p≤n)。那么把k分散到这n个数上，一定比不上对n个数中最大的左移k次或完的值要大，因为从0-1串的长度上来说已经输了。
这题有人用DP做的，他定义f[i][j]表示nums[0:i]个数用掉j次左移能得到的最大值。那么f[n-1][k]就是答案，状态转移方程为：
import static java.lang.Math.max;
class Solution {
public long maximumOr(int[] nums, int k) {
int n = nums.length;
if(n==1){
return ((long)nums[0])<<k;
}
long[][] f = new long[n][k + 1];
for (int i = 0; i <= k; i++) {
f[0][i] = ((long) nums[0]) << i;
}
// 状态转移方程
for (int i = 1; i < n; i++) {
for (int j = 0; j <= k; j++) {
for (int z = 0; z <= j; z++) {
f[i][j] = max(f[i][j], f[i - 1][z] | (((long) nums[i]) << (j - z)));
}
}
}
return f[n-1][k];
}
}
这个做法假了。例如：
[10,8,4]
按他的做法来说，前两个数用掉0次左移可以最大得到10，用掉1次左移可以最大得到28（20|8），但是实际上的最大是（10|16|4），而不是（20|8|4）。这个状态转移是错的。基于当前的最大不一定能得到下一次的最大。
7. LC 2411 按位或最大的最小子数组长度
跟LC 3097差不多。不过我这个选择的是倒着遍历的。因为他要求最大么，正着遍历的话不知道后面是否会出现更大的，但是倒着遍历就把后面元素全记录了，这样就是O(n)了。
大致思路如下：
- 倒着遍历元素，记录每一个或值及能够达成这个或值的最小右边界
- 把当前元素和记录的或值全部或起来，原地去重
- 或的同时记录最大值，查询这个最大值对应的右边界r，r-i+1即为ans[i]
class Solution {
public int[] smallestSubarrays(int[] nums) {
int n = nums.length;
int[][] ors = new int[32][2];
int m = 0;
int[] ans = new int[n];
for (int i = n-1; i >= 0; i--) {
ors[m][0] = 0;
ors[m++][1] = i;
int j = 0;
int max = 0;
for (int k = 0; k < m; k++) {
ors[k][0] |= nums[i];
if(ors[k][0]!=ors[j][0]){
ors[++j][0] = ors[k][0];
}
ors[j][1] = ors[k][1];
if(ors[max][0]<ors[j][0]){
max = j;
}
}
m = j+1;
ans[i] = ors[max][1]-i+1;
}
return ans;
}
}
但这题还有个做法，就是正着遍历的过程中倒着遍历。可以这么想，如果正着遍历到一个新元素，导致之前以某个位置开始的或值变得更大，就可以更新这个位置的长度。如果不会造成更大，那么更之前的也不会更大（因为卡在了当前这里），再之前的也统统不用更新。
class Solution {
public int[] smallestSubarrays(int[] nums) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
ans[i] = 1;
for (int j = i - 1; j >= 0 && (nums[j] | nums[i]) != nums[j]; j--) {
nums[j] |= nums[i];
ans[j] = i - j + 1;
}
}
return ans;
}
}
