# 剑指 Offer 15. 二进制中1的个数

输入：00000000000000000000000000001011



输入：00000000000000000000000010000000



输入：11111111111111111111111111111101

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

# LeetCode XOR Operation in an Array

1486. XOR Operation in an Array

Given an integer n and an integer start.

Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length.

Return the bitwise XOR of all elements of nums.

Example 1:

Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.


Example 2:

Input: n = 4, start = 3
Output: 8
Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.

Example 3:

Input: n = 1, start = 7
Output: 7


Example 4:

Input: n = 10, start = 5
Output: 2


Constraints:

• 1 <= n <= 1000
• 0 <= start <= 1000
• n == nums.length

class Solution {
public:
int xorOperation(int n, int start) {
int ans = 0;
for (int i = 0; i < n; ++i) {
ans ^= (start + 2 * i);
}
return ans;
}
};

# 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

# hihoCoder 1496-寻找最大值

hihoCoder 1496-寻找最大值

### 输出

2
3
1 2 3
4
1 2 4 5

12
80

# 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

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

# LeetCode Bitwise AND of Numbers Range

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

Example 1:

Input: [5,7]
Output: 4


Example 2:

Input: [0,1]
Output: 0

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

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

Example:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["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[code];
if (hash[code] == 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.

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

Example 1:

Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

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


Example 2:

Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
Therefore, for n = 0 the gray code sequence is [0].

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