# 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.


## 分析

如果A^B==C



class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
unordered_set<int> map;
for(int i=31;i>=0;i--){
map.clear();
for(int num:nums)
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.如果某个数的末尾是01，则-1会比较快

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

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

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].

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.

## 分析

/*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;
}
};


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


/*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;
}
};


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

## 分析

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;
}
};


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"


## 分析

0000 0000 0000 0000 0000 0000 0000 0011


1111 1111 1111 1111 1111 1111 1111 1100


1111 1111 1111 1111 1111 1111 1111 1101


0xfffffffd


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;
}
};


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