Bit Manipulation
136. Single Number
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?
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (int i = 0; i < 32; ++i) {
int cnt = 0;
for (auto num : nums) {
if ((num >> i) & 1u) cnt++;
}
cnt %= 3;
if (cnt) res |= (1u << i);
}
return res;
}
};
260. Single Number III
iven 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.
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. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> res;
int bit_xor = 0;
for (auto n : nums) bit_xor ^= n;
int i = 0;
for (i = 0; i < 8 * sizeof (int) ; ++i) {
if (bit_xor & (1<<i)) break;
}
int first_num = 0;
int second_num = 0;
for (auto n : nums) {
if (n & (1<<i)) first_num ^= n;
else second_num ^= n;
}
res.push_back(first_num);
res.push_back(second_num);
return res;
}
};
201. Bitwise AND of Numbers Range
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
if (m == 0 || n == 0) return 0;
if (m == n) return m;
int h1 = 0, h2 = 0;
for (int i = 0; i < 32; ++i) {
if (m & (1u<<i)) h1 = i;
if (n & (1u<<i)) h2 = i;
}
int res = 0;
if (h1 == h2) {
res = m;
for (long long i = m; i <= n; ++i) res &= i;
}
return res;
}
};
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.
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. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> res;
int bit_xor = 0;
for (auto n : nums) bit_xor ^= n;
int i = 0;
for (i = 0; i < 8 * sizeof (int) ; ++i) {
if (bit_xor & (1<<i)) break;
}
int first_num = 0;
int second_num = 0;
for (auto n : nums) {
if (n & (1<<i)) first_num ^= n;
else second_num ^= n;
}
res.push_back(first_num);
res.push_back(second_num);
return res;
}
};
268. Missing Number
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example, Given nums = [0, 1, 3] return 2.
class Solution {
public:
int missingNumber(vector<int>& nums) {
long sum = 0;
for (auto n : nums) {
sum += n;
}
long n = nums.size();
long target = n*(n+1)/2;
return int(target - sum);
}
};
318. Maximum Product of Word Lengths
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:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] Return 16 The two words can be "abcw", "xtfn".Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"] Return 4 The two words can be "ab", "cd".Example 3:
Given ["a", "aa", "aaa", "aaaa"] Return 0 No such pair of words.
class Solution {
public:
int maxProduct(vector<string>& words) {
vector<int> mask(words.size());
int res = 0;
sort(words.begin(), words.end(), [](const string& a, const string& b){
return a.size() > b.size();
});
for (size_t i = 0; i < words.size(); ++i) {
for (auto c : words[i]) {
mask[i] |= (1 << (c - 'a'));
}
for (size_t j = 0; j < i; ++j) {
if (mask[i] & mask[j]) continue;
res = max(res, int(words[i].size() * words[j].size()));
break;
}
}
return res;
}
};
338. Counting Bits
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: For num = 5 you should return [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. Show Hint
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res(num + 1);
if (num <= 0) return res;
res[1] = 1;
for (int i = 2; i <= num; i*=2) {
for (int j = i; j < i*2 && j <= num; ++j) {
res[j] = res[j-i] + 1;
}
}
return res;
}
};
342. Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
Example: Given num = 16, return true. Given num = 5, return false.
Follow up: Could you solve it without loops/recursion?
class Solution {
public:
bool isPowerOfFour(int num) {
return num > 0 && ((num&(num-1)) == 0) && (num & 0x55555555);
}
};
X times 7
Write a function to calculate x 7 without using + - / %. x 7可以做如下分解： x 7 = x 4 + x 2 + x = (x << 2) + (x << 1) + x = add(x << 2, add(x << 1, x)) 所以本质上这题就是考用二进制实现add函数。
int add(int a, int b) {
int sum, carry;
do {
sum = a ^ b;
carry = (a & b) << 1;
a = sum;
b = carry;
} while (b);
return a;
}
int times_7(int val) {
return add(val << 2, add(val << 1, val));
}