Shulou(Shulou.com)06/01 Report--

This article will explain in detail what is the solution to the problem of big data's double-pointer algorithm. The content of the article is of high quality, so the editor shares it for you as a reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

The use of double pointers in the algorithm sometimes feels very ingenious and solves a lot of problems, so it is necessary to sum up. First of all, double pointers are also a very broad concept, which is similar to I and j in traversal, but the difference is that the two pointers move at the same time, that is, they do not contribute complexity from O (N) to O (N), so they are respected by many algorithm bosses. Therefore, based on this, the common solutions and routines of double pointers are summarized.

1. Item type induction

Here, there are three types of questions, which are as follows:

Fast and slow pointers (two pointers in different steps)

Front and rear double-ended pointer (one at the head, one at the tail, closer to the middle)

Pointers at fixed intervals (two pointers spaced by I, I + k)

As mentioned earlier, all three pointers can be done by traversing the array once, and their time complexity is less than or equal to O (N), and the space complexity is O (1) because only two pointers are stored.

two。 Common question type 2.1 Speed pointer

A rather classic question:

To determine whether the linked list has a ring-

Through two pointers with different steps, one moves together until the pointers coincide.

Https://leetcode.com/problems/linked-list-cycle/description, the code snippet is as follows:

Public boolean hasCycle (ListNode head) {ListNode slow = head; ListNode fast = head; while (slow! = null & & fast! = null) {ListNode n = fast.next; fast = n = = null? Null: n.next.if (slow = = fast) {return true;} slow = slow.next;} return false;}

Look for a repeating plural and find a repeating integer from the array: https://leetcode-cn.com/problems/find-the-duplicate-number/

The code is solved as follows:

Public int findDuplicate (int [] nums) {/ / think of it as a circular linked list with fast and slow pointer cycles int index1 = 0; int index2 = 0; do {index1 = nums [index1]; index2 = nums [index2]; index2 = nums [index2];} while (nums [index1]! = nums [index2]) Index1 = 0 index2 / find out where the starting point is, it can be proved that we must meet at the beginning of the circle while (index1! = index2) {index1 = nums [index1]; index2 = nums [index2];} return index1;} 2.2

Binary search

Binary search is a typical question type of front and back pointer, and the code is as follows:

Public static int binarySearch (int [] array, int targetElement) {int leftIndex = 0, rightIndex = array.length-1, middleIndex = (leftIndex + rightIndex) / 2; while (leftIndex middleElement) {leftIndex = middleIndex + 1;} else {return middleIndex;} middleIndex = (leftIndex + rightIndex) / 2;} return-1;} 2.3 fixed interval pointer

Find the midpoint https://leetcode-cn.com/problems/middle-of-the-linked-list/ of the linked list

/ / the fast pointer Q takes two steps at a time, the slow pointer p takes one step at a time, and p is right in the middle when Q comes to the end. Class Solution {public ListNode middleNode (ListNode head) {ListNode p = head, Q = head; while (Q! = null & & q.next! = null) {Q = q.next.next.nextp = p.next;} return p;}}

Find the last k element https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/ of the linked list

/ / Fast and slow pointer, first let the fast pointer take k steps, and then the two pointers go synchronously. When the fast pointer reaches the end, the slow pointer is the last-to-last node of the linked list. Public ListNode getKthFromEnd (ListNode head, int k) {ListNode frontNode = head, behindNode = head; while (frontNode! = null & & k > 0) {frontNode = frontNode.next; Kmuri;} while (frontNode! = null) {frontNode = frontNode.next; behindNode = behindNode.next;} return behindNode;} 3. Template summary

After looking at the three codes, do you think it's very simple? let's summarize three kinds of double-pointer code templates.

/ / 1. The fast and slow pointer l = 0r = 0while does not traverse if under certain conditions l + = 1r + = 1return appropriate value / / 2. The left and right endpoint pointer l = 0r = n-1while l < r if found the value if found by return certain condition 1 l + = 1 else if certain condition 2 r-= 1return did not find / / 3. Fixed spacing pointer l = 0r = kwhile did not finish traversing the custom logic l + = 1r + = 1return appropriate value on the big data double-pointer algorithm solution ideas are shared here, I hope the above content can be of some help to everyone, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.