Classification brush algorithm, persist, progress!
Line reference: github.com/chefyuan/al…
Hi, I’m the third person who has trouble solving problems, and in this video we’re going to do some very interesting degree problems, and they all have the same kind of very clever solutions.
What is the solution? Read on!
Basic knowledge of
Before we begin, we’d better understand some of the basics of bit operations.
The original reverse complement
First, briefly, source code, inverse code, complement.
The binary representation of a number in a computer is called the machine number of that number. Machine numbers are signed. In a computer, the highest bit of a number is used to store the symbol. Positive numbers are 0 and negative numbers are 1.
For example, the number +3 in decimal is 00000011 if the computer word length is 8 bits. If it’s negative 3, it’s 10000011.
- The original code
The source code is the sign bit plus the absolute value of the truth value, that is, the first bit represents the sign and the remaining bits represent the value. For example, if it is 8-bit binary:
[+1] = 0000 0001
[-1] Original = 1000 0001
- Radix-minus-one complement
The inverse of a positive number is itself
The inverse of a negative number is based on its original code, the sign bit is unchanged, the rest of the bits are inverse.
[+1] = [00000001] Original = [00000001] Negative
[-1] = [10000001] Original = [11111110] negative
- complement
The complement of a positive number is itself
The complement of a negative number is based on its original code, the sign bits remain unchanged, the other bits are reversed, and finally +1.
[+1] = [00000001] Original = [00000001] Inverse = [00000001] Complement
[-1] = [10000001] Original = [11111110] inverse = [11111111] complement
Complement is an unintuitive representation of the human brain. It was invented to allow machines to handle addition operations in a consistent way.
For more information, please read j Computer Composition Principles.
And or not xOR operation
When working with integer values, the bitwise operator operates directly on the bits that make up the integer value. These bitwise operators work in bit mode. A operators include: &, |, ~ ^
- And (&)
The corresponding bits are all 1, the result is 1, otherwise the result is 0
int a=129;
int b=128;
System.out.println("Results of A and B:"+(a&b)); Output a and b:128
Copy the codeThe calculation process is as follows:
10000001 &
10000000 =
10000000
Copy the code- Or (|)
If one of the corresponding bits is 1, the result is 1, otherwise it is 0
int a=129;
int b=128;
System.out.println("The result of A or B:"+(a|b)); Print a or b as follows:129
Copy the codeThe calculation process is as follows:
10000001 |
10000000 =
10000001
Copy the code- Not (~)
Bit 0, result 1; Bit is 1, so it’s 0
int a = 8;
System.out.println("Non-a result:"+(~a)); Output non-a results: -9
Copy the codeThe calculation process is as follows
//8 is converted to binary
1000
// Complement symbol bit
01000
/ / the not
10111(complement)// Convert the source code to divide the symbol bit by the inverse +1
11001
Copy the code- Xor (^)
The corresponding bit is the same, the result is 0, otherwise the result is 1
1111 ^
0010 =
1101
Copy the codeA shift
A shift, as the name implies, is a binary shift, and we are only talking about shifts of ints.
- << left-shift operator
The complement of the value is moved several bits to the left, the sign bit and the high position are discarded, and the low position is filled with 0.
- >> Right shift operator
The complement of the value is shifted several bits to the right, and the sign bit remains unchanged.
If int is an 8-bit binary, two examples are as follows:
10’s complement is 0000 1010. Move one bit to the left becomes 20 (0001 0100) and move one bit to the right becomes 5 (0000 0101).
5’s complement is 0000 0101, move one bit to the left becomes 10 (0000 1010), move one bit to the right becomes 2 (0000 0010)
Degree problem
LeetCode136. A number that occurs only once
☕ Title: 136. Numbers that only appear once (leetcode-cn.com/problems/si…)
❓ Difficulty: Simple
📕 description:
Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.
Description:
Your algorithm should have linear time complexity. Can you do it without using extra space?
💡 ideas:
Hash method
Use a hash table to store the number of occurrences of each element, and finally find the element that occurs once.
The code is as follows:
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
// Store the number of occurrences of the element
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
// Iterate over the case of occurrence 1
for (int k : map.keySet()) {
if (map.get(k) == 1) {
returnk; }}return -1;
}
Copy the code⏰ Time complexity: O(n)
🏠 Space complexity: O(n)
An operation
The space complexity O(1) is required, and the hash method is obviously not required.
Here’s an entirely new approach: bitwise operations.
Xor operation has the following characteristics:
- A number and a zero
Exclusive orThe operation is equal to itself: A ⊕0 = a - A number and itself
Exclusive orThe operation is equal to 0: A ⊕ A = 0 Exclusive orThe operation satisfies the commutative and associative laws: A ⊕ B ⊕ A = (a⊕ A)⊕ B = 0⊕ B = B
You can use xor over and over again, xor all the elements of the array, and the last one left is the element that appears only once.
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
// Xor
ans ^= nums[i];
}
return ans;
}
Copy the code⏰ Time complexity: O(n)
🏠 Space complexity: O(1)
LeetCode137. Number II that occurs only once
☕ Title: 137. Numbers that occur only once II (leetcode-cn.com/problems/si…)
❓ Difficulty: medium
📕 description:
Given an array of integers, nums, each element appears exactly ** three times, except for an element that appears only once. ** Please find and return the element that appears only once.
This is the same as the number of occurrences in the array Offer 56-ii.
💡 ideas:
Hash method
The first reaction is hashing, so I don’t have to say much, but I’ll just go to the code:
public int singleNumber(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
for (int k : map.keySet()) {
if (map.get(k) == 1) {
returnk; }}return -1;
}
Copy the code⏰ Time complexity: O(n)
🏠 Space complexity: O(n)
An operation
All right, it’s time for our hero again.
Add each of the binary bits of our number and mod 3 with the sum of each bit:
What is the principle?
If all the other numbers have 3 occurrences and only the target number has 1 occurrence, then each 1 can have one of these two occurrences,
- Is a multiple of 3.
- Multiple of 3 +1 (including the number that occurs once)
This multiple of 3 plus 1 is the digit we’re aiming for.
The code is as follows:
public int singleNumber(int[] nums) {
int res = 0;
for (int i = 0; i < 32; i++) {
int count = 0;
for (int num : nums) {
// Check if the I bit is 1
if ((num >> i & 1) = =1) { count++; }}if (count % 3! =0) {
// Set bit I to 1
res = res | 1<< i; }}return res;
}
Copy the code🚗 Time complexity: O(n)
🏠 Space complexity: O(1)
LeetCode260. The number III that occurs only once
☕ Title: 260. Numbers that occur only once III (leetcode-cn.com/problems/si…)
❓ Difficulty: medium
📕 description:
Given an integer array nums, exactly two elements appear only once, and all the rest appear twice. Find the two elements that appear only once. You can return the answers in any order.
The number of occurrences in the array Offer 56-i is the same as the number of occurrences in the array Offer 56-i.
💡 ideas:
This time it’s not one repeating element, it’s two. Let’s start with our simple hashing.
Hash method
The code is as follows:
public int[] singleNumber(int[] nums) {
int[] res = new int[2];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
int index = 0;
for (int k : map.keySet()) {
if (map.get(k) == 1) { res[index] = k; index++; }}return res;
}
Copy the code🚗 Time complexity: O(n)
🏠 Space complexity: O(n)
Bit operations [5]
We found the one-occurrence number in LeetCode136 with only one xor.
What about this problem?
If only we could split it into two groups.
How do you divide it?
We all know that xor has the same bit, so it’s 0, otherwise it’s 1
We can divide an array into two groups based on whether one of the digits is a 0 or a 1.
For example arrays: [12,13,14,17,14,12]
The xOR result is 13^17.
The packet bits are found.
So how do you group by grouping bits?
The xOR value of 13 and 17 can retain only the packet bits of the xor value and change the rest bits to 0. For example, 11100 becomes 00100.
Why do you do that? As mentioned in the second question, we can determine whether the last bit of A is 0 or 1 according to a & 1, so after changing 11100 to 00100, the elements x & 001 can group x.
So how do we keep only the packet bits, and the rest of the bits go to zero?
I can use x minus x to keep the 1 on the right-hand side.
The code is as follows:
public int[] singleNumber(int[] nums) {
int bitMask = 0;
// All elements in the array are xor once
for (int num : nums) {
bitMask ^= num;
}
// Keep the rightmost 1
bitMask &= -bitMask;
int[] res = {0.0};
for (int num : nums) {
// Divide the array into two parts, each xor separately
if ((num & bitMask) == 0) {
res[0] ^= num;
} else {
res[1] ^= num; }}return res;
}
Copy the codeconclusion
And we’re done with the triple degree problem.
The simplest way to solve the degree problem is the Hash method, which stores the number of occurrences of an element using a Hash.
But the Hash method is O(n), not O(1).
At this time, we should use the method of bit operation flexibly. The key of bit operation is to fully understand the relevant application of bit operation.
Do simple things repeatedly, do repetitive things carefully, and do serious things creatively.
Like, pay attention to not get lost, let’s see you next time!
Reference:
[1]. Github.com/chefyuan/al…
[2]. Leetcode-cn.com/problems/si…
[3]. Blog.csdn.net/White_Idiot…
[4]. Blog.csdn.net/qq_30374549…
[5]. Leetcode-cn.com/problems/si…
[6]. www.cnblogs.com/zhangziqiu/.