421. Maximum XOR of Two Numbers in an Array

描述

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

分析

这道题要求我们找出一个数组中两个数产生的最大的XOR值，并且要求在O(n)的时间复杂度内完成。

如果没有最后一条限制，那么这道题还是挺简单的，不过此题来自微软的面试，那么最容易想到的O(n*2)的解法肯定是无法拿到offer的。

我们知道，要找到这个最大的异或值，应该让两个数在对应位上的差距尽可能大，所以我们要先把组成一个数的各个位取出来，之后我们假设有一个候选最大值candidate，下一步要做的是确认数组中的某两个数可以在经过XOR之后得到这个candidate。

这里就是这道题的精髓部分，我们需要利用异或操作的性质:

如果A^B==C
那么B^C==A,或A^C==B

所以我们要想证明这个candidate确实是由数组中的两个数XOR后得到的，只需要把candidate看成C，把数组中的两个数看做A和B，之后遍历之前得到的各个二进制位并且与candidate进行XOR，如果异或的结果与之前获得的二进制位中的某个值相同，则说明candidate是由数组中的两个数做XOR得到的。

这里就存在一个问题，我们之前得到的二进制位如果保存在数组里，反复查找就显得很浪费时间了，所以我们用一个hash-table来降低查找操作上的时间开销。

代码如下：

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int maxValue=0,mask=0;
        unordered_set<int> map;
        for(int i=31;i>=0;i--){
            mask|=(1<<i);
            map.clear();
            for(int num:nums)
                map.insert(num&mask);
            int candidate= maxValue|(1<<i);
            for(int prefix:map){
                if(map.find(prefix^candidate)!=map.end()){
                    maxValue=candidate;
                    break;
                }
            }
        }
        return maxValue;
    }
};

这道题还有利用字典树和递归的两种解法，不过我还没有完全理解这两种算法。

• [Trie and recursion ]

397. Integer Replacement

描述:

Given a positive integer n and you can do operations as follow:

1.If n is even, replace n with n/2.

2.If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1

Example 2:

Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

这道题要求我们寻找一种最快的将给定数字变成1的路径，转换规则题中已经给出，感觉就是在观察中得出一条规律，即:

1.如果某个数的末尾是01，则-1会比较快

2.如果某个数末尾是11，则+1会比较快，但这里有一个特例，即3,3虽然以11结尾，但是却发现它如果+1反而会比较慢，所以我们将其作为特例考虑。

3.其余情况全部直接右移一位

为什么会得出这样的规律呢？因为要想最快的将一个数通过除以2的方式变成1，就要让其含有尽可能多的0，所以以01结尾的应该-1，以11结尾的应该+1(造成连续进位)。

还有一个边界条件，当给出的数为INT_MAX时，也就是二进制表示为32个1的那个数，此时如果判断其以11结尾之后，必然会+1，那么就会造成溢出，所以我们在最开始添加一个if判断进行过滤。 (个人感觉这是这道题唯一考察思维严密性的地方)

我主观上认为这道题没什么意思，或许是数学水平还不够吧，代码如下：

class Solution {
public:
    int integerReplacement(int n) {
        int count=0;
        if(n==INT_MAX)
            return 32;
        while(n!=1){
            if((n&1)==0)
                n=n>>1;
            else if(n==3||((n>>1)&1)==0)
                n--;
            else
                n++;
            count++;
        }
        return count;
    }
};

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:

1.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?

2.Space complexity should be O(n).

3.Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

分析

这道题需要我们对一个数中’1’bit的数量进行统计，最最容易想到的方法就是O(n*sizeof(integer))的算法，也就是将一个数的二进制表示一位位拆开，统计1的个数，代码如下:

/*compute every bit then judge if it equals 1*/
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(num+1,0);
        for(int i=0;i<=num;i++){
            for(int j=0;j<32;j++){
                if(i!=0&&(i>>j)&1==1)
                    res[i]++;
            }
        }
        return res;
    }
};

在题目的暗示下，我们有了更好的方法，那就是将0~num的区间进行划分，分成[2-3], [4-7], [8-15]这样的区间，我们如果把0~15的二进制数中的1进行统计，如下:

0000    0
-------------
   0001    1
-------------
   0010    1
   0011    2
-------------
   0100    1
   0101    2
   0110    2
   0111    3
-------------
   1000    1
   1001    2
  1010    2
  1011    3
  1100    2
  1101    3
  1110    3
  1111    4

发现了一个规律，从0100开始，前一半和上一个区间中的值完全相同，而后一半是上一个区间中的值依次+1。所以，我们可以尽量利用已经计算出的结果对算法进行优化。代码如下:

/*make use of what you have produced*/
class Solution {
public:
    vector<int> countBits(int num) {
        if(num==0)
            return {0};
        vector<int> res{0,1};
        int k=1,i=1;
        while(i<=num){
            for(i=pow(2,k);i<pow(2,k+1);i++){
                if(i>num)
                    break;
                int tmp=(pow(2,k+1)-pow(2,k))/2;
                if(i<pow(2,k)+tmp)
                    res.push_back(res[i-tmp]);
                else
                    res.push_back(res[i-tmp]+1);
            }
            k++;
        }
        return res;
    }
};

这个代码在交给OJ之后，测算出的时间似乎并不能令人满意，甚至还不如第一种暴力破解的算法。所以，参照讨论区大神的代码，我发现了更深的一个规律。

如果一个数是偶数，其含有的’1’的个数与其除以2的结果含有的‘1’的个数相同，如果是奇数，则和其除以2的结果含有的‘1’的个数再加1相同，代码如下:

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res{0};
        for(int i=1;i<=num;i++){
            if(i%2==0)
                res.push_back(res[i/2]);
            else
                res.push_back(res[i/2]+1);
        }
        return res;
    }
};

对于位运算的问题，我们只有多做题，多参阅讨论区大神的思路，才能获取到足够的经验，游刃有余地处理各类问题，希望自己能够继续保持谦逊的态度吧。

2016-10-20

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

分析

这道题要求找出一个string组成的vector中两个不重复子串的长度之积的最大值，方法有两种:

1.穷举法

枚举所有可能，最后找出长度之积最大且不相交的两个字符串，这种方法很容易想到，但细节方面还是需要注意，这里我们考虑到题目要求中保证输入数据只含有小写字母，所以我们就用一个数组来进行映射操作。

代码如下:

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int max=0;
        for(int i=0;i<words.size();i++){
            int k=0;
            int map[26]={0};
            int size_a=words[i].size();
            while(k<words[i].size())
                map[words[i][k++]-'a']=1;
            for(int j=i+1;j<words.size();j++){
                int m=0;
                int size_b=words[j].size();
                if(size_a*size_b>max){
                    while(m<words[j].size()){
                        if(map[words[j][m]-'a']==0)
                            m++;
                        else
                            break;
                    }
                    if(m==words[j].size())
                        max=size_a*size_b;
                    else
                        continue;
                }
            }
        }
        return max;
    }
};

显然，多次的循环会极大地影响算法的时间性能，于是我们考虑换一个角度进行考虑。

我们只是想判断穷举过程中后一个字符串中的字母是否在前面的某个字符串中出现过，既然只是判断字母，那么我们可以用一个二进制位来保存字母的存在与否及其位置关系。

具体而言，我们需要一个长度为n的数组，n为vector的长度，之后对每个子串进行遍历，遍历过程中，需要将每一个字母映射到相应的二进制位上，之后，想要判断是否在之前出现过，只需要对两个子串对应的二进制数做AND运算，结果为0，则说明没有出现重复。

代码如下:

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int size=words.size();
        int max=0;
        vector<int> word(size,0);
        for(int i=0;i<words.size();i++){
            for(int j=0;j<words[i].size();j++)
                word[i]|=1<<(words[i][j]-'a');
        }
        for(int i=0;i<words.size();i++){
            for(int j=i+1;j<words.size();j++){
                if((word[i]&word[j])==0&&words[i].size()*words[j].size()>max)
                    max=words[i].size()*words[j].size();
            }
        }
        return max;
    }
};

405. Convert a Number to Hexadecimal

描述

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

1.All letters in hexadecimal (a-f) must be in lowercase.

2.The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character ‘0’; otherwise, the first character in the hexadecimal string will not be the zero character.

3.The given number is guaranteed to fit within the range of a 32-bit signed integer.

4.You must not use any method provided by the library which converts/formats the number to hex directly.

Example 1:

Input:
26

Output:
"1a"

Input:
-1

Output:
"ffffffff"

分析

这道题要求我们将一个十进制数转换为十六进制数。

那么对于正数，我们用辗转相除法就很容易求得其十六进制表示，但这道题还要求我们考虑输入为负的情况，我们知道，负数是无法用这个方法进行转换的。

要解决这个问题，我们得先考虑一个十进制数在计算机中是如何存储的。

以3为例,其二进制表示为（考虑int类型为32位）

0000 0000 0000 0000 0000 0000 0000 0011 

我们将这样的某个整数的绝对值的二进制表示称为源码。

那么如果我们对这个二进制串按位取反，可得其反码

1111 1111 1111 1111 1111 1111 1111 1100

反码再+1可得其补码

1111 1111 1111 1111 1111 1111 1111 1101

而补码正是一个负数在计算机中的存储方式，而-3的十六进制表示是

0xfffffffd

所以我们看到，要将一个十进制数转换为十六进制数，不管其是正数还是负数，都只需要将其二进制表示每四位分成一个单元，将其取出后计算这四位二进制数代表的十进制数，与0~f之间的数字做一个映射即可。要把每四位取出也很简单，与0xf进行AND运算即可。代码如下：

class Solution {
public:
    string toHex(int num) {
        string res;
        int low=0,high=0;
        char map[16]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
        while(num&&res.size()<8){
            res=map[(num&0xf)]+res;
            num=num>>4;
        }
        return res;
    }
};

需要注意的一点是，如果输入为负数，那么我们需要在循环条件中，保证要返回的字符串长度小于8，因为输入是32位int类型。这和负数计算机中的存储方式和C++中的右移运算符有关。

在C++中，左移是逻辑移位，也就是说在数字后面补0，右移运算符是算术移位，也就是在左侧补符号位(正数补0，负数补1，不同编译环境可能不一样)，所以我们以-128为例，每次右移1位，右移10次来查看结果，如下:

-64
-32
-16
-8
-4
-2
-1
-1
-1
-1

因为不断在左边补1，而-1在计算机中以1111 1111存储(补码)，所以无论再怎么右移，最后得到的二进制串在经过-1，取反后得到的真值永远是-1，那么循环条件如果只有num!=0，就会陷入死循环。

这道题不仅考查了正数的十进制与十六进制的转换，还通过将负数引入测试样例的方法让我们思考一个数在计算机中究竟是怎么存储的以及C++中右移运算符的特殊性，是一道非常综合的题目，值得反复琢磨。