And & amp; operation
The AND operation is when two binary numbers are compared, if they are both 1, it is 1, and as long as 0 is encountered, it is 0.
Perform AND operation as follows: 2 and 5
Then the binary system of 2 is 10, and the binary system of 5 is 101
When it encounters 0, it is 0, and when both are 1, it is 1
OR | operation
The OR operation means that when 1 is encountered, it is 1, as follows:
The binary number of 10 is 1010, the binary number of 5 is 0101, and the comparison between the top and bottom is 1111
When 12 | 5, the upper and lower parts are both 0, so it is 0.
XOR operation^
The XOR operation is 0 when they are the same, and 1 when they are different.
Left shift<
rule:
The vacant bits on the right are filled with 0s
If the high bit shifts to the left and overflows, the high bit is discarded.
Example:
The meaning of this figure is that binary 101 is shifted one position to the left, then binary 101 is 5 in decimal.
Shifting one bit to the left means padding zeros on the right. This picture is the result of shifting one position to the left, which is 10 in decimal. Being such a smart person, you will quickly discover that the rule is correct. Shift left by one decimal place and multiply by 2. The principle is that your original binary bit is shifted one bit to the left, which is equivalent to multiplying by 2, so the decimal number is also multiplied by 2.
Right shift>>operation
rule:
The vacant bits on the left are filled with 0 or 1. Positive numbers are padded with 0s and negative numbers are padded with 1s.
If the low bit shifts to the right and overflows, the bit will be discarded.
Example:
This picture is binary 10101 shifted right by 1 bit
After shifting one position to the right, it becomes binary 1010. In the same way, shifting it to the right one decimal place divides it by 2 and rounds down. (Because the last 1 is gone after it is moved to the right)
So, some people will start to wonder? What can these do?
For example, there are algorithm questions in leetcode.
Algorithm questions using bit operations
Numbers that appear only once
Explanation of the question: There are several numbers in the array, but one number only appears once, and the rest of the numbers appear twice.
Method 1: Use hash table or set
Using a hash table, create a hash table to store the number of times each number appears, and then loop to find the number of times it appears as 1.
But the question states that extra space cannot be used, so Method 1 passes.
Method 2: Use bit operations
For this question, you can use the XOR operation. The XOR operation has the following three properties.
If any number is XORed with 000, the result will still be the original number, that is, a^0=a
If any number is XORed with itself, the result is 000, that is, a^a=0
The XOR operation satisfies the commutative law and associative law, that is, a^b^a=b^a^a=b^(a^a)=b^0=b
Therefore, applying this XOR relationship can produce that once two numbers are the same, they can be directly equal to 0;
The title clearly states that if there is only one number, it will only appear once, and the other numbers will appear twice. Therefore, all numbers will be XORed, and only a single number will be left in the end.
int singleNumber(vector<int> & amp; nums) {
int ans = 0;
for(auto & amp;num : nums) //Can loop through the numbers in the nums array
{
ans ^= num; //XOR the numbers in each cycle
}
return ans;
}
Complexity Analysis
-
Time complexity: O(n), where n is the array length. The array only needs to be traversed once.
-
Space complexity: O(1).
Rings and rods
Today’s leetcode daily question is this. It is a simple question and you can use hash tables or bit operations.
To briefly explain the meaning of this question, it means that there are ten poles, and each pole can store rings of different colors. When a pole has red = ‘R’, blue = ‘ B’, green = ‘G’ The rings of three colors are accumulated once, as shown in the figure.
Bit operations
Before using bit operations to solve this problem, let’s review the << left shift operator, which can shift the binary to the left by n bits.
Then using this feature, we can move 26 letters to the left multiple times. For example, if A is moved 0 times, it is represented as 1 in binary, B is moved once, and moved left once is 10, and so on. Each letter has a corresponding binary representation.
| operation means that when 1 is encountered, it is 1, then we can use this feature, for example, the original mark is 0
Then mark = 0 | 100 (C) is 100, then mark = 100 | 010 (B), and the final answer of mark is 110, which is BC.
Then we can store the binary of R G B in a variable mark in advance
int mark = 0;
mark |= 1 << 'R' - 'A'; // Move ASCII to determine the number of left shifts. For example, 'R' in ASCII code is 82, minus 65 of 'A', that is 17, then the binary number of 1 is shifted to the left 17 times.
mark |= 1 << 'G' - 'A'; //The function of |= here is to store the binary into mark every time.
mark |= 1 << 'B' - 'A';
Next is the overall idea. We can use an array deposit with a length of 10 to represent the color of the ring on each rod, where deposit [i] represents the color of the ring on the i-th rod. If there is For red, green, and blue rings, their binary will be the same as mark.
We traverse the string rings, rings[i + 1] represents the number of the rod where the ring is located, and rings[i] represents the color of the ring. We put the ring into the deposit array.
Finally, we count the number of deposit median values that are the same as the mark elements, which is the number of rods that collect all three color rings.
The final code is as follows:
int countPoints(string rings) {
vector <int> deposit(10);
int mark = 0;
mark |= 1 << 'R' - 'A';
mark |= 1 << 'G' - 'A';
mark |= 1 << 'B' - 'A';
for(int i = 0;i<rings.size();i + = 2)
{
deposit[rings[i + 1] - '0'] |= 1 << rings[i] -'A';
}
int ans = 0;
for(auto & amp; tmp : deposit)
{
if(tmp == mark)
{
ans + + ;
}
}
return ans;
}
Complexity Analysis
-
Time complexity: O(n), where n is the array length.
-
Space complexity: O(m). m represents the size of the character set
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57209 people are learning the system
rule:
The vacant bits on the right are filled with 0s
If the high bit shifts to the left and overflows, the high bit is discarded.
Example:
The meaning of this figure is that binary 101 is shifted one position to the left, then binary 101 is 5 in decimal.
Shifting one bit to the left means padding zeros on the right. This picture is the result of shifting one position to the left, which is 10 in decimal. Being such a smart person, you will quickly discover that the rule is correct. Shift left by one decimal place and multiply by 2. The principle is that your original binary bit is shifted one bit to the left, which is equivalent to multiplying by 2, so the decimal number is also multiplied by 2.
Right shift>>operation
rule:
The vacant bits on the left are filled with 0 or 1. Positive numbers are padded with 0s and negative numbers are padded with 1s.
If the low bit shifts to the right and overflows, the bit will be discarded.
Example:
This picture is binary 10101 shifted right by 1 bit
After shifting one position to the right, it becomes binary 1010. In the same way, shifting it to the right one decimal place divides it by 2 and rounds down. (Because the last 1 is gone after it is moved to the right)
So, some people will start to wonder? What can these do?
For example, there are algorithm questions in leetcode.
Algorithm questions using bit operations
Numbers that appear only once
Explanation of the question: There are several numbers in the array, but one number only appears once, and the rest of the numbers appear twice.
Method 1: Use hash table or set
Using a hash table, create a hash table to store the number of times each number appears, and then loop to find the number of times it appears as 1.
But the question states that extra space cannot be used, so Method 1 passes.
Method 2: Use bit operations
For this question, you can use the XOR operation. The XOR operation has the following three properties.
If any number is XORed with 000, the result will still be the original number, that is, a^0=a
If any number is XORed with itself, the result is 000, that is, a^a=0
The XOR operation satisfies the commutative law and associative law, that is, a^b^a=b^a^a=b^(a^a)=b^0=b
Therefore, applying this XOR relationship can produce that once two numbers are the same, they can be directly equal to 0;
The title clearly states that if there is only one number, it will only appear once, and the other numbers will appear twice. Therefore, all numbers will be XORed, and only a single number will be left in the end.
int singleNumber(vector<int> & amp; nums) {
int ans = 0;
for(auto & amp;num : nums) //Can loop through the numbers in the nums array
{
ans ^= num; //XOR the numbers in each cycle
}
return ans;
}
Complexity Analysis
-
Time complexity: O(n), where n is the array length. The array only needs to be traversed once.
-
Space complexity: O(1).
Rings and rods
Today’s leetcode daily question is this. It is a simple question and you can use hash tables or bit operations.
To briefly explain the meaning of this question, it means that there are ten poles, and each pole can store rings of different colors. When a pole has red = ‘R’, blue = ‘ B’, green = ‘G’ The rings of three colors are accumulated once, as shown in the figure.
Bit operations
Before using bit operations to solve this problem, let’s review the << left shift operator, which can shift the binary to the left by n bits.
Then using this feature, we can move 26 letters to the left multiple times. For example, if A is moved 0 times, it is represented as 1 in binary, B is moved once, and moved left once is 10, and so on. Each letter has a corresponding binary representation.
| operation means that when 1 is encountered, it is 1, then we can use this feature, for example, the original mark is 0
Then mark = 0 | 100 (C) is 100, then mark = 100 | 010 (B), and the final answer of mark is 110, which is BC.
Then we can store the binary of R G B in a variable mark in advance
int mark = 0; mark |= 1 << 'R' - 'A'; // Move ASCII to determine the number of left shifts. For example, 'R' in ASCII code is 82, minus 65 of 'A', that is 17, then the binary number of 1 is shifted to the left 17 times. mark |= 1 << 'G' - 'A'; //The function of |= here is to store the binary into mark every time. mark |= 1 << 'B' - 'A';
Next is the overall idea. We can use an array deposit with a length of 10 to represent the color of the ring on each rod, where deposit [i] represents the color of the ring on the i-th rod. If there is For red, green, and blue rings, their binary will be the same as mark.
We traverse the string rings, rings[i + 1] represents the number of the rod where the ring is located, and rings[i] represents the color of the ring. We put the ring into the deposit array.
Finally, we count the number of deposit median values that are the same as the mark elements, which is the number of rods that collect all three color rings.
The final code is as follows:
int countPoints(string rings) {
vector <int> deposit(10);
int mark = 0;
mark |= 1 << 'R' - 'A';
mark |= 1 << 'G' - 'A';
mark |= 1 << 'B' - 'A';
for(int i = 0;i<rings.size();i + = 2)
{
deposit[rings[i + 1] - '0'] |= 1 << rings[i] -'A';
}
int ans = 0;
for(auto & amp; tmp : deposit)
{
if(tmp == mark)
{
ans + + ;
}
}
return ans;
}
Complexity Analysis
-
Time complexity: O(n), where n is the array length.
-
Space complexity: O(m). m represents the size of the character set
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57209 people are learning the system