Directory:
- Understand how the double pointer idea works (fast and slow type and collision type)
- Understand how double pointers solve the problem of deleting elements
- Understand how dual pointers solve the odd-even movement problem
- Understand how double pointers solve array rotation problems
- Understand how pointers solve interval-related problems
- Understand how double pointers solve string substitution problems
Content:
How double pointers work
Understand how the double pointer idea works (fast and slow type and collision type)
Fast and slow pointers are a commonly used idea in arrays. They can quickly assign the value of the fast pointer to the location of the slow pointer, eliminating the problem of repeated movement caused by unnecessary values in the middle.
Let’s look at an example. Delete duplicate elements [1,2,2,2,3,3,3,5,5,7,8] from the following sequence, leaving only one duplicate element. The result after deletion should be [1,2,3,5,7,8]. We can move the entire element behind it forward once when deleting the first 2, and move the entire element forward once when deleting the second 2, to handle the same situation as the following 3 and 5. This results in us needing to perform 5 large movements to complete, which is too inefficient. This problem can be easily solved by using double pointers, as shown in the figure:
First we define two pointers slow and fast. Slow means that the elements before the current position are not repeated, while fast keeps looking backward until it finds a position different from that of slow. After finding it, it moves slow one position backward and copies arr[fast] to arr. [slow], then fast continues to search backwards and executes in a loop. After searching, slow and the previous elements will be single. This solves the problem with just one move.
Delete element topic:
2.1 Delete the element with value val in place
LeetCode27. Given an array nums and a value val, you need to remove all elements with a value equal to val in place and return the new length of the array after removal.
Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2] Explanation: The function should return a new length of 2, and the first two elements in nums are both 2. You don't need to consider elements in the array beyond the new length. For example, the new length returned by the function is 2, and nums = [2,2,3,3] or nums = [2,2,0,0] will also be considered the correct answer.
The first type: fast and slow pointers
When traversing, if:
● If the value of nums[fast] is not val, move it to nums[slow + +].
● If the value of nums[fast] is val, fast continues to move forward, and slow waits first.
/**
* Delete elements through fast and slow pointers
*
* @param nums array
* @param val value to be deleted
* @return
*/
public static int delVal(int[] nums, int val) {<!-- -->
int slow = 0;
for (int fast = 0; fast < nums.length; fast + + ) {<!-- -->
if (nums[fast] != val) {<!-- -->
nums[slow + + ] = nums[fast];
}
}
return slow;
}
Second type: Collision of double pointers
**Basic idea:** The left pointer is used to find places where = val, and the right pointer is used to find places that are not val.
Let’s take nums = [0,1,2,2,3,0,4,2], val = 2 as an example:
/**
* Collision of double pointers
*
* @param nums array
* @param val value to be deleted
* @return size
*/
public static int delValWithCollision(int[] nums, int val) {<!-- -->
int slow = 0;
int fast = nums.length - 1;
while (slow < fast) {<!-- -->
if (nums[slow] == val & amp; & amp; nums[fast] != val) {<!-- -->
nums[slow] = nums[fast];
}
if (nums[slow] != val) slow + + ;
if (nums[fast] == val) fast--;
}
return slow;
}
Third type: Optimization of collision pointers
As long as slow == val, convert it
public static int delValWithCollision2(int[] nums, int val) {<!-- -->
int slow = 0;
int fast = nums.length - 1;
for (slow = 0; slow <= fast;) {<!-- -->
if (nums[slow] == val) {<!-- -->
nums[slow] = nums[fast--];
} else {<!-- -->
slow + + ;
}
}
return slow;
}
2.2 Delete duplicates in ordered array
LeetCode26 gives you an ordered array nums. Please delete the repeated elements in place so that each element appears only once, and return the new length of the array after deletion. Instead of using extra array space, you must modify the input array in-place and do it using O(1) extra space.
Example 1: Input: nums = [1,1,2] Output: 2, nums = [1,2,_] Explanation: The function should return the new length 2, and the first two elements of the original array nums are modified to 1, 2. Elements in the array beyond the new length do not need to be considered. Example two: Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4] Explanation: The function should return a new length of 5, and the first five elements of the original array nums are modified to 0, 1, 2, 3, 4. Elements in the array beyond the new length do not need to be considered.
public static int removeDuplicates(int[] arr) {<!-- -->
// The first position here does not need to be considered, it is equivalent to being equal.
int slow = 1;
for (int fast = 0; fast < arr.length; fast + + ) {<!-- -->
if (arr[fast] != arr[slow - 1]) {<!-- -->
arr[slow] = arr[fast];
slow + + ;
}
}
return slow;
}
Element odd-even movement:
LeetCode905, sort array by odd and even. Given an array of nonnegative integers, return an array in which all even elements of are followed by all odd elements. You can return any array that satisfies this condition as the answer.
The ontology uses the collision pointer to move the odd-numbered parts on the left to the right
Input: nums = [3,1,2,4] Output: [2,4,3,1] Explanation: [4,2,3,1], [2,4,1,3] and [4,2,1,3] are also considered correct answers.
public static int[] sortArrayByParity(int[] nums) {<!-- -->
int left = 0;
int right = nums.length - 1;
while (left < right) {<!-- -->
// Left odd, right even
if (nums[left] % 2 > nums[right] % 2) {<!-- -->
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
if (nums[left] % 2 == 0) {<!-- -->
left + + ;
}
if (nums[right] % 2 == 1) {<!-- -->
right --;
}
}
return nums;
}
Array rotation problem:
LeetCode189.Given you an array, rotate the elements in the array k positions to the right, where k is a non-negative number.
Example one:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: Rotate right 1 step: [7,1,2,3,4,5,6] Rotate right 2 steps: [6,7,1,2,3,4,5] Rotate 3 steps to the right: [5,6,7,1,2,3,4]
In addition to the gradual rotation of this question, we will find that the final rotation can be achieved in three steps:
- First flip the entire array, for example [1,2,3,4,5,6,7], we first flip it as a whole into [7,6,5,4,3,2,1].
- It is divided into left and right parts from k. Here it is divided into two groups [7,6,5] and [4,3,2,1] based on k.
- Finally, flip the two again to get [5,6,7] and [1,2,3,4], and the final result is [5,6,7,1,2,3,4]
The principle is as follows:
(
A
B
)
?
1
(AB)^-1
(AB)?1 =
B
?
1
B^-1
B?1
A
?
1
A^-1
A?1
(
B
?
1
A
?
1
)
?
1
(B^-1 A^-1)^-1
(B?1A?1)?1 = B A
The code is as follows:
public void rotate(int[] nums, int k) {<!-- -->
k %= nums.length;
if (k != 0) {<!-- -->
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k-1);
reverse(nums, k, nums.length - 1);
}
}
public void reverse(int[] nums, int start, int end) {<!-- -->
while (start < end) {<!-- -->
int temp = nums[start];
nums[start + + ] = nums[end];
nums[end--] = temp;
}
}
Interval problem of array:
Interval:
LeetCode228.Given an ordered integer array nums without duplicate elements. Returns a list of the smallest ordered ranges that exactly cover all the numbers in the array. That is, every element of nums is covered by exactly some interval range, and there is no number x that belongs to a range but not nums . Each interval range [a,b] in the list should be output in the following format: “a->b” if a != b”a” if a == b
Input: nums = [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Explanation: The interval range is: [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7\ "
In this question, the slow pointer is used to determine the starting point, and the fast pointer is used to determine the end point.
public static List<String> summaryRanges(int[] nums) {<!-- -->
List<String> res = new ArrayList<>();
// starting point
int slow = 0;
// The loop moves the fast pointer forward continuously
for (int fast = 0; fast < nums.length; fast + + ) {<!-- -->
if (fast + 1 == nums.length || nums[fast] + 1 != nums[fast + 1]) {<!-- -->
StringBuilder sb = new StringBuilder();
sb.append(nums[slow]);
// If there is only one value, then there is no need to splice it
if (slow != fast) {<!-- -->
sb.append("->").append(nums[fast]);
}
// Refresh slow to fast next
slow = fast + 1;
res.add(sb.toString());
}
}
return res;
}
Key point: The if judgment in the for loop must add the boundary condition fast + 1 == nums.length to prevent crossing the boundary, such as [0]. The same is true for the following if (slow != fast). If there is only one element and slow == fast, splicing cannot be performed.
Non-interval:
public static List<String> ranges(int[] nums, int big) {<!-- -->
List<String> res = new ArrayList<>();
for (int index = 0; index < nums.length; index + + ) {<!-- -->
if (index + 1 == nums.length || nums[index] + 1 != nums[index + 1]) {<!-- -->
int min = nums[index] + 1;
int max = 0;
// If a boundary value occurs, the maximum value cannot be index + 1, otherwise it will cross the boundary.
if (index + 1 == nums.length) {<!-- -->
max = big;
} else {<!-- -->
max = nums[index + 1] - 1;
}
StringBuilder sb = new StringBuilder();
sb.append(min);
// If there is only one value difference in the middle, don't worry about it.
if (min != max) {<!-- -->
sb.append("->").append(max);
}
res.add(sb.toString());
}
}
return res;
}
String space separation problem:
Convert spaces to
- Find how many spaces there are
- Expand to original size + 2 * number of spaces
- Values are assigned from the end forward, and if spaces appear, a new array is created three characters forward. The fast pointer points to the end of the old array, and the slow pointer points to the end of the new array.
public static String replaceSpace(StringBuffer str) {<!-- -->
if (str == null) {<!-- -->
return null;
}
//Number of spaces
int numOfblank = 0;
int len = str.length();
for (int i = 0; i < len; i + + ) {<!-- -->
if (str.charAt(i) == ' ') {<!-- -->
numOfblank + + ;
}
}
//Set the length
str.setLength(len + 2 * numOfblank);
//Two pointers
int fast = len - 1;
int slow = (len + 2 * numOfblank) - 1;
while (fast >= 0 & amp; & amp; slow > fast) {<!-- -->
char c = str.charAt(fast);
if (c == ' ') {<!-- -->
fast--;
str.setCharAt(slow--, '0');
str.setCharAt(slow--, '2');
str.setCharAt(slow--, '%');
} else {<!-- -->
str.setCharAt(slow, c);
fast--;
slow--;
}
}
return str.toString();
}