191 Number of 1 Bits

来源：Leetcode

原帖：https://leetcode.com/problems/number-of-1-bits/

题目：
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight). For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

代码：

 class Solution {  
 public:  
   int hammingWeight(uint32_t n) {  
     int count = 0;  
     while (n) {  
       n = (n & (n-1));  
       count++;  
     }  
     return count;  
   }  
 };  

190 Reverse Bits

来源：Leetcode

原帖：https://leetcode.com/problems/reverse-bits/
            http://articles.leetcode.com/2011/08/reverse-bits.html

题目：
Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).
Follow up:
If this function is called many times, how would you optimize it?

思路：

[1]. 使用swap trick，就是交换整数中i-th, j-th bit的位置。这个思路比较容易想到。

The XOR swap trick:
Reversing bits could be done by swapping the n/2 least significant bits with its most significant bits. The trick is to implement a function called swapBits(i, j), which swaps the i^th bit with the j^th bit. If you still remember how XOR operation works: 0 ^ 0 == 0, 1 ^ 1 == 0, 0 ^ 1 == 1, and 1 ^ 0 == 1. We only need to perform the swap when the i^th bit and the j^th bit are different. To test if two bits are different, we could use the XOR operation. Then, we need to toggle both i^th and j^th bits. We could  apply the XOR operation again. By XOR-ing the i^thand j^th bit with 1, both bits are toggled.

代码：

 class Solution {  
 public:  
     void swap(uint32_t& n, int i, int j) {  
         int p_i = ((n >> i) & 1);  
         int p_j = ((n >> j) & 1);  
         if (p_i ^ p_j) {  
             n ^= ((1 << i) | (1 << j));  
         }  
     }  
   
     uint32_t reverseBits(uint32_t n) {  
         int bits = sizeof(n) * 8;  
         for (int i = 0; i < bits/2; i++) {  
             swap(n, i, bits - i - 1);  
         }  
         return n;  
     }  
 };  

[2] 考虑分治法，time complexity O(log(n)).

The divide and conquer approach:Remember how merge sort works? Let us use an example of n == 8 (one byte) to see how this works:

      01101001
        /         \
   0110      1001
    /   \         /   \
 01   10   10   01
 /\     /\     /\     /\
0 1  1 0  1 0   0 1

The first step is to swap all odd and even bits. After that swap consecutive pairs of bits, and so on… Therefore, only a total of log(n) operations are necessary. The below code shows a specific case where n == 32, but it could be easily adapted to larger n‘s as well.

代码：

 class Solution {  
 public:  
     uint32_t reverseBits(uint32_t n) {  
         assert(sizeof(n) == 4);  
         n = ((n & 0x55555555) << 1) | ((n & 0xAAAAAAAA) >> 1);  
         n = ((n & 0x33333333) << 2) | ((n & 0xCCCCCCCC) >> 2);  
         n = ((n & 0x0F0F0F0F) << 4) | ((n & 0xF0F0F0F0) >> 4);  
         n = ((n & 0x00FF00FF) << 8) | ((n & 0xFF00FF00) >> 8);  
         n = ((n & 0x0000FFFF) << 16) | ((n & 0xFFFF0000) >> 16);  
         return n;  
     }  
 };  

License Plate & Dictionary

来源：Meetqun,一亩三分地, Google Phone Interview

原帖：http://www.meetqun.com/thread-2802-1-1.html
            http://www.meetqun.com/forum.php?mod=viewthread&tid=4901&ctid=41

题目：

“AC1234R” => CAR, ARC | CART, CARED not the shortest

“OR4567S” => SORT, SORE | SORTED valid, not the shortest | OR is not valid, missing S

Google电面题目: 04/13/2015

1 <= letters <= 7

O(100) license plate lookups

O(4M) words in the dictionary

d1 = abc   000....111

d2 = bcd   000…..110

s1 = ac1234r  00001...101

s1 & d1 == s1 d1

s1 & d2 != s1

代码：

 int convert2Num(string s) {   
     int res = 0;   
     for (int i = 0; i < s.size(); ++i) {   
         if (!isdigit(s[i]) {   
             res |= 1 << (s[i] - ‘a’);    
         }   
     }   
     return res;   
 }   
   
 string find_shortest_word(string license, vector<string> words) {   
     int lis_num = convert2Num(license);   
     string res;    
     for (int i = 0; i < words.size(); ++i) {   
         int word_num = convert2Num(words[i]); // conversion;    
         if (lis_num & word_num == lis_num) {   
             if (res.empty() || res.size() > words[i].size())   
                 res = words[i]; // brute force; 可以sorting来减少比较次数   
         }   
     }   
     return res;   
 }  

<key, conversion number》

<words, save shortest length of words>

abc, abccc,   <000...111, abc>   

Follow up:
dictionary = { “BAZ”, “FIZZ”, “BUZZ” } | BAZ only has one Z

vector<int> map(26, 0);

a -> 0,   z -> 25;

map[s-’a’]++;

need[26];

need[i] < map[i]

代码：

 bool compare(const string& s1, const string& s2) {   
     return s1.size() < s2.size();   
 }    
   
 string find_shortest_string(string license, vector<string> words) {   
     sort(word.begin(), word.end(), compare);   
     int lic_num = convert2Num(license);   
     vector<int> map(26, 0);   
     for (auto i : license) {   
         if (!isdigit(i)) map[i-’a’]++;   
     }   
   
     for (int i = 0; i < words.size(); ++i) {   
         int word_num = convert2Num(words[i]);   
         // First check that it has all the letters, then check the counts   
         if (lic_num & word_num != lic_num) continue;   
   
         vector<int> word_map(26, 0);   
         for (auto k : words[i]) {   
             if (!isdigit(k)) map[k-’a’]++;   
         }    
         int j = 0;   
         for (; j < 26; ++j) {   
             if (word_map[‘a’+j] < map[‘a’+j]) break;   
         }   
         if (j == 26) return words[i];   
     }   
 }    

Follow up:

find_shortest_word(“12345ZZ”, dictionary) 50% => “FIZZ” | 50% => “BUZZ”

vector<string> s = {};

s[rand() % 2];

reservoir sampling;

FIZZ: s = words;

count = 1;

BUZZ: count++; count = 2;

rand() % count == 0 : s = BUZZ;