LeetCode esay mid 记录

位运算（基础/性质/拆位/试填/恒等式/贪心/脑筋急转弯）

一、基础题

1486. 数组异或操作

感觉一般也用不到 emmm

灵茶山艾府传送门

推导过程可以结合官网部分观看
重点由两部分的结合

---

将特定部分转换为常见部分

---

    public static int xorOperation(int n, int start){
        int a = start / 2;
        int b = n & start & 1;  // 当n和start都为奇数时，b = 1
        return (xor(a + n - 1) ^ xor(a - 1) * 2 + 1);
    }

    // 计算从 0 到 n的异或和
    // 0 ^ 1 = 1 , ... ,  i ^ (i+1) = 1;
    // 令 n = 4k + (1,2,3,4)
    // n = 4k + 1时， (n+1)/2 = (4k+2)/2 = 2k+1，等于有奇数个 i ^ (i+1) = 1，所以等于 1
    // n = 4k + 2时,  单独拿出一个n，这样就简化为4k+1的情况，最后等于 n ^ 1，即 (4k+2)^1 = 4k+3 = n+1
    // n = 4k + 3时， (n+1)/2 = (4k+4)/2 = 2k+2，等于有偶数个 i ^ (i+1) = 1, 最后等于 1 ^ 1 = 0
    // n = 4k + 4时， 单独拿出一个n，这样就简化为4k+3的情况，最后等于 n ^ 0，即 n
//    public static int xor(int n){
//        return switch(n % 4){
//            case 0 -> n;
//            case 1 -> 1;
//            case 2 -> n + 1;
//            default -> 0;
//        };
//    }
    public static int xor(int n) {
        int result;
        switch (n % 4) {
            case 0:
                result = n;
                break;
            case 1:
                result = 1;
                break;
            case 2:
                result = n + 1;
                break;
            default:
                result = 0;
                break;
        }
        return result;
    }

0到n的异或和表示

---

2595. 奇偶位数

0x555是十六进制数，转换为二进制为 0101 0101 0101

class Solution {
    public int[] evenOddBit(int n) {
        int mask = 0x555;
        return new int[]{Integer.bitCount(n & mask), Integer.bitCount(n & (mask >> 1))};
    }
}

231. 2 的幂

如果 n = 2的幂，则 n & (n-1) 一定等于 0

class Solution {
    static final int BIG = 1 << 30;
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n-1)) == 0;
    }
}

342. 4的幂

在2的幂的基础上，加上n%3==1的特性

class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n-1)) == 0 && n % 3 == 1;
    }
}

476. 数字的补数

class Solution {
    public int findComplement(int num) {
        int res = 0;
        for(int i = 0 ; num > 0; i++){
            int temp = num % 2;
            temp = temp == 1? 0:1;
            res += temp * Math.pow(2, i);
            num >>= 1;
        }
        return res;
    }
}

191. 位1的个数

class Solution {
    public int hammingWeight(int n) {
         int res = 0;
         while(n != 0){
            n &= n-1;
            res++;
         }
         return res;
    }
}

338. 比特位计数

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for(int i = 0 ; i <= n; i++){
            res[i] = Integer.bitCount(i);
        }
        return res;
    }
}

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

自定义排序

    public int[] sortByBits(int[] arr) {
        // 初始化
        // 0 <= arr[i] <= 10^4
        int[] bits = new int[10001];
        ArrayList<Integer> counts = new ArrayList<>();
        for(int i = 0 ; i < arr.length; i++){
            counts.add(arr[i]);
            bits[arr[i]] = Integer.bitCount(arr[i]);

        }

        counts.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if(bits[o1] != bits[o2]){
                    return bits[o1] - bits[o2];
                }else{
                    return o1 - o2;
                }
            }
        });
        int[] res = new int[arr.length];
        for(int i = 0; i < res.length; i++){
            res[i] = counts.get(i);
        }
        return res;


    }

461. 汉明距离

    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }

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

    class Solution {
        public int minBitFlips(int start, int goal) {
            return Integer.bitCount(start ^ goal);
        }
    }

693. 交替位二进制数

    public boolean hasAlternatingBits(int n) {
        int a = n ^ (n >> 1);
        return (a & (a + 1)) == 0;
    }

二、与或（AND/OR）的性质

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

    public boolean hasTrailingZeros(int[] nums) {
        int even = nums.length;
        for (int x : nums) {
            even -= x % 2;
        }
        return even >= 2;
    }

2401. 最长优雅子数组

// 相当于退队
 while ((or & nums[right]) > 0) // 有交集
     or ^= nums[left++]; // 从 or 中去掉集合 nums[left]

// 相当于入队
or |= nums[right]; // 把集合 nums[right] 并入 or 中

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;
    }
}