位运算：异或

0136. 只出现一次的数字 (opens new window)

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

解析

将数组中所有数字做异或，两两消除，最终剩下的就是只出现一次的元素。

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (auto &num: nums) ans ^= num;
        return ans;
    }
};

func singleNumber(nums []int) int {
    ans := 0
    for i := 0; i < len(nums); i++ {
        ans ^= nums[i]
    }
    return ans
}

0268. 丢失的数字 (opens new window)

题目

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

解析

将 [0, n] 与 nums 中的所有数字异或，最终得到的就是 nums 中缺失的数字。

代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ans = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            ans ^= nums[i] ^ i;
        }
        return ans;
    }
};

func missingNumber(nums []int) int {
    ans := len(nums)
    for i := 0; i < len(nums); i++ {
        ans ^= i ^ nums[i];
    }
    return ans;
}

0389. 找不同 (opens new window)

题目

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

解析

由于两个相同字符异或结果为 0，则 s 与 t 的全部字符异或之后就是 t 中添加的字符。

代码

class Solution {
public:
    char findTheDifference(string s, string t) {
        char c = t.back();
        for (int i = 0; i < s.length(); i++) {
            c ^= s[i] ^ t[i];
        }
        return c;
    }
};

func findTheDifference(s string, t string) byte {
    ans := t[len(t) - 1]
    for i := 0; i < len(s); i++ {
        ans ^= s[i] ^ t[i];
    }
    return ans
}