LC78 Subsets

Problem

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
Think

回溯

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    helper(nums, 0, {}, res);
    return res;
}
void helper(vector<int>& nums, int start, vector<int> out, vector<vector<int>>& res){
    int n = nums.size();
    if(start == n){
        res.push_back(out);
        return;
    }
    out.push_back(nums[start]);
    helper(nums, start + 1, out, res);
    out.pop_back();
    helper(nums, start + 1, out, res);
}

LC190 Reverse Bits

Problem

Reverse bits of a given 32 bits unsigned integer.

Example 1:

1
2
3
Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

1
2
3
Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Note:

  • Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

Think

遍历uint32_t即可

Code 
1
2
3
4
5
6
7
8
9
uint32_t reverseBits(uint32_t n) {
    uint32_t res = 0;
    for(int i = 0; i < 32; i++){
        res <<= 1;
        res += n & 1;
        n >>= 1;
    }
    return res;
}

LC191 Number of 1 Bits

Problem

Write a function that takes an unsigned integer and return the number of ‘1’ bits it has (also known as the Hamming weight).

Example 1:

1
2
3
Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

1
2
3
Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

1
2
3
Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Note:

  • Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3 above the input represents the signed integer -3.

Follow up:

If this function is called many times, how would you optimize it?

Think

遍历

Code 
1
2
3
4
5
6
7
8
int hammingWeight(uint32_t n) {
    int res = 0;
    for(int i = 0; i < 32; i++){
        if(n & 1) res++;
        n >>= 1;
    }
    return res;
}

LC201 Bitwise AND of Numbers Range

Problem

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

1
2
Input: [5,7]
Output: 4

Example 2:

1
2
Input: [0,1]
Output: 0
Think

即相当于求m和n的最大公共前缀

  • Approach 1

m和n同时右移直至相等

  • Approach 2

Brian Kernighan’s Algorithm，n & (n - 1)相当于去掉n的最右端的1

Code
  • Approach 1
1
2
3
4
5
6
7
8
9
int rangeBitwiseAnd(int m, int n) {
    int shift = 0;
    while(m < n){
        m >>= 1;
        n >>= 1;
        shift ++;
    }
    return m << shift;
}
  • Approach 2
1
2
3
4
5
6
int rangeBitwiseAnd(int m, int n) {
    while(m < n){
        n &= (n - 1);
    }
    return n;
}

LC231 Power of Two

Problem

Given an integer, write a function to determine if it is a power of two.

Example 1:

1
2
3
Input: 1
Output: true 
Explanation: 20 = 1

Example 2:

1
2
3
Input: 16
Output: true
Explanation: 24 = 16

Example 3:

1
2
Input: 218
Output: false
Think
  • Approach 1

(x & (-x)) == x，则说明只有1个1

  • Approach 2

(x & (x - 1)) == 0，说明只有1个1

Code
  • Approach 1
1
2
3
4
5
bool isPowerOfTwo(int n) {
    if(n == 0) return false;
    long x = (long) n;
    return (x & (-x)) == x;
}
  • Approach 2
1
2
3
4
5
bool isPowerOfTwo(int n) {
    if(n == 0) return false;
    long x = (long) n;
    return (x & (x - 1)) == 0;
}

LC268 Missing Number

Problem

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

1
2
Input: [3,0,1]
Output: 2

Example 2:

1
2
Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Think
  • Approach 1

位运算，将每一位的下标和对应的值异或，最后再和n异或即可

  • Approach 2

数列求和公式，0 - (n - 1)

Code
  • Approach 1
1
2
3
4
5
6
7
int missingNumber(vector<int>& nums) {
    int missing = nums.size();
    for(int i = 0; i < nums.size(); i++){
        missing ^= i ^ nums[i];
    }
    return missing;
}
  • Approach 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int missingNumber(vector<int>& nums) {
    int n = nums.size();
    int pred = n * (n + 1) / 2;
    int sum = 0;
    for(int i = 0; i < nums.size(); i++){
        sum += nums[i];
    }
    return pred - sum;
}
// OR
int missingNumber(vector<int>& nums) {
    int sum = 0;
    for(int i = 0; i < nums.size(); i++){
        sum += (i + 1) - nums[i];
    }
    return sum;
}

LC318 Maximum Product of Word Lengths

Problem

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

1
2
3
Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16 
Explanation: The two words can be "abcw", "xtfn".

Example 2:

1
2
3
Input: ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4 
Explanation: The two words can be "ab", "cd".

Example 3:

1
2
3
Input: ["a","aa","aaa","aaaa"]
Output: 0 
Explanation: No such pair of words.
Think

首先将每一个word转成对应的26位bit数字，然后将数字和对应的word的最长的长度对应存放到hash map里面；遍历hash map，找到对应的bit数字的按位与结果为0的（表示两个字符串没有公共字符），返回两者长度的乘积。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int maxProduct(vector<string>& words) {
    unordered_map<int, int> map;
    for(auto word: words){
        int bit = changeToBit(word);
        map[bit] = max(map[bit], (int)word.size());
    }
    int res = 0;
    for(auto i: map){
        for(auto j: map){
            if((i.first & j.first) == 0) res = max(res, i.second * j.second);
        }
    }
    return res;
}

int changeToBit(string s){
    int res = 0;
    for(char c: s){
        res |= (1 << (int)(c - 'a'));
    }
    return res;
}

LC338 Counting Bits

Problem

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example 1:

1
2
Input: 2
Output: [0,1,1]

Example 2:

1
2
Input: 5
Output: [0,1,1,2,1,2]

Follow up:

  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).
  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
Think

i和i - 1的按位与之后会消除i的最右端的1，也就是有res[i] = res[i & (i - 1)] + 1，同时i一定比i & (i - 1)要大。

Code 
1
2
3
4
5
6
7
vector<int> countBits(int num) {
    vector<int> res(num + 1, 0);
    for(int i = 1; i <= num; i++){
        res[i] = res[i & (i - 1)] + 1;
    }
    return res;
}

LC342 Power of Four

Problem

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

1
2
Input: 16
Output: true

Example 2:

1
2
Input: 5
Output: false

Follow up: Could you solve it without loops/recursion?

Think

即三点：

  • 正数
  • 只有一个1
  • 1的位置为倒数奇数位，即num & 0xaaaaaaaa得出的结果是0
Code 
1
2
3
bool isPowerOfFour(int num) {
    return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0xaaaaaaaa) == 0);
}

LC371 Sum of Two Integers

Problem

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:

1
2
Input: a = 1, b = 2
Output: 3

Example 2:

1
2
Input: a = -2, b = 3
Output: 1
Think

采用的是递归式的加法，每次将当前结果加上当前进位即可。需要注意的是左移的时候可能会产生左移INT_MIN的问题，会报错，因此需要先用一个long类型的mask处理一下，使其均变为32位的int；最后返回的时候需要判断当前a是否为INT_MAX，如果是INT_MAX，则需要取反。

Code 
1
2
3
4
5
6
7
8
9
10
int getSum(int a, int b) {
    long mask = 0xFFFFFFFF;
    while(b != 0){
        int sum = (a ^ b) & mask;
        int carry = ((a & b) & mask) << 1;
        a = sum;
        b = carry;
    }
    return a < INT_MAX ? a : ~(a & mask); 
}

LC389 Find the Difference

Problem

Given two strings *s* and *t* which consist of only lowercase letters.

String *t* is generated by random shuffling string *s* and then add one more letter at a random position.

Find the letter that was added in *t*.

Example:

1
2
3
4
5
6
7
8
9
Input:
s = "abcd"
t = "abcde"

Output:
e

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

将s和t都变成26位的unsigned int，然后判断出两者在那一位不同即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char findTheDifference(string s, string t) {
    uint32_t x1 = change(s), x2 = change(t);
    uint32_t x = x1 ^ x2;
    int cnt = 0;
    while(x){
        cnt++;
        x >>= 1;
    }
    return 'a' + cnt - 1;
}
uint32_t change(string &s){
    uint32_t res = 0;
    for(auto c: s){
        res ^= (1 << (c - 'a'));
    }
    return res;
}

Review

位操作主要包括：AND OR XOR NOT和左移右移(<< 和 >>)，常用的使用这些运算符实现的操作有：

  • Set union A | B
  • Set intersection A & B
  • Set subtraction A & ~B
  • Set negation ALL_BITS ^ A or ~A
  • Set bit A |= 1 << bit
  • Clear bit A &= ~(1 << bit)
  • Test bit (A & 1 << bit) != 0
  • Remove last bit of 1 A&-A or A&~(A-1) or x^(x&(x-1))
  • Remove last bit A&(A-1)
  • Get all 1-bits ~0