Exercises: 461. Hamming Distance
Calculate the number of positions at which the corresponding bits are different.
Solution: Do XOR and find the number of 1.
class Solution {
public:
int hammingDistance(int x, int y) {
int tmp = x ^ y;
int ans = 0;
while( tmp > 0 ){
if( tmp & 1 ) ans++;
tmp = tmp >> 1;
}
return ans;
}
};
int main()
{
Solution solver;
cout << solver.hammingDistance( 1, 4 ) << endl;
return 0;
}
Exercises: 190. Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
eg.
00000010100101000001111010011100 ->
00111001011110000010100101000000
#include <iostream>
#include <bitset>
using namespace std;
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ans = 0;
for( int i = 0; i < 32; ++i )
{
ans = (ans<<1) + (n&1);
n = n >> 1;
}
return ans;
}
};
int main()
{
Solution solver;
uint32_t value = 43261596;
cout << (bitset<32>)value << endl; // output as binary format
value = solver.reverseBits( value );
cout << value << endl;
cout << (bitset<32>)value << endl; // output as binary format
return 0;
}
Exercises: 136. Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
Solution:
Plan A, sort all elements and find the single one.
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
class Solution {
public:
int singleNumber(vector<int>& nums) {
sort( nums.begin(), nums.end() );
stack<int> sta;
sta.push( nums[0] );
for( int i = 1; i < nums.size(); ++i ){
if( sta.size() == 0 || sta.top() != nums[i] )
{
sta.push( nums[i] );
}
else if( sta.top() == nums[i] ){
sta.pop();
}
}
return sta.top();
}
};
int main()
{
vector<int> arr{ 4,1,2,1,2 };
Solution solver;
cout << solver.singleNumber( arr ) << endl;
return 0;
}
Plan B, do XOR and get the result.
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for( auto value: nums )
{
ans = ans ^ value;
}
return ans;
}
};
Exercises: 342. Power of Four
Given an integer n, return true if it is a power of four. Otherwise, return false.
Solution: if 
, then we have 
.
#include <iostream>
#include <iostream>
#include <functional>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;
class Solution {
public:
bool isPowerOfFour(int n) {
for( int i = 0; i < 16; ++i )
{
int value = 1;
value = (value << i) * (value << i);
if( value == n )
{
return true;
}
}
return false;
}
};
int main()
{
Solution worker;
cout << worker.isPowerOfFour( -64 ) << endl;
return 0;
}
Exercises: 338. Counting Bits
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.
Solution: do dynamic programming to speed up. To find the mathematical laws in the problem.
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> countBits(int n) {
// 0 - 0; 1 - 1; 2 - f(1); 3 - f(2)+1; 4 - f(1)
vector<int> dp( n+1, 0 );
for( int i = 1; i <= n; ++i )
{
if( i & 1 ){
dp[i] = dp[i-1]+1;
}
else{
int tmp = i;
while( 0 == (tmp&1) ){
tmp = tmp >> 1;
}
dp[i] = dp[tmp];
}
}
return dp;
}
};
int main()
{
Solution solver;
auto arr = solver.countBits( 5 );
for( auto element: arr )
{
cout << element << " ";
}
cout << endl;
return 0;
}
Exercises: 260. Single Number III
Given an integer array 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. You can return the answer in any order.
Solution:
plan A, just sort and compare one by one.
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
stack<int> ans;
sort( nums.begin(), nums.end() );
int tmp = nums[0];
ans.push( nums[0] );
for( int i = 1;i < nums.size(); ++i ){
if( ans.size() == 0 || nums[i] != ans.top() ){
ans.push( nums[i] );
}
else{
if( nums[i] == ans.top() ){
ans.pop();
}
}
}
vector<int> realAns;
while( ans.size() ) {
realAns.push_back( ans.top() );
ans.pop();
}
return realAns;
}
};
int main()
{
std::vector<int> arr{ 0,1,2,2 };
Solution solver;
auto ans = solver.singleNumber( arr );
for( auto element: ans )
{
cout << element << " ";
}
cout << endl;
return 0;
}
Plan B: create a mask number by XOR and divide all numbers to two arrays. Convert the problem to 136. Single Number.
The mask is the value of the last digit 1 in the original binary format. int mask = xorValue&(-xorValue);.
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int xorValue = 0;
for( auto value: nums ){
xorValue = xorValue ^ value;
}
int mask = xorValue&(-xorValue); // 10101000 -> 1000; The value of the last digit 1
vector<int> ans{ 0, 0 };
for( auto value: nums ){
if( value & mask ){
ans[0] = ans[0] ^ value;
}
else {
ans[1] = ans[1] ^ value;
}
}
return ans;
}
};
int main()
{
std::vector<int> arr{ 0,1,2,2 };
Solution solver;
auto ans = solver.singleNumber( arr );
for( auto element: ans )
{
cout << element << " ";
}
cout << endl;
return 0;
}
