算法奇妙屋(一)-位运算

景画

发布于 2025-12-19 12:39:44

一. 力扣268.丢失的数字

1. 题目

2. 算法原理

1.方法一: 因为每次都缺失一个数字, 每个数字都不同, 可以使用位运算来异或缺少数字的数组和完成的数组, 相同抵消为0, 这样就完成了消消乐操作, 相当于找单身数字, 最后就能找到确实的那个数字 2.方法二: 高斯求和: 根据高斯求和公式, (首项+尾项)*项数/2, 再减去nums数组的和

3. 代码

(1) 异或位运算

    public int missingNumber(int[] nums) {
        int tmp = 0;
        for (int x : nums) {
            tmp ^= x;
        }
        for(int i = 0; i <= nums.length; i++) {
            tmp ^= i;
        }
        return tmp;
    }

(2) 高斯求和

    public int missingNumber(int[] nums) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        int sum2 = (0 + nums.length) * (nums.length + 1) / 2;
        return sum2 - sum;
    }

二. 力扣260.只出现一次的数字 III

1. 题目

2. 算法原理

1.先全部异或得到数字 num, 得到的该数字然后计算二进制第一个 1 的位置 x, 得到该x是为了确定这两个单身数字二进制的第一个不同位置, 然后按照该位置二进制不同值来分组, 为 0 一组, 为 1 的一组, 这两个不同数字肯定在不同组, 最后分别异或两组, 即可求出这两个单身数字

3. 代码

    public int[] singleNumber(int[] nums) {
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            num ^= nums[i];
        }
        int x = 0;
        while(true) {
            if ((num & 1) == 1) {
                break;
            }
            num >>= 1;
            x++;
        }
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (((nums[i] >> x) & 1) == 1) {
                list1.add(nums[i]);
            }else {
                list2.add(nums[i]);
            }
        }
        int tmp = 0;
        for (int i = 0; i < list1.size(); i++) {
            tmp ^= list1.get(i);
        }
        int[] ret = new int[2];
        ret[0] = tmp;
        tmp = 0;
        for (int i = 0; i < list2.size(); i++) {
            tmp ^= list2.get(i);
        }
        ret[1] = tmp;
        return ret;

    }

三. 力扣371.两整数之和

1. 题目

2. 算法原理

3. 代码

    public int getSum(int a, int b) {
        if (b == 0) {
            return a;
        }
        return getSum((a ^ b),((a & b) << 1));
    }

四. 力扣137.只出现一次的数字 II

1. 题目

2. 算法原理

根据位图思想, 结合下方图示算法, 可以看出当该单身数二进制的某一位置为 0 时, 磨上 n 也为0 , 为 1 时磨上 n 仍为 1, 然后将该数写到位图中, 写满32个比特位, 得到的数字就是要找的单身数字

3. 代码

    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int x : nums) {
                if (((x >> i) & 1) == 1) {
                    sum++;
                }
            }
            sum %= 3;
            if (sum == 1) {
                ret |= (1 << i);
            }
        }
        return ret;
    }

五. 力扣面试题 17.19. 消失的两个数字

1. 题目

2. 算法原理

该题目和上面的题目相似, 只是换了个形式

3. 代码

    public int[] missingTwo(int[] nums) {
        int tmp = 0;
        for(int i = 0; i <= (nums.length + 2); i++) {
            tmp ^= i;
        }
        for (int n : nums) {
            tmp ^= n;
        }
        int x = 0;
        while (true) {
            if ((tmp & 1) == 1) {
                break;
            }
            tmp >>= 1;
            x++;
        }
        int[] ret = new int[2];
        for (int n : nums) {
            if (((n >> x) & 1) == 1) {
                ret[1] ^= n;
            }else {
                ret[0] ^= n;
            }
        }
        for (int i = 0; i <= nums.length + 2; i++) {
            if (((i >> x) & 1) == 1) {
                ret[1] ^= i;
            }else {
                ret[0] ^= i;
            }
        }
        return ret;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-09-26，如有侵权请联系 cloudcommunity@tencent.com 删除

算法