Double pointer
Some double pointers are also called fast and slow pointers, and some are divided into fast and slow pointers and left and right pointers, which are mainly used to solve the problems of arrays, strings, linked lists and so on. Today's problem involves relatively shallow, mainly to solve the problem of simple arrays and strings.
Question 1: leetcode27. Removing 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: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2] Explanation: the function should return a new length of 2, also nums The first two elements in are both 2. You don't need to consider the elements in the array that exceed 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]，It will also be regarded as the correct answer.
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3] Explanation: the function should return a new length of 5, also nums The first five elements in are 0, 1, 3, 0, 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.
Tips:
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= val <= 100
Problem solving ideas:
The problem stem emphasizes "in place", so we can't create another array to solve the problem. Let's use the fast and slow pointer for this problem. First, let's understand the process of the fast and slow pointer:
Make slowIdx (slow pointer) point to subscript 0 and fastIdx (fast pointer) point to subscript 0. fastIdx moves forward. If the corresponding value is different from the deleted element, assign the current value to the value at the corresponding position of slowIdx. fastIdx is actually the self increasing i in the for loop. After traversal, slowIdx+1 is the length we need. There are videos and illustrations in the official explanation and comment area of leetcode. Those who don't understand can have a good look.
Next, add the following code:
public static void main(String[] args) {
int[] nums = new int[]{0,1,2,2,3,0,4,2};
int val = 2;
int len = removeElement(nums, val);
for (int i = 0; i < len; i++) {
System.out.print(nums[i]+" ");
}
}
// Just a few lines of code will not be annotated
private static int removeElement(int[] nums, int val) {
int slowIdx = 0;
for (int fastIdx = 0; fastIdx < nums.length; fastIdx++) {
if (nums[fastIdx] != val){
nums[slowIdx] = nums[fastIdx];
slowIdx++;
}
}
return slowIdx;
Similar to the above question leetcode26. Remove duplicates from ordered arrays as well as leetcode283. Move 0 , we won't do specific analysis here, but just give you the code (lazy):
leetcode26:
public static void main(String[] args) {
int[] nums = new int[]{};
int len = removeDuplicates(nums);
for (int i = 0; i < len; i++) {
System.out.print(nums[i]+" ");
}
}
private static int removeDuplicates(int[] nums) {
if (nums.length == 0)
return 0; //return -1 in leetcode will make an error;
// Here, slowIdx starts from 1 because the first number is taken as the val value in the double pointer at the beginning
int slowIdx = 1;
int val = nums[0];
for (int fastIdx = 0; fastIdx < nums.length; fastIdx++) {
if (nums[fastIdx] != val){
val = nums[fastIdx];
nums[slowIdx++] = val;
}
}
return slowIdx;
}
leetcode283:
public static void main(String[] args) {
int[] nums = new int[]{0,1,0,3,12};
moveZeroes(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+" ");
}
}
// The idea is to take 0 as the removed val, calculate how many zeros there are, and then insert these zeros into the back of the array
private static void moveZeroes(int[] nums) {
int val = 0;
int slowIdx = 0;
int zeroNum = 0;
for (int fastIdx = 0; fastIdx < nums.length; fastIdx++) {
if (nums[fastIdx] != val){
nums[slowIdx++] = nums[fastIdx];
}
else
zeroNum++;
}
// Insert 0 back
for (int i = nums.length - zeroNum; i <nums.length; i++) {
nums[i] = 0;
}
}
Question 2: leetcode844. 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: S and T Will become“ ac".
Example 2:
Input: s = "ab##", t = "c#d#" Output: true Explanation: s and t Will become "".
Example 3:
Input: s = "a##c", t = "#a#c" Output: true Explanation: s and t Will become“ c".
Example 4:
Input: s = "a#c", t = "b" Output: false Explanation: s Will become“ c"，but t Still“ b".
Tips:
- 1 <= s.length, t.length <= 200
- s and t contain only lowercase letters and the character '#'
Problem solving ideas:
I believe many people don't immediately think of double pointers (yes, it's myself). Generally, they delete what should be deleted in the string and compare the reconstructed two strings. However, since one of its labels has double pointers, it can be solved with double pointers. After reading the official double pointer solution and using the method of reverse order traversal and comparison, how can you feel that it is much more troublesome than the general double pointer? Of course, the official also has the dynamic diagram explanation, you can go and have a look.
In fact, this problem is not as troublesome as the official one. It is the same as the previous routine. Of course, we first change the string into an array, and then take '#' as the val value. If fastIdx finds val, the previous data needs to be deleted according to the meaning of the problem, so we only need to put slowIdx-1. Finally, you can get the deleted string fragment (I was surprised to use double pointers to reconstruct the string). If you don't say much, go to the code:
public static void main(String[] args) {
String s = "a#c", t = "b";
boolean out = backspaceCompare(s, t);
System.out.println(out);
}
private static boolean backspaceCompare(String s, String t) {
// Double pointers are best used to operate on arrays, so here we turn strings into arrays
String ss = getStr(s.toCharArray());
String tt = getStr(t.toCharArray());
return ss.equals(tt);
}
private static String getStr(char[] str) {
// When using slowIdx, first + 1 and then assign a value, so as to facilitate - 1 in else if
int slowIdx = -1;
char space = '#';
for (int fastIdx = 0; fastIdx < str.length; fastIdx++) {
if (str[fastIdx] != space){
slowIdx++;
str[slowIdx] = str[fastIdx];
}
else if (slowIdx >= 0){
slowIdx--;
}
}
// The copyOfRange method intercepts the array
char[] result = Arrays.copyOfRange(str,0,slowIdx+1);
// The return value is converted to String
return new String(result);
}
Question 3: leetcode977. Square of ordered array
Give you an integer array nums sorted in non decreasing order, and return a new array composed of the square of each number. It is also required to sort in non decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10] Output:[0,1,9,16,100] Explanation: after squaring, the array becomes [16,1,0,9,100] After sorting, the array becomes [0,1,9,16,100]
Example 2:
Input: nums = [-7,-3,2,3,11] Output:[4,9,9,49,121]
Tips:
- $1 <= nums.length <= 10^4$
- $-10^4 <= nums[i] <= 10^4$
- Num sorts in non decreasing order
Problem solving ideas:
In fact, this problem is very simple. You can sort the array one by one after square. Of course, the efficiency of sorting methods is different. You can also directly call the arrays provided by java Sort () method, which uses a sort algorithm called TimSort, is an optimized version of merge sort. The official solution is double pointer + merge sorting. Those who are interested can learn.
There is no direct call to the sorting provided by java. According to the title, if there is a negative number in the array, the value after the square is reduced first and then increased (the array is not decreasing), so we can directly compare the size after the square of the first and last values, and then insert the maximum value into the last bit by using the first and last double pointers. See the code below:
public static void main(String[] args) {
int[] nums = new int[]{-7,-3,2,3,11};
int[] result = sortedSquares(nums);
for (int i = 0; i < result.length; i++) {
System.out.print(result[i]+" ");
}
}
private static int[] sortedSquares(int[] nums) {
// Create a new array with the same length as nums as the return array
int[] res = new int[nums.length];
// Initialize header and footer pointers
int leftIdx = 0, rightIdx = nums.length-1;
int idx = nums.length-1; //This is the order in which values are inserted
while (leftIdx <= rightIdx){
// Compare the size of the leading and trailing squares, and then update the corresponding leading and trailing pointers
if (nums[leftIdx] * nums[leftIdx] >= nums[rightIdx] * nums[rightIdx]){
res[idx--] = nums[leftIdx] * nums[leftIdx];
leftIdx++;
}
else{
res[idx--] = nums[rightIdx] * nums[rightIdx];
rightIdx--;
}
}
return res;
}
Summary:
OK, this is the content of today's study. It simply uses double pointers and does not involve data structures such as linked lists (take your time the next day when you enter the leetcode pit). You can only improve if you can summarize and be happy if you can share. Don't forget to swipe questions and punch in during the new year.
Brush reference: route code (WeChat official account)