In fact, I just want to share string palindrome related content, looking at the discovery of left and right pointer algorithm, looking at the discovery of fast and slow pointer algorithm. Added: ak47 schematic item and loot added this two days, I would like to share this item with my brothers.
First, fast and slow pointer
The fast and slow Pointers generally initialize head, which points to the head node of the linked list. When moving forward, the fast pointer fast is in front and the slow pointer slow is in front, cleverly solving some problems in the linked list.
1. Check whether the linked list has rings
The characteristic of a singly linked list is that each node only knows the next node, so it is impossible to determine whether there is a ring in the list with a pointer. A single list has no rings, so the pointer will eventually encounter a null pointer indicating that the list is at an end.
boolean hasCycle(ListNode head) {
while(head ! =null)
head = head.next;
return false;
}
Copy the codeA singly linked list gets a false value, and a looped list keeps going into an infinite loop in the while because there are no null Pointers as tail nodes in the looped list.
So the classic way to tell if there are rings in a linked list is to use two Pointers, one fast and one slow. If there are no rings, the faster pointer will eventually encounter null, indicating that the list has no rings. If there are rings, the fast pointer ends up one circle behind the slow pointer, which means the linked list contains rings.
boolean hasCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while(fast ! =null&& fast.next ! =null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) return true;
}
return false;
}
Copy the codeA single linked list yields a false value, and a looped list yields a true value.
2. List with rings, get the starting position of rings
This question is not difficult at all, it’s kind of like a brain teaser, first look directly at the code:
ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while(fast ! =null&& fast.next ! =null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// This code is similar to the hasCycle function
if (fast == null || fast.next == null) {
// If fast encounters a null pointer, there is no loop
return null;
}
slow = head;
while(slow ! = fast) { fast = fast.next; slow = slow.next; }return slow;
}
Copy the codeAs you can see, when the fast and slow Pointers meet, let one of them point to the head node, and then let them go at the same speed. When they meet again, they will be at the node where the ring started. Why is that?
On the first encounter, assuming that the slow pointer took K steps, then the fast pointer fast must have taken 2k steps, that is, k more steps (i.e. the length of the ring) than slow.
Let the distance between the encounter point and the beginning of the ring be m, then the distance between the beginning of the ring and the head node is k-m, that is, if you advance k-m steps from the head, you can reach the beginning of the ring.
Coincidentally, if you continue k-m steps from the point of encounter, you also reach the beginning of the ring.
I even think it’s a physics problem
3. Find the list midpoint
We can also make the fast pointer advance two steps at a time and the slow pointer advance one step at a time, so that when the fast pointer reaches the end of the list, the slow pointer will be in the middle of the list.
ListNode findMid(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while(fast ! =null&& fast.next ! =null) {
fast = fast.next.next;
slow = slow.next;
}
// Slow is in the middle
return slow;
}
Copy the codeWhen the length of the list is odd, slow stops exactly at the midpoint; If the length is even, slow ends up right of center:
An important function of finding the midpoint of a linked list is to merge and sort the list.
Recall the merge sort of arrays: find the midpoint index, divide the array recursively, and merge two ordered arrays. For linked lists, merging two ordered linked lists is very simple, the difficulty is the dichotomy.
But now that you’ve learned to find the midpoint of a linked list, you can achieve binary lists. I don’t want to go into the details of merge sort in this article.
4. Find the KTH element to the end of the list
The idea is to use the fast and slow Pointers, so that the fast and slow Pointers take k steps first, and then the fast and slow Pointers start to move at the same speed. So when the fast pointer reaches the end of the list, null, the slow pointer is at the position of the penultimate KTH list node (assuming k does not exceed the list length for simplicity) :
ListNode backwardK(ListNode head) {
ListNode slow, fast;
slow = fast = head;
while (k-- > 0)
fast = fast.next;
while(fast ! =null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
Copy the codeSecond, left and right Pointers
The left and right Pointers in the array actually refer to two index values, usually initialized to left = 0, right = nums.length-1.
Binary search
Here is only the simplest binary algorithm to highlight its two-pointer nature:
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
Copy the code2. Sum of two numbers
Close the door on Easy! The sum of two Numbers
As long as the array is ordered, you should think about the two-pointer trick. The solution to this problem is somewhat similar to binary search, where sum can be adjusted by adjusting left and right:
int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// The index starts at 1
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++; // Make sum larger
} else if (sum > target) {
right--; // Make sum smaller}}return new int[]{-1, -1};
}
Copy the code3. Reverse the array
void reverse(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
// swap(nums[left], nums[right])int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; }}Copy the code4. Find the longest loop string
Close the door and go middle! Longest string of subroutines
What is a palindrome? A palindrome string is a string that reads the same backwards and forwards. For example, the strings ABA and ABba are both palindromic strings because they are symmetric and, in reverse, identical to themselves. Conversely, the string abac is not a palindrome string.
It can be seen that the length of the palindrome string may be odd or even, which adds to the difficulty of the palindrome string problem. The core to solve this kind of problem is double pointer. The following is to understand the palindrome string problem in detail through a longest loop substring problem:
thinking
The first thing we should think about is, given a string s, how do we find a subroutine in S?
Here’s an interesting idea: since a palindrome string is a string that reads the same backwards and forwards, if we reverse s, call it s’, and then look for the longest common substring in s and S ‘, we should find the longest common substring.
For example, the string abacd, in reverse, dcaba, whose longest common substring is ABA, the longest loop substring. For example, the string aacxycaa is reversed to aacyxcaa. The longest common substring is aac, but the longest loop substring should be AA. Although this way of thinking is not correct, but this way of thinking about the problem into other forms is very worth advocating.
Here is the correct way to use a double pointer.
The core idea of finding palindromes is to judge palindromes by spreading from the middle to both sides. For the longest substring, this is what it means:
// Find the palindrome string centered around s[I]
for 0 <= i < len(s):
Copy the codeBut, as we said, the palindrome string can be odd or even, and in the case of ABBA, without a central character, the algorithm is dead. So we can modify it:
// Find the palindrome string centered on s[I] and s[I +1]
for 0 <= i < len(s):
Copy the codeCode implementation
To find the longest palindrome string, implement a tricky function:
string palindrome(string& s, int l, int r) {
// Prevent index transgressions
while (l >= 0 && r < s.size()
&& s[l] == s[r]) {
// Expand to both sides
l--; r++;
}
// Returns the longest palindrome string centered on s[l] and s[r]
return s.substr(l + 1, r - l - 1);
}
Copy the codeWhy pass in two Pointers L and r? Because this implementation can handle both odd and even palindrome string lengths:
for 0<= I < len(s): # find palindrome(s, I, I) # find palindrome(s, I, I) # find s[I] and s[I +1] is a palindrome(s, I, I +1)
Copy the codeLook at the complete code for longestPalindrome below:
string longestPalindrome(string s) {
string res;
for (int i = 0; i < s.size(); i++) {
// The longest loop substring centered around s[I]
string s1 = palindrome(s, i, i);
// The longest loop substring centered on s[I] and s[I +1]
string s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.size() > s1.size() ? res : s1;
res = res.size() > s2.size() ? res : s2;
}
return res;
}
Copy the codeAt this point, the problem of the longest substring is solved, O(N^2) in time, O(1) in space.
Reprinted from
-
Labuladong Fucking -algorithm double pointer technique
-
Find the longest callback substring
“Assault delete”
Learning algorithms from scratch is so damn hard!!
I am Yangyang Li, a front-end brick moving younger brother
Ten thousand years is too long, seize the day, see you next time
