# LeetCode Integer Replacement

LeetCode 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. 如果n是偶数，把n变成n/2
2. 如果n是奇数，把n变成n+1或者n-1

class Solution {
private:
struct P {
long long val;
int step;
P(long long v_, int s_) :val(v_), step(s_) {};
};
public:
int integerReplacement(int n) {
P p(n, 0);
queue<P> qp;
qp.push(p);
while (!qp.empty()) {
P f = qp.front();
qp.pop();
if (f.val == 1)return f.step;
else if (f.val & 1) {
qp.push(P(f.val + 1, f.step + 1));
qp.push(P(f.val - 1, f.step + 1));
}
else {
qp.push(P(f.val / 2, f.step + 1));
}
}
return 0;
}
};


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


# hihoCoder 1496-寻找最大值

hihoCoder 1496-寻找最大值

### 输出

2
3
1 2 3
4
1 2 4 5

12
80

#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<algorithm>
#include<functional>
#include<vector>
#include<climits>
#include<cfloat>
using namespace std;
typedef long long LL;
vector<LL> nums(100005, 0);
int main() {
//freopen("input.txt", "r", stdin);
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
LL first = LLONG_MIN, second = LLONG_MIN, third = LLONG_MIN;
for (int i = 0; i < n; ++i) {
scanf("%d", &nums[i]);
if (nums[i] > first) {
third = second;
second = first;
first = nums[i];
}
else if (nums[i] > second) {
third = second;
second = nums[i];
}
else if (nums[i] > third) {
third = nums[i];
}
}
LL ans = max(first*second*(first&second), first*third*(first&third));
ans = max(ans, second*third*(second&third));
printf("%lld\n", ans);
}
return 0;
}


# LeetCode Maximum XOR of Two Numbers in an Array

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

• 0^0=0 | 0=0^0
• 0^1=1 | 0=1^1
• 1^0=1 | 1=0^1
• 1^1=0 | 1=1^0

class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int ans = 0, mask = 0;
for (int i = 31; i >= 0; --i) {
unordered_set<int> hash;
for (const auto& num : nums) {
}
int tmpmax = ans | (1 << i);
for (const auto& prefix : hash) {
if (hash.find(prefix ^ tmpmax) != hash.end()) {
ans = tmpmax;
break;
}
}
}
return ans;
}
};


# LeetCode Maximum Product of Word Lengths

LeetCode 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) {
int ans = 0;
for (int i = 0; i < words.size(); ++i) {
for (int j = 0; j < words[i].size(); ++j) {
mask[i] |= 1 << (words[i][j] - 'a');
}
for (int k = 0; k < i; ++k) {
ans = max(ans, int(words[i].size()*words[k].size()));
}
}
return ans;
}
};


# LeetCode Bitwise AND of Numbers Range

LeetCode 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) {
int offset = 0;
while (m != n) {
m >>= 1;
n >>= 1;
++offset;
}
return m << offset;
}
};


# LeetCode Repeated DNA Sequences

LeetCode Repeated DNA Sequences
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"].

class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> ans;
unordered_map<string, int> hash;
for (size_t i = 0; i + 10 <= s.size(); ++i) {
string seq = s.substr(i, 10);
++hash[seq];
if (hash[seq] == 2)ans.push_back(seq);
}
return ans;
}
};


class Solution {
private:
unsigned int encode(const string &s) {
unsigned int code = 0;
for (size_t i = 0; i < s.size(); ++i) {
code <<= 2;
switch (s[i]) {
case 'A':code += 0; break;
case 'T':code += 1; break;
case 'C':code += 2; break;
case 'G':code += 3; break;
}
}
return code;
}
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> ans;
unordered_map<unsigned int, int> hash;
for (size_t i = 0; i + 10 <= s.size(); ++i) {
string seq = s.substr(i, 10);
unsigned int code = encode(seq);
++hash;
if (hash == 2)ans.push_back(seq);
}
return ans;
}
};


# LeetCode UTF-8 Validation

LeetCode UTF-8 Validation
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

1. For 1-byte character, the first bit is a 0, followed by its unicode code.
2. For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

   Char. number range  |        UTF-8 octet sequence
--------------------+---------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx


Given an array of integers representing the data, return whether it is a valid utf-8 encoding.
Note:
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.
Example 1:

data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.
Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.


Example 2:

data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.
Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

class Solution {
public:
bool validUtf8(vector<int>& data) {
vector<int> mask1 = { 0x80,0xe0,0xf0,0xf8 };
vector<int> first = { 0x0,0xc0,0xe0,0xf0 };
int mask2 = 0xc0, second = 0x80;
int i = 0, j = 0;
while (i < data.size()) {
for (j = 0; j < 4; ++j) {
if ((data[i] & mask1[j]) == first[j]) {
while (j--) {
if (++i >= data.size())return false;
if ((data[i] & mask2) != second)return false;
}
break;
}
}
if (j >= 4)return false;
++i;
}
return true;
}
};


# LeetCode Gray Code

LeetCode Gray Code
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2


Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

class Solution {
public:
void work(vector<int>& ans, unordered_set<int>& codes, int gray, int n) {
for (int i = 0; i < n; ++i) {
int new_gray = (gray&(~(1 << i))) | (~gray)&(1 << i); // flip i-th bit
if (codes.find(new_gray) == codes.end()) {
codes.insert(new_gray);
ans.push_back(new_gray);
work(ans, codes, new_gray, n);
break;
}
}
}
vector<int> grayCode(int n) {
vector<int> ans = { 0 };
if (n == 0)return ans;
unordered_set<int> codes = { 0 };
work(ans, codes, 0, n);
return ans;
}
};


class Solution {
public:
vector<int> grayCode(int n) {
vector<int> ans = { 0 };
if (n == 0)return ans;
ans.push_back(1);
for (int i = 2; i <= n; ++i) {
int sz = ans.size();
while (sz--) {
ans.push_back(ans[sz] | (1 << (i - 1)));
}
}
return ans;
}
};


# LeetCode Convert a Number to Hexadecimal

LeetCode 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"


Example 2:

Input:
-1
Output:
"ffffffff"

class Solution {
public:
string toHex(int num) {
if (num == 0)return "0";
vector<string> dict = { "0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f" };
string ans = "";
for (int i = 0; i < 8; ++i) {
if (num == 0)break;
num >>= 4;
}
return ans;
}
};


# LeetCode Total Hamming Distance

LeetCode Total Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.
Example:

Input: 4, 14, 2
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.


Note:

1. Elements of the given array are in the range of 0 to 10^9
2. Length of the array will not exceed 10^4.

• 4:  0100
• 14:1110
• 2:  0010

class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int bit_len = sizeof(int) * 8;
vector<int> one(bit_len, 0), zero(bit_len, 0);
for (int i = 0; i < bit_len; ++i) {
for (int j = 0; j < nums.size(); ++j) {
if (nums[j] & 1)++one[i];
else ++zero[i];
nums[j] >>= 1;
}
}
int ans = 0;
for (int i = 0; i < bit_len; ++i) {
ans += one[i] * zero[i];
}
return ans;
}
};