Have you done these problems before?
In the preparation process of interview, brush algorithm is a required course, of course, I am no exception. One day, I got a magical title:
# 136. A number that appears only onceGiven an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once. Note: Your algorithm should have linear time complexity. Can you do it without using extra space? Example 1: input: [2, 2, 1] output: 1 example 2: input:,1,2,1,2 [4] output: 4Copy the codeI can not help but frown, heart said, this is not simple, three five in addition to two write down the following code:
/**
* HashMap
*
* @param* nums array@returnResults the * /
public int solution(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.remove(num);
} else {
map.put(num, 1); }}return map.entrySet().iterator().next().getKey();
}
Copy the codeThen I saw another title:
# 137. Number II that occurs only onceGiven an array of non-empty integers, every element appears three times except one. Find the element that appears only once. Note: Your algorithm should have linear time complexity. Can you do it without using extra space? Example 1: input:,2,3,2 [2] output: 3 example 2: input:,1,0,1,0,1,99 [0] output: 99Copy the codeI could not help but frown again, heart said, as if it is the same routine, then wrote the following code:
/** * Use Map to store keys and occurrences **@param* nums array@returnThe number that appears once */
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1); }}for (Integer key : map.keySet()) {
if (map.get(key) == 1) {
returnkey; }}return 0;
}
Copy the codeThen comes the final question:
# 260. The number III that occurs only onceGiven an integer array nums, exactly two elements appear only once, and all the rest appear twice. Find the two elements that appear only once. Example: input: [1,2,1,3,2,5] output: [3,5] note: 1. The order in which the results are printed does not matter; for the example above, [5, 3] is also the correct answer. 2. Your algorithm should have linear time complexity. Can you do this using just constant space complexity?Copy the codeI could not help but frown again, heart said, HMM… Then write the following code:
/** * Use Map to store keys and occurrences **@param* nums array@returnAn array of numbers that appear once */
public int[] singleNumber(int[] nums) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1); }}int i = 0;
for (Integer key : map.keySet()) {
if (map.get(key) == 1) { result[i] = key; i++; }}return result;
}
Copy the codeWith almost the same idea to do three questions, I have to praise myself:
After completing all three problems and submitting their answers, only 10% of the solvers took time to execute and consumed more memory. I couldn’t help frowning (I finally knew why I had such a deep forehead line), realizing that things are not so simple…
Then I looked for other solutions, as follows:
/** * #136 The time complexity must be O(n), and the space complexity must be O(1), so the sorting method cannot be used, and the map data structure cannot be used. The answer is to use the Bit Operation to solve the problem. A [1] ⊕ A [2] ⊕ A [3] ⊕... ⊕ a[n], the result is the number that occurs only once, with time complexity O(n). * By the nature of xOR any number xor itself is equal to 0 * *@param* nums array@returnResults the * /
private int solution(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
Copy the code /** * # We'll explain this in more detail * * here we use xor, and, and inverse operations * *@param* nums array@returnThe number that appears once */
public int singleNumber2(int[] nums) {
int a = 0, b = 0;
int mask;
for (int num : nums) {
b ^= a & num;
a ^= num;
mask = ~(a & b);
a &= mask;
b &= mask;
}
return a;
}
Copy the code /** * #260 If all elements are xOR, then the result is xOR of the two elements that occur only once. * Then, since the two elements that occur only once must be different, the binary form of the two elements must have at least one bit different, namely, one is 0 and the other is 1, and now we need to find that bit. * The xOR property is that any number xor itself is equal to 0, so any 1 bit in the binary form of this number is the one we're looking for. * Then divide the n elements of the array into two parts based on whether the digit is 1 or 0. * 1. Xor all elements with the digit 0, resulting in a number that occurs only once * 2. By xor of all the elements with the 1 digit, you get another one of those numbers that only appear once. * And that will solve the problem. Ignoring the process of finding different bits, the number group is traversed twice in total, with time complexity of O(n). * * uses the bit operation * *@param* nums array@returnAn array of numbers */ that appears only once
public int[] singleNumber2(int[] nums) {
int diff = 0;
for (int num : nums) {
diff ^= num;
}
// Get the least significant bit, i.e. the one in which the two numbers differ
diff &= -diff;
int[] result = new int[2];
for (int num : nums) {
if ((num & diff) == 0) {
result[0] ^= num;
} else {
result[1] ^= num; }}return result;
}
Copy the codeAfter reading the above solution, I can only think of the existence of the question mark, what does it mean? !
Let’s take a quick look at bit operations and parse these three problems.
A quick introduction to bit operations
1. Xor operation (^)
The xOR logical relation is: when AB is different, P=1; When AB is the same, P is equal to 0. “⊕” is an xor mathematical operation symbol. Xor logic is also A combination of and or non-logic. Its logical expression is: P=A⊕B. In computer language, the symbol for xor is ^.
The truth table of the xOR operation A ⊕ B is as follows:
| A | B | The radius |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | F |
So we know from #136 that by xor, two identical elements result in 0, and any xor operation with 0 results in itself.
2. And operation (&)
“And” operation is a basic logical operation in the computer, the symbol is “&”, the two data to participate in the operation, according to the binary “and” operation. Operation rules: 0&0=0; 1 = 0 0 &; 1 & 0 = 0; 1 &1 = 1; That is, the result is 1 only when both digits are 1. Otherwise, the result is 0. In addition, negative numbers participate in bitwise and operations in the form of complement.
The truth table for and operations A & B is as follows:
| A | B | & |
|---|---|---|
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
Special uses of “and operation” :
-
Reset. If you want to zero a cell, even if all of its binary bits are zero, if you combine it with a value where all bits are zero, the result is zero.
-
Takes the specified bit of a number
Method: find a number that corresponds to the bits to be taken by X. The corresponding bits of this number are 1 and the rest bits are zero. Perform “and operation” on this number and X to obtain the specified bits in X. Example: let X=10101110, take the lower 4 bits of X, use X & 0000 1111 = 0000 1110 can be obtained; It can also be used to pick the second, fourth, and sixth bits of X.
(3) or (|) operation
Two objects that participate in the operation are “or” in binary bits. Algorithm: 0 | 0 = 0; 0 | 1 = 1; 1 | 0 = 1; 1 | 1 = 1; That is, as long as one of the two objects in the operation is 1, its value is 1. In addition, negative numbers participate in bitwise or operations in the form of complement.
Or operation of A | B truth table is as follows:
| A | B | | |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
Or operation “special function:
-
Commonly used for some position of a data 1.
Method: Find a number that corresponds to the 1 bit of X. The corresponding bits of this number are 1 and the remaining bits are zero. This number phase with X may make certain positions in X 1.
Example: X = 10100000 low four set to 1, with X | 0000 1111 = 1010, 1111.
4. Reverse operation (~)
A piece of data that participates in an operation and is “inverted” by binary bits. Operation rule: ~1=0; ~ 0 = 1; That is, a binary number is reversed by bits, that is, 0 becomes 1, and 1 becomes 0.
If the lowest point of a number is zero, it can be expressed as: A &~1. The value of ~1 is 111111111111111110. Press and to calculate the value. The lowest value of the value must be 0. The ~ operator takes precedence over arithmetic, relational, logical, and other operators.
OK, so now that we’ve done the bit operations that we used in the three problems, let’s insert the detailed solution to #137.
public int singleNumber2(int[] nums) {
// Let's change the variable name here
// Use one to record the number of bits in binary 1 that appear "1 time" (1 after mod 3) until the current element is processed;
// Use two to record the number of bits in binary 1 that appear "twice" (2 after mod 3) up to the currently calculated variable.
int one = 0, two = 0;
int mask;
for (int num : nums) {
// Since two needs to consider the existing state of one and whether the current state continues to appear. So we have to do it first
two ^= one & num;
// one is a binary bit of 0,1, alternating between two states
one ^= num;
// If one of the two bits is 1 at the same time, 1 appears three times in the binary bit.
mask = ~(one & two);
// Clear zero
one &= mask;
two &= mask;
}
// Use binary to simulate ternary operations. In the end one records the end result.
return one;
}
Copy the codeLet’s start with a relatively simple problem. If we add 0 and 1 to the input array, we need to count the number of occurrences of 1. When we encounter 1, we increase the number by 1; when we encounter 0, it stays the same. We can do this counting with m bits, that is, xm, xm−1… X1, we just need to make sure 2m > k. The next question we need to consider is what operation to do in each check element to satisfy the above conditions. Before starting the count, each count bit initializes bit 0, and then iterates through nums until it hits the first 1, at which point x1 becomes 1, and continues through until it hits the second 1, at which point x1=0, x2=1, until you should see the pattern here. For each 1 encountered, for Xm, xm−1… X1 only changes its value if all the previous bits are 1, if it was 1, it becomes 0, if it was 0, it becomes 1, and if it’s 0, it stays the same. Once you understand this logic, it’s easy to write expressions. Here is Java code with m = 3 as an example:
for(int num: nums) {
x3 ^= x2 & x1 & num;
x2 ^= x1 & num;
x1 ^= num;
// other operations
}
Copy the codeBut we haven’t solved the problem that when we get to k of 1, the count has to go back to 0, so all the count bits have to go to 0. The solution is also more subtle.
Suppose we have a sign variables, only when the count value to k this flag variable to 0, and the remaining cases are 1, then every element when the check for each count and mark do with operating variables, so if the logo variable is 0, that is, when the count value for k, all will become 0, on the other hand, All the bits stay the same, and we’re done.
Ok, the last question is how to calculate the value of the flag variable. To convert k to binary, only when the count value reaches K, will all the count bits be the same as the binary of K. Therefore, only the binary bits of K need to be combined and operated. If a bit is 0, the sum operation will be performed with the value after the inverse of the bit.
For example, k=3, m=2, the Java code is as follows:
// where yj = xj if kj = 1,
// and yj = ~xj if kj = 0,
// k1, k2 is the binary representation of k (j = 1 to 2).
mask = ~(y1 & y2);
x2 &= mask;
x1 &= mask;
Copy the codePut these two pieces together and you have a complete algorithm for solving this problem.
5. Left-shift operator (<<)
To move all bits of an operand to the left (discarding the left bits and adding zeros to the right).
Example: a = a<< 2 move the binary bits of A 2 bits to the left, add 0 to the right, move 1 bit to the left and a = A *2;
If the left position does not contain a 1, then each left position is equal to multiplying that number by 2.
The integers in this code are 32-bit integers, so if they are negative, binary means their length is 32:
/** * << indicates left shift. If the number is positive, 0 is added at the lower level; if it is negative, 1 is added at the lower level. For example, 5<<2 means that the binary bit of 5 is moved two places to the left, and the binary bit of 5 is 0000 0101. Therefore, 101 is moved two places to the left, which is 0001 0100 */
@Test
public void leftShiftTest(a) {
int number1 = 5;
System.out.println("The decimal number before left-shifting is:" + number1);
System.out.println("The binary number before left-shifting is:" + Integer.toBinaryString(number1));
int number2 = number1 << 2;
System.out.println("Left-shifted decimal number is:" + number2);
System.out.println("The binary number shifted left is:" + Integer.toBinaryString(number2));
System.out.println();
int number3 = -5;
System.out.println("The decimal number before left-shifting is:" + number3);
System.out.println("The binary number before left-shifting is:" + Integer.toBinaryString(number3));
int number4 = number3 << 2;
System.out.println("Left-shifted decimal number is:" + number4);
System.out.println("The binary number shifted left is:" + Integer.toBinaryString(number4));
}
Copy the codeThe results are as follows:
The decimal number before the left shift is as follows: 5 The binary number before the left shift is as follows: 101 The decimal number after the left shift is as follows: 20 The binary number after the left shift is as follows: 10100 The decimal number before the left shift is as follows: -5 The binary number before the left shift is as follows: Left after the decimal number is: 11111111111111111111111111111011-20 left after the binary number is: 11111111111111111111111111101100Copy the code6. Right shift operator (>>)
>> represents right shift, which means that all binary bits of a number are moved several bits right. Positive numbers are left supplemented with 0, negative numbers are left supplemented with 1, and the right is discarded. Every time the operand moves one bit to the right, it is equal to dividing the number by 2.
>>> indicates an unsigned right shift, also known as a logical right shift, that is, if the number is positive, then 0 is added to the high level, and if the number is negative, then 0 is added to the high level after the right shift.
For example, if a = a >> 2, move the binary bits of A to the right by 2 bits, and complement 0 or 1, depending on whether the number of bits shifted is positive or negative.
The integers in this code are 32-bit integers, so if they are negative, binary means their length is 32:
@Test
public void rightShift(a) {
int number1 = 10;
System.out.println("The decimal number before the right shift is:" + number1);
System.out.println("The binary number before right shift is:" + Integer.toBinaryString(number1));
int number2 = number1 >> 2;
System.out.println("The right-shifted decimal number is:" + number2);
System.out.println("The binary number shifted to the right is:" + Integer.toBinaryString(number2));
System.out.println();
int number3 = -10;
System.out.println("The decimal number before the right shift is:" + number3);
System.out.println("The binary number before right shift is:" + Integer.toBinaryString(number3));
int number4 = number3 >> 2;
System.out.println("The right-shifted decimal number is:" + number4);
System.out.println("The binary number shifted to the right is:" + Integer.toBinaryString(number4));
System.out.println("* * * * * * * * * * * * * * * * * * * * * * * logic moves to the right * * * * * * * * * * * * * * * * * * * * * *");
int a = 15;
System.out.println("The decimal number before the logical right shift is:" + a);
System.out.println("The binary number before the logical right shift is:" + Integer.toBinaryString(a));
int b = a >>> 2;
System.out.println("Logical right-shifted decimal number is:" + b);
System.out.println("The logical right-shifted binary number is:" + Integer.toBinaryString(b));
System.out.println();
int c = -15;
System.out.println("The decimal number before the logical right shift is:" + c);
System.out.println("The binary number before the logical right shift is:" + Integer.toBinaryString(c));
int d = c >>> 2;
System.out.println("Logical right-shifted decimal number is:" + d);
System.out.println("The logical right-shifted binary number is:" + Integer.toBinaryString(d));
}
Copy the codeThe results are as follows:
Moves to the right in front of the decimal number is: 10 moves to the right in front of the binary number is: 1010 moves to the right after the decimal number is: after 2 moves to the right of the binary number is: 10 moves to the right in front of the decimal number is: - 10 moves to the right in front of the binary number is: 11111111111111111111111111110110 moves to the right after the decimal number is: - 3 moves to the right after the binary number is: 11111111111111111111111111111101 * * * * * * * * * * * * * * * * * * * * * * * logic moves to the right * * * * * * * * * * * * * * * * * * * * * * logic moves to the right in front of the decimal number is: 15 The binary number before the logical right shift is: 1111 The decimal number after the logical right shift is: 3 The binary number after the logical right shift is: 11 The decimal number before the logical right shift is: -15 The binary number before the logical right shift is: 11111111111111111111111111110001 logic moves to the right after the decimal number is: 1073741820 logic moves to the right after the binary number is: 111111111111111111111111111100Copy the codeconclusion
The above is our common several bit operations, including left shift, right shift and other operations, in the source code of HashMap will often see, understanding these bit operations, for understanding the source code is also a certain help, of course, will help us write more efficient code.
Can be seen from the above partial sample, an operation is usually used to reduce contains permutation, count the operation of the high complexity, such as, of course, also can be used instead of by 2 except for 2, judge a prime number, even number, the basic operation, such as multiple but I think its significance lies in the former, which is counter to reduce the complexity of the design to arrange or count.
#136, #260, #137 Single Number II, #136 Single Number II, #136 Single Number II, #136 Single Number II, #136 Single Number II, #136 Single Number II, #136 Single Number II
The above is my personal summary. If there are any flaws or mistakes, please point them out and correct them.
Reference:
- Leetcode Single Number problem summary
- LeetCode–# 136 appears only once
- Leetcode –#137 Single Number II
- #137 SingleNumber II discuss