Array double pointer method
Double pointer method is also called fast and slow pointer method. Using double pointer method in array and linked list can effectively solve many problems
The key of double pointer method is to combine two cycles into one. Many violent algorithms can be optimized by double pointer method
Don't say much, just go to the question ヾ (≥ ▽≤ *) o
Brushing order from Code Capriccio , make your own summary
leetcode related topics
27. Remove elements
Give you an array num 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.
Instead of using extra array space, you must use only O(1) extra space and modify the input array in place.
The order of elements can be changed. You don't need to consider the elements in the array that exceed the new length.
Example 1:
Input: num = [3,2,2,3], Val = 3
Output: 2, Num = [2,2]
Explanation: the function should return a new length of 2, and the first two elements in num are 2. You don't need to consider the elements in the array that exceed the new length. For example, if the new length returned by the function is 2, and num = [2,2,3,3] or num = [2,2,0,0], it will also be regarded as the correct answer.
Example 2:
Input: num = [0,1,2,2,3,0,4,2], Val = 2
Output: 5, Num = [0,1,4,0,3]
Explanation: the function should return a new length of 5, and the first five elements in num are 0, 1, 3, 0 and 4. Note that these five elements can be in any order. You don't need to consider the elements in the array that exceed the new length.
This problem can be solved by setting a new array, traversing one side of the original array, and putting the elements not equal to val into the new array. The time complexity is O(n) and the space complexity is O(n). However, the problem requires that only the space of O(1) can be used, that is, it has to operate on the original array.
-
Violent solution O(n^2)
Traverse the array. Every time an element equal to val is encountered, delete the element and move the following element forward
class Solution { public: int removeElement(vector<int>& nums, int val) { int length = nums.size(); for (int i = 0; i < length; i++) { if (nums[i] == val) { for (int j = i; j < length - 1; j++) { nums[j] = nums[j + 1]; } length -= 1; i--; //Key, easy to write and leak, and the subscript moves forward as a whole } } return length; } };This method can also be optimized. Traversing from back to front can reduce the number of elements moving forward, but the time complexity is still O(n^2)
For example, if the array [3, 2, 2, 3], val = 2, traverse from front to back and delete it. We need to move [3, 2, 2, 3] (2 times) + [3, 2, 3] (1 time) = 3 times
Traversing from the back to the front, we need to move [3, 2, 2, 3] (once) + [3, 2, 3] (once) = twice. The number of moves is reduced because we move fewer duplicate elements to be deleted.
-
Double pointer method O(n)
Define a fast pointer fastIndex to traverse the array. The slow pointer slowIndex points to the position of the array to be updated. When the element pointed by fastIndex is different from the element to be deleted, it is updated to the position of slowIndex, and slowIndex moves by one bit
class Solution { public: int removeElement(vector<int>& nums, int val) { int slowIndex = 0, fastIndex = 0; //Initialize speed pointer while (fastIndex < nums.size()) { //Fast pointer traversal if (nums[fastIndex] != val) { nums[slowIndex] = nums[fastIndex]; slowIndex++; } fastIndex++; } return slowIndex; //slowIndex points to the next subscript, and slowIndex is the length } };
26. Delete duplicates in ordered array
Give you an ordered array nums, please delete the repeated elements in place, make each element appear only once, and return the new length of the deleted array.
Do not use additional array space. You must modify the input array in place and complete it with O(1) additional space.
Example 1:
Input: num = [1,1,2]
Output: 2, Num = [1,2]
Explanation: the function should return a new length of 2, and the first two elements of the original array num are modified to 1 and 2. There is no need to consider the elements in the array that exceed the new length.
Example 2:
Input: num = [0,0,1,1,1,2,2,3,3,4]
Output: 5, Num = [0,1,2,3,4]
Explanation: the function should return a new length of 5, and the first five elements of the original array num are modified to 0, 1, 2, 3 and 4. There is no need to consider the elements in the array that exceed the new length.
Because the array is ordered, we can use the double pointer method to delete duplicate elements, let slowIndex point to the previous element, and fastIndex traverses. If the value pointed by fastIndex is the same as that pointed by slowIndex, it means that the array is repeated, slowIndex does not move, and fastIndex moves by one bit; Otherwise, let slowIndex point to the next bit first, and then update.
Note that the difference from the previous question is that the slowIndex here points to the position of the array that has been updated, not the position to be updated, so the length should be + 1 at the end of the return
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() == 0) return 0;
int slowIndex = 0, fastIndex = 0;
while (fastIndex < nums.size()) {
if (nums[fastIndex] != nums[slowIndex]) {
slowIndex++; //slowIndex needs to be added by one first
nums[slowIndex] = nums[fastIndex];
}
fastIndex ++;
}
return slowIndex + 1; //The return length should be increased by one
}
};
283. Move zero
Given an array num, write a function to move all zeros to the end of the array while maintaining the relative order of non-zero elements.
Note that you must operate on the array in place without copying it.
Example 1:
Input: num = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: num = [0]
Output: [0]
It is equivalent to deleting the element with 0 in the element and adding 0 at the end
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int fastIndex = 0, slowIndex = 0;
for (; fastIndex < nums.size(); fastIndex++) { //Delete element with 0
if (nums[fastIndex] != 0) {
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
for (int i = slowIndex; i < nums.size() ; i++) { //Add 0 at the end
nums[i] = 0;
}
}
};
844. Compare strings with backspace
Given the two strings s and t, when they are input into the blank text editor respectively, please judge whether they are equal# Represents a backspace character.
If equal, return true; Otherwise, false is returned.
Note: if you enter a backspace character for empty text, the text continues to be empty.
Example 1:
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: both S and T will become "ac".
Example 2:
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: both s and t will become "".
Example 3:
Input: s = "a##c", t = "#a#c"
Output: true
Explanation: both s and t will become "c".
Example 4:
Input: s = "a#c", t = "b"
Output: false
Explanation: s will become "c", but t is still "b".
-
One method is to convert the two inputs into the corresponding string first. Here, the data structure of the stack is used, and then the string size is compared
Time complexity O(N)
Space complexity O(N)
class Solution { public: bool backspaceCompare(string s, string t) { string s1, s2; int index1 = 0, index2 = 0; for (int i = 0; i < s.length(); i++) { //Using the stack characteristic of string, s is transformed into the corresponding character if (s[i] != '#') { s1 += s[i]; } else if (!s1.empty()) { s1.pop_back(); } } for (int i = 0; i < t.length(); i++) { //Using the stack characteristic of string, t is transformed into the corresponding character if (t[i] != '#') { s2 += t[i]; } else if (!s2.empty()) { s2.pop_back(); } } if (s1.compare(s2) == 0) { //Compare strings return true; } return false; } }; -
Using double pointers, the double pointers here do not point to the fast and slow pointers in an array mentioned earlier, but a pointer to the string s and a pointer to the string t, and then compare them one by one.
When comparing ordinary strings, such as "abc" and "abd", we compare whether the characters at each position are equal in turn, that is, essentially only one subscript is changing.
However, the special character "#" in the title string indicates backspace, so we can't use the same subscript when comparing two strings, so there are two different pointers, or two pointers with different speed.
Then how can we determine the speed of two pointers? That is, through the "#" symbol in the string, we must first determine the number of "#" in order to locate the position where the two pointers should move respectively, so the pointer should traverse from back to front.
Time complexity O(N)
Space complexity O(1)
It's easy to make mistakes here. From the beginning, I naturally count the number of "#" from the back to the front, and then let the pointer move the corresponding number of times at one time to compare whether the characters are equal at this time. At this time, there will be a special case, that is, if the string pointed to after backspace is still backspace, an error will occur. For example, "ab##" and "c#d#", the former points to 'b' and the latter points to '#', which returns false and should actually return true. The solution is to judge whether the current character is "#" after each backspace. If so, continue to backspace.
class Solution { public: bool backspaceCompare(string s, string t) { int index1 = s.size() - 1, index2 = t.size() - 1; //Initialize two "pointers" to point to the end of two strings respectively int skips = 0, skipt = 0; //Backspace times while (index1 >= 0 || index2 >= 0) { //When both strings are not completely traversed while (index1 >= 0) { if (s[index1] == '#'{/ / the current character is a backspace character, and the number of backspaces is + 1 skips++; index1--; } else if (skips > 0) { //Backspace number is not 0, backspace index1--; skips--; } else { //The current character is not a backspace character, and the backspace number is 0, indicating that the character currently pointed to is the character to be compared break; } } // The same is true for string t processing while (index2 >= 0) { if (t[index2] == '#'{/ / the current character is a backspace character, and the number of backspaces is + 1 skipt++; index2--; } else if (skipt > 0) { //Backspace number is not 0, backspace index2--; skipt--; } else { //The current character is not a backspace character, and the backspace number is 0, indicating that the character currently pointed to is the character to be compared break; } } //The following is the wrong way of writing //From the beginning, it is natural to count the number of "#" from the back to the front, and then let the pointer move the corresponding number of times at one time // while (s[index1] == '#') { // skips++; // In case of backspace, the number of backspace + 1 // index1--; // } // If (skips > 0) {/ / if the number of backspaces is greater than 0, the corresponding number of backspaces will be reset // index1 -= skips; // skips = 0; // } // while (t[index2] == '#') { // skipt++; // In case of backspace, the number of backspace + 1 // index2--; // } // If (skip > 0) {/ / if the number of backspaces is greater than 0, the corresponding number of backspaces will be reset // index2 -= skipt; // skipt = 0; // } if (index1 >= 0 && index2 >= 0) { //At this time, both index1 and index2 point to the character to be compared if (s[index1] != t[index2]) { //If the characters are not equal, false is returned return false; } } else if (index1 >= 0 || index2 >=0){ //If one of the two strings is traversed and the other is not traversed, false is returned return false; } index1--, index2--; } return true; //At this point, both strings are traversed } };