【Leetcode刷题笔记 持续更新】Day08

Day 08


异或运算:x ^ 0 = x​ , x ^ 1 = ~x
与运算:x & 0 = 0 , x & 1 = x


数组中数字出现的次数 I

在一个数组 nums 中除两个数字只出现一次之外,其他数字都出现了两次。请找出只出现一次的数字。

思路: 这个问题在于如何找出两个出现一次的数字。假设数字分别为x,y
如果只有一个数字,那么将数组所有数字异或便能得到那个数。但是题目中有两个,那么异或的结果为x^y。
因为x和y必不相同,所以至少二进制中有一位不相同,因此根据此位可以将 nums 拆分为分别包含 x 和 y 的两个子数组。易知两子数组都满足 「除一个数字之外,其他数字都出现了两次」。因此,仿照以上一个数字问题的思路,分别对两子数组遍历执行异或操作,即可得到两个只出现一次的数字 x, y 。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : nums)               // 1. 遍历异或
            n ^= num;
        while((n & m) == 0)               // 2. 循环左移,计算 m
            m <<= 1;
        for(int num: nums) {              // 3. 遍历 nums 分组
            if((num & m) != 0) x ^= num;  // 4. 当 num & m != 0
            else y ^= num;                // 4. 当 num & m == 0
        }
        return new int[] {x, y};          // 5. 返回出现一次的数字
    }
}

数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

思路: 各二进制位的 位运算规则相同 ,因此只需考虑一位即可。如下图所示,对于所有数字中的某二进制位 1 的个数,存在 3 种状态,即对 3 余数为 0, 1, 2。

若输入二进制位 1 ,则状态按照0->1->2顺序转换;
若输入二进制位 0 ,则状态不变。

例:
【Leetcode刷题笔记 持续更新】Day08

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }
}

不用加减乘除做加法

写一个函数,求两个整数之和,要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

思路: 一拿过来确实有些懵,这个题其实本质上还是用到了异或,可见异或在处理位运算问题的重要性。
【Leetcode刷题笔记 持续更新】Day08
可见,无进位和与异或相同,进位与与运算相同但是需要左移一位。所以两个数的和就是无进位和加进位。但是不能出现“+”,因此只能继续做无进位和,直到进位为0,得到结果

class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

上一篇:day08_面向对象(中)


下一篇:day08_03 客户端多次连接