Hello everyone, I am Su Lin, and today I will bring you the third level of the algorithm.
Outline of this issue
-
- Double pointer idea
-
- speed pointer
-
- Delete the Kth element from the bottom
- Delete element topic
-
- Remove element
- Special topic on odd-even movement of elements
- Summary interval
- Rotate array
Double pointer idea
Here is a simple but very effective way – a pair of pointers. The so-called double pointers are actually two variables, not necessarily pointers. The idea of double pointers is simple and easy to use, and is very common in scenarios such as array processing and character review.
For example, the picture below:
The fast pointer always moves ahead of the slow pointer and is always in front of the slow pointer. When the end comes, the slow pointer may point to the same place as the fast pointer, or the fast pointer may end directly when it reaches the end…
Speed and slow pointers
Fast and slow pointers are an implementation of double pointers. Two pointers are defined to point to a node at the same time, such as a head node, a virtual node, etc. The fast pointer takes a few more steps than the slow pointer. Let’s use a question to understand the fast and slow pointers:
Delete the Kth element from the bottom
Description:
Given a linked list, delete the nth node from the bottom of the linked list and return the head node of the linked list
Title:
LeetCode deletes the penultimate N node of the linked list:
Analysis:
First create a virtual node (sentinel node). The next node of the virtual node points to the head node, which is more convenient when we move elements. The slow node and fast node point to the virtual node using slow and slow pointers. The fast pointer is more than the nth element from the bottom. Take one step to flow out the deleted node, so slow.next = slow.next.next deletes the nth node from the bottom and finally returns the newNode.next node, which is the head node. However, there will be some problems in returning the head node directly. What is the problem here? Friends, think about it for yourselves.
Example: 1,2 delete the first element from the last
Analysis:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {<!-- -->
public ListNode removeNthFromEnd(ListNode head, int n) {<!-- -->
ListNode newNode = new ListNode(-100);
newNode.next = head;
ListNode slow = newNode;
ListNode fast = newNode;
for(int i = 0;i<= n ;i + + ){<!-- -->
fast = fast.next;
}
while(fast != null){<!-- -->
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return newNode.next;
}
}
In this way, the speed pointer is realized. Friends, practice by yourself…
Delete element topic
Remove element
Title:
LeetCode 27. Remove elements:
27. Remove elements
Analysis:
Speed pointer:
Define two pointers, slow and fast, with initial values 0. The positions before Slow are all valid parts, and fast represents the element currently being accessed.
When traversing like this, fast keeps moving backward:
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.
In this way, the first half is the valid part and the second half is the invalid part
Analysis:
class Solution {<!-- -->
public int removeElement(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;
}
}
Special topic on odd-even movement of elements
Description:
Given an integer array nums, move all even elements in nums to the front of the array, followed by all odd elements.
Return any array that satisfies this condition as the answer.
Title:
LeetCode 905. Sort array by parity:
Sort array by odd and even
Analysis:
We can use the collision type double pointer method. The collision type in the illustration is basically the same, but the comparison object is an odd number or an even number. As shown below:
Maintain two pointers left=0 and right=arr.ength-1, left is checked one by one starting from 0 Whether each position is an even number, if so, skip, if it is an odd number, stop. Then right checks from right to left, if it is an odd number, it skips the even number and stops. Then swap array[left] and array[right]. Then continue the tour loop until left>=right.
Analysis:
class Solution {<!-- -->
public int[] sortArrayByParity(int[] nums) {<!-- -->
int left = 0;
int right = nums.length - 1;
while(left < right){<!-- -->
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 > 0){<!-- -->
right--;
}
}
return nums;
}
}
Summary interval
Description:
Given a ordered integer array nums with no duplicate elements.
Returns a minimally ordered list of interval ranges that exactly covers 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 .
Title:
LeetCode 228. Summary interval:
228. Summary interval
Analysis:
This problem can also be solved very conveniently using double pointers. The slow pointer points to the starting position of each interval, and the fast pointer starts from the slow pointer position and traverses backward until the continuous increment is no longer satisfied (or the fast pointer reaches the array boundary), then the current interval End; then update the slow pointer to fast + 1, as the starting position of the next interval, fast continues to traverse backward to find the end position of the next interval, and so on until the input array is traversed.
Analysis:
// LeetCode
class Solution {<!-- -->
public List<String> summaryRanges(int[] nums) {<!-- -->
ArrayList<String> al = new ArrayList<>();
int slow = 0;
for(int fast = 0;fast < nums.length ; fast + + ){<!-- -->
if(fast + 1 == nums.length || nums[fast] + 1 != nums[fast + 1]){<!-- -->
StringBuffer s = new StringBuffer();
s.append(nums[slow]);
if(slow != fast){<!-- -->
s.append("->").append(nums[fast]);
}
al.add(s.toString());
slow = fast + 1;
}
}
return al;
}
}
Rotate array
Description:
Given an integer array nums, rotate the elements in the array k positions to the right, where k is a non-negative number.
Title:
Niuke NC110 rotating array:
Here Niuke gives the array length and we can use it directly.
LeetCode 189. Rotate array:
189. Rotate array
Analysis:
How to solve this problem? Have you ever thought that it can be realized by moving it one by one? In theory, it is possible, but when it is implemented, you will find that there are many situations to deal with, which is more difficult. Here is a simple method: two-wheel flip
Methods as below:
1. 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].
2. 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] according to k.
3. 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].
Analysis:
// LeetCode
class Solution {<!-- -->
public void rotate(int[] nums, int k) {<!-- -->
k %= nums.length;
exchange(nums, 0, nums.length -1);
exchange(nums, 0, k -1);
exchange(nums, k, nums.length -1);
}
public void exchange(int[] arr , int left , int right){<!-- -->
while(left <= right){<!-- -->
int temp =arr[left];
arr[left] = arr[right];
arr[right] = temp;
left + + ;
right--;
}
}
}
That’s it for this issue, see you in the next one!