LeetCode第452场周赛复盘

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

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

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