date: 2025-06-01
tags:

• LeetCode
• 算法

第一题

3566. 等积子集的划分方案

我的通过解法

public class Solution {  
    boolean ans = false;  
    boolean[] visited;  

    public boolean checkEqualPartitions(int[] nums, long target) {  
        long sum = 1;  
        visited = new boolean[nums.length];  

        for (int num : nums) {  
            sum *= num;  
        }  

        if (nums.length == 1) return false;  
        if (sum != target * target || sum == target) return false;  

        dfs(nums, target, 0, 1, 0);  
        return ans;  
    }  

    void dfs(int[] nums, long target, int index, long res, int count) {  
        if (ans) return;  

        if (res == target) {  
            if (count == nums.length) return;  

            long sum2 = 1;  
            for (int i = 0; i < nums.length; i++) {  
                if (!visited[i]) {  
                    sum2 *= nums[i];  
                }  
            }  

            if (sum2 == target) {  
                ans = true;  
            }  
            return;  
        }  

        for (int i = index; i < nums.length; i++) {  
            visited[i] = true;  
            dfs(nums, target, i + 1, res * nums[i], count + 1);  
            visited[i] = false;  
        }  
    }  
}

用到了全局变量，但其实这样并不好，因为可能引发锁🔒的问题
尤其是我最先开始还将res进行全局，这样在频繁操作是就更容易出问题了

赛后看了灵神的二进制枚举的方法，故进行学习

class Solution {
    public boolean checkEqualPartitions(int[] nums, long target) {
        int n = nums.length;
        int u = (1 << n) - 1;
        for (int s = 1; s < u; s++) { // 枚举 u 的非空真子集 s
            long mul1 = 1, mul2 = 1;
            for (int i = 0; i < n && mul1 <= target && mul2 <= target; i++) {
                if ((s >> i & 1) > 0) { // i 在集合 s 中
                    mul1 *= nums[i];
                } else { // i 在补集中
                    mul2 *= nums[i];
                }
            }
            if (mul1 == target && mul2 == target) {
                return true;
            }
        }
        return false;
    }
}

^二进制枚举算法 ^93f48b

根据灵神的链接来到了这里分享｜从集合论到位运算，常见位运算技巧分类总结！

常见的位运算

• 代码示例

public static void main(String[] args) {  
    //6==0110  
    int a = 6;  
    //3==0011  
    int b = 3;  

    //& 按位与 对应位都为1时才为1  
    //输出2==0010  
    System.out.println(a & b);  

    //| 按位或 只要其中一位是 1，结果就是 1    //输出7==0111  
    System.out.println(a | b);  

    //^ 按位异或 不同为1，相同为0  
    //输出5==0101  
    System.out.println(a ^ b);  

    //~ 按位取反，0变1，1变0  
    //输出-7  
    /*    详细解释一下这个  
    6 的二进制（原码）:  00000000 00000000 00000000 00000110  
    ~6 :  11111111 11111111 11111111 11111001 负数  
    取反码 00000000 00000000 00000000 00000110    
    +1 00000000 00000000 00000000 00000111 结果为7  
    加 - 号  
     */    
    System.out.println(~a);  

    //<< 左移 所有位向左移动 n 位，右边补 0    6 << 1 = 12（1100）  
    //不溢出的情况下  a << n 相当于 a * 2ⁿ    System.out.println(a<<1);  

    //>> 右移 所有位向右移动 n 位，保留符号位   6 >> 1 = 3（011）  
    System.out.println(a>>1);  

    //>>> 无符号右移 所有位右移 n 位，左边补 0   -1 >>> 1（补 0）  

}

• >> 和 >>> 的区别

十进制： -8
二进制（补码）：11111111 11111111 11111111 11111000


//>>
原始：11111111 11111111 11111111 11111000
右移：11111111 11111111 11111111 11111110（还是负数）
十进制：-2


//>>>
原始：11111111 11111111 11111111 11111000
右移：00111111 11111111 11111111 11111110（变成了正数！）
十进制：1073741822

• 常用技巧

public class BitwiseOperations {

    public static void main(String[] args) {
        int x = 6, a = 5, b = 3;

        // 1. 判断奇偶数
        if ((x & 1) == 0) {
            System.out.println(x + " 是偶数");
        } else {
            System.out.println(x + " 是奇数");
        }

        // 2. 快速乘以或除以 2 的幂
        System.out.println("x << 1 = " + (x << 1)); // x * 2
        System.out.println("x >> 1 = " + (x >> 1)); // x / 2（向下取整）

        // 3. 交换两个数（不使用临时变量）
        System.out.println("交换前: a = " + a + ", b = " + b);
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println("交换后: a = " + a + ", b = " + b);

        // 4. 清除最低位的 1
        int y = 6; // 110
        System.out.println("x & (x - 1) = " + (y & (y - 1))); // 100 = 4

        // 5. 取出最低位的 1
        System.out.println("x & -x = " + (x & -x)); // 010 = 2

        // 6. 判断第 k 位是否为 1
        int k = 1;
        System.out.println("第 " + k + " 位是否为 1: " + (((x >> k) & 1) == 1));

        // 7. 设置第 k 位为 1
        System.out.println("设置第 " + k + " 位为 1: " + (x | (1 << k)));

        // 8. 清除第 k 位（设为 0）
        System.out.println("清除第 " + k + " 位: " + (x & ~(1 << k)));

        // 9. 取反第 k 位（0变1，1变0）
        System.out.println("取反第 " + k + " 位: " + (x ^ (1 << k)));
    }
}