136. Single Number

Given an array of integers, every element appearstwiceexcept for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

S1: Hash table

S2: bit manipulation

Exclusive or(XOR) 会抵消出现了两次的元素

  int singleNumber(vector<int>& nums) {
       int result = 0;
       for(auto i: nums) result ^= i;
       return result;
   }

389. Find the Difference

Given two stringssandtwhich consist of only lowercase letters.

Stringtis generated by random shuffling stringsand then add one more letter at a random position.

Find the letter that was added int.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

S: bit manipulation O(n)

和sigle number一样，用xor抵消出现过两次的char

    char findTheDifference(string s, string t) {
        char c = 0;
        for (char i : s) c ^= i;
        for (char i : t) c ^= i;
        return c;
    }

137. Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

S: bit manupulation

记录出现一次，两次，三次的情况

    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0, three = 0;
        for(auto i: nums){
            two |= one & i;
            one ^= i;
            three = one & two;
            one &= ~three;
            two &= ~three;
        }
        return one;
    }

260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.

S: bit manipulation

对于两个只出现一次的数，若i位相同XOR后i位为0；若i位不同，XOR后i位为一。取任意i位为1的位为pivot V可以将整个数组分为i为为1和i位为0两组，则这两个要求的数分别在两组中各出现一次，可以用XOR求解。
isolate rightmost 1: i &= (-i) 二进制中-i = ~x + 1[]

details

    vector<int> singleNumber(vector<int>& nums) {
        int diff = 0, num1 = 0, num2 = 0;
        for(int i: nums) diff ^= i;
        diff &= (-diff);//isolate rightmost 1;

        for(int i: nums) (diff & i) > 0? num1 ^= i: num2 ^= i;
        return vector<int>{num1, num2};
    }