喜刷刷: bit manipulation

Friday, November 21, 2014

[LeetCode] Single Number I, II

Single Number I

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

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

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?

思路：Single Number I

和find duplicate正好相反，但是仍然可以用排序或hash table解决。排序以后，对每个坐标i，查找A[i-1], A[i+1]中是否有等于A[i]的，没有则为要找的数。或者用hash table/set来记录扫描过的数字。如果A[i]不在hash table中，则插入，如果已经在，则在hash table中删除，最后table中剩下的就是要找的数。但排序法事件复杂度是O(nlogn)，而hash table尽管是O(n)事件复杂度，需要o(n)的extra memory。

这题的终极解法是利用位运算中的异或：x^x = 0, x^0 = x。并且异或有交换律：1^1^0 = 0 = 1^0^1。所以如果将全部数字进行异或运算，所有重复元素都会被消除，最后的结果便是那个唯一的数。

class Solution {
public:
    int singleNumber(int A[], int n) {
        int res = 0;
        for(int i=0; i<n; i++) 
            res ^= A[i];
        return res;        
    }
};

思路：Single Number II

由于x^x^x = x，无法直接利用I的方法来解。但可以应用类似的思路，即利用位运算来消除重复3次的数。以一个数组[14 14 14 9]为例，将每个数字以二进制表达：

1110

1001

_____

4331 对每一位进行求和

1001 对每一位的和做%3运算，来消去所有重复3次的数

class Solution {
public:
    int singleNumber(int A[], int n) {
        int res = 0;
        for(int i=31; i>=0; i--) {
            int sum = 0;
            int mask = 1<<i;
            for(int j=0; j<n; j++) {
                if(A[j] & mask) 
                    sum++;
            }
            res = (res<<1) + (sum%3);
        }
        return res;
    }
};

Monday, November 17, 2014

[LeetCode] Subsets I, II

Subsets I

Given a set of distinct integers, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

思路：Subsets I

方法1：backtracking

与combination/combination sum I, II思路一样。区别在于单层扫描时不用跳过重复数字，而在进入下一层递归前就需要把当前subset压入结集中。

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> allSets;
        vector<int> sol;
        allSets.push_back(sol);
        sort(S.begin(),S.end());
        findSubsets(S, 0, sol, allSets);
        return allSets;
    }
    
    void findSubsets(vector<int> &S, int start, vector<int> &sol, vector<vector<int>> &allSets) {
        for(int i=start; i<S.size(); i++) {
            sol.push_back(S[i]);
            allSets.push_back(sol);
            findSubsets(S, i+1, sol, allSets);
            sol.pop_back();
        }
    }
};

方法2：添加数字构建subset

起始subset集为：[]
添加S0后为：[], [S0]
添加S1后为：[], [S0], [S1], [S0, S1]
添加S2后为：[], [S0], [S1], [S0, S1], [S2], [S0, S2], [S1, S2], [S0, S1, S2]
红色subset为每次新增的。显然规律为添加Si后，新增的subset为克隆现有的所有subset，并在它们后面都加上Si。

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> allSets;
        vector<int> sol;
        allSets.push_back(sol);
        sort(S.begin(), S.end());
        for(int i=0; i<S.size(); i++) {
            int n = allSets.size();
            for(int j=0; j<n; j++) {
                sol = allSets[j];
                sol.push_back(S[i]);
                allSets.push_back(sol);
            }
        }
        return allSets;
    }
};

方法3：bit manipulation

由于S[0: n-1]组成的每一个subset，可以看成是对是否包含S[i]的取舍。S[i]只有两种状态，包含在特定subset内，或不包含。所以subset的数量总共有2^n个。所以可以用0~2^n-1的二进制来表示一个subset。二进制中每个0/1表示该位置的S[i]是否包括在当前subset中。

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> allSets;
        sort(S.begin(), S.end());
        unsigned long long maxNum = pow(2, S.size()) - 1;
        for(unsigned long long i=0; i<=maxNum; i++) 
            allSets.push_back(num2subset(S, i));
        return allSets;
    }
    
    vector<int> num2subset(vector<int> &S, unsigned long long num) {
        vector<int> sol;
        int i=0;
        while(num) {
            if(num & 1) sol.push_back(S[i]);
            num >>= 1;
            i++;
        }
        return sol;
    }
};

思路：Subsets II

和3sum, combination sum II一样的去重思路。这类问题两个细节千万不能粗心：

1. 一定要先排序
2. 调用下一层递归时(ln 17)，起始index 一定是i+1而不能错写成start+1

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int>> allSets;
        vector<int> sol;
        allSets.push_back(sol);
        sort(S.begin(), S.end());
        findSubsetsWithDup(S, 0, sol, allSets);
        return allSets;
    }
    
    void findSubsetsWithDup(vector<int> &S, int start, vector<int> &sol, vector<vector<int>> &allSets) {
        for(int i=start; i<S.size(); i++) {
            if(i>start && S[i]==S[i-1]) continue;
            sol.push_back(S[i]);
            allSets.push_back(sol);
            findSubsetsWithDup(S, i+1, sol, allSets);
            sol.pop_back();
        }
    }
};