Algorithm (II) double pointer / iteration

Examples

1. Reverse linked list (recursive, double pointer / iteration)

From LeetCode206 Supplement:

* 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; }
* }

solution

1. Recursion

In recursive articles.

2. Double pointer

class Solution {
ListNode pre = null;
ListNode temp = null;
while(cur!=null){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}

cur points to the current node, pre points to the previous node, and temp points to the next node. Iteration.

Understanding (not guaranteed to be correct)

1. The linked list problem should draw the process in the book, so it is easy to get the algorithm.

2. Fixed position reverse linked list (recursive, double pointer / iteration)

From LeetCode92 Supplement:

* 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; }
* }

solution

1. Double pointer solution

class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {

if(left == right)

ListNode pre = null;
ListNode temp = null;
ListNode now = null;
ListNode r = null;
int count = 1;
for(;count<left;count++){
cur = cur.next;
}

while(count<=right&&cur!=null){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
count++;
}
for(int i =1;i<left-1;i++){
l=l.next;
}

if(left!=1){
l.next = pre;
pre = l;
}
while(now.next!=null)
now = now.next;
now.next = temp;
if(left==1)
return pre;
}
}

Write according to the double pointer algorithm of reverse linked list 1.

It is too violent to handle the linked list that has not been reversed (before left).

Big man's double pointer solution:

class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// Define a dumpyhead to facilitate processing

// Initialization pointer

// Move the pointer to the corresponding position
for(int step = 0; step < m - 1; step++) {
g = g.next; p = p.next;
}

// Insert node by head inserting method
for (int i = 0; i < n - m; i++) {
ListNode removed = p.next;
p.next = p.next.next;

removed.next = g.next;
g.next = removed;
}

}
}

The dummy header pointer dummyHead is used to avoid the front and back boundary problems.

2. Iteration

Write when you have time.

Understanding (not guaranteed to be correct)

1. There are left and right boundary value problems in linked list problems. Introducing a virtual head pointer can avoid a large number of problems.

From leetcode 160 solution

1. Double pointer IQ question

In fact, I walk twice. I often use this idea

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
while(A!=B){
if(A==null)
else
A = A.next;
if(B==null)
else
B = B.next;
}
return  A;
}
}

understand

None.

From LeetCode 415 solution

class Solution {
public String addStrings(String num1, String num2) {
StringBuffer sb = new StringBuffer();
int i = num1.length()-1;
int j = num2.length()-1;
int x = i >= 0? num1.charAt(i) - '0' : 0;
int y = j >= 0? num2.charAt(j) - '0' : 0;
int result = x + y + add;
if(result>=10)
else
sb.append(result%10);
i--;
j--;
}
sb.reverse();
return sb.toString();
}
}

understand

1. Double pointers point to single digits, and then use StringBuffer for storage and addition

2. There are many boundary conditions, which need special care.

3. You need to master String/StringBuffer/StringBuilder.

4. Merge two ordered arrays

From LeetCode88 be careful: 1. We need to review the question. The question tells us that it is an ordered array (from small to large).

solution

1. nt solution

class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m;
for(int j = 0;j<n;i++,j++){
nums1[i] = nums2[j];
}
Arrays.sort(nums1);
}
}

Throw it in and sort it directly.

2. Forward double pointer

• Because the order has been arranged, the smallest comparison only needs to compare the top elements.
• You can think of double pointers here, but this method must create a new array with high space complexity.
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] result = new int[m+n];
int i=0,j=0,r=0;
while(i<m||j<n){
if(i==m){
result[r] = nums2[j];
j++;
}
else if(j==n){
result[r] = nums1[i];
i++;
}
else if(nums1[i]<nums2[j]){
result[r] = nums1[i];
i++;
}
else{
result[r] = nums2[j];
j++;
}
r++;
}
for(int q = 0;q<m+n;q++){
nums1[q] = result[q];
}
}
}

3. Reverse double pointer

• Inverse idea of forward double pointer
• If you don't want to create a new array, the original elements of nums1 may be overwritten with minimum coverage
• So we can think of using the maximum to cover the last element of nums1, because nums1 has a fixed length.
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int r = m+n -1;
while(i>=0||j>=0){
if(i==-1){
nums1[r] = nums2[j];
j--;
}
else if(j==-1){
nums1[r] = nums1[i];
i--;
}
else if(nums1[i]>nums2[j]){
nums1[r] = nums1[i];
i--;
}
else{
nums1[r] = nums2[j];
j--;
}
r--;
}
}
}

understand

1. Review the topic.

5. Binary tree traversal

In the article of algorithm (8).

Very important. Very important. Very important. Very important. Very important. Very important. Very important. Very important. Very important. Very important.

Added by inerte on Mon, 10 Jan 2022 05:47:30 +0200