0. Content description

Recently, when I was writing some small algorithms, I felt that my algorithm was too bloated. It happened that Datawhale organized the course of data structure and algorithm in the new team learning. So I joined. Thank Datawhale again~~

First of all, I would like to share with you two learning materials that I feel better. One is Algorithm clearance manual It is also the learning material of Datawhale in this team learning; One is the video on station B [Peking University] data structure and algorithm Python Version (full version) , the teacher spoke very well (it's rare to have a data structure course in Python, ha ha ~).

It should be pointed out that the content of this blog is more like notes on the above two materials. Many of them are the original content of the materials, not original.

1. Introduction to double pointer

Two Pointers: refers to the use of Two Pointers instead of a single pointer in the process of traversing elements, so as to achieve the corresponding purpose. If the Two Pointers are in opposite directions, it is called colliding clockwise. If Two Pointers have the same direction, they are called fast and slow pointers. If Two Pointers belong to different arrays / linked lists, they are called separated double pointers. In the interval problem of arrays, the time complexity of violent algorithms is often O ( n 2 ) O(n^2) O(n2). The double pointer takes advantage of the monotonicity of the interval, which reduces the time complexity to O ( n ) O(n) O(n).

1.1 collision pointer

The collision pointer algorithm has a left pointer and a right pointer. Left and right point to the first element and the last element of the sequence respectively, and then the left pointer increases and right decreases until the values of the two pointers Collide (i.e. left == right) or meet other special conditions.

Example 1

• subject

  Give an array of integers in ascending order: numbers and a target value target.

• requirement

  Find two numbers from the array that meet the sum of addition equal to target, and return the label value of the two numbers in the array.

• thinking

  Use two pointers left, right. Left points to the position of the first element with the smallest value in the array, and right points to the position of the element with the largest value in the array. Judge the relationship between the sum of elements at two positions and the target value. If the sum of elements is equal to the target value, two element positions are returned. If the element sum is greater than the target value, move right to the left to continue detection. If the element sum is less than the target value, move left to the right to continue detection. Stop detection until left and right move to the same position. If it is still not found, it returns [- 1, - 1].

code:

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        while left < right:
            total = numbers[left] + numbers[right]
            if total == target:
                return [left + 1, right + 1]
            elif total < target:
                left += 1
            else:
                right -= 1
        return [-1, -1]

Example 2

• subject

  Validate palindrome string.

• requirement

  Judge whether it is a palindrome string (only consider the alphanumeric characters in the string, and ignore the case of letters).

• thinking

  Use two pointers left, right. Left points to the beginning of the string and right points to the end of the string. Judge whether the characters corresponding to two pointers are letters or numbers. Filter out characters other than letters and numbers by moving left to the right and right to the left. Then judge whether s[start] is equal to s[end] (pay attention to case). If they are equal, move left to the right and right to the left to continue the next filtering and judgment. If it is not equal, it indicates that it is not a palindrome string and returns False directly. If left == right is encountered and the loop jumps out, it indicates that the string is a palindrome string and returns True.

code:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1
        
        while left < right:
            if not s[left].isalnum():
                left += 1
                continue
            if not s[right].isalnum():
                right -= 1
                continue
            
            if s[left].lower() == s[right].lower():
                left += 1
                right -= 1
            else:
                return False
        return True

Example 3

• subject

  Given n nonnegative integers a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1, a2,..., an, each number represents a point in the coordinate ( i , a i ) (i,a_i) (i,ai​). Draw n vertical lines in the coordinates, and the two endpoints of the vertical line I are ( i , a i ) (i,a_i) (i,ai) and ( i , 0 ) (i,0) (i,0).

• requirement

  Find out the two vertical lines so that the container composed of them and the x-axis can hold the most water.

• thinking

  Use two pointers left, right. Left points to the start of the array and right points to the end of the array. Calculate the area value composed of left and right, and maintain and update the maximum area value at the same time. Judge the height values of left and right. If the height of the line pointed to by left is relatively low, move the left pointer to the right. If the straight line height pointed by right is relatively low, move the right pointer to the left. If left == right is encountered, jump out of the loop and finally return the maximum area.

code:

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        ans = 0
        while left < right:
            area = min(height[left], height[right]) * (right-left)
            ans = max(ans, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return ans

1.2 speed pointer

The fast and slow pointer refers to that two pointers start to traverse the sequence from the same side, and the moving step is fast and slow. A pointer that moves fast is called a fast pointer, and a pointer that moves slow is called a slow pointer. The two pointers move at different speeds and strategies until the fast pointer moves to the end of the array, or the two pointers intersect, or other special conditions are met.

Example 1

• subject

  Removes duplicates from an ordered array.

• requirement

  Delete the duplicate elements in the array num so that each element appears only once. And output the length of the array after removing duplicate elements.

• thinking

  Define two speed pointers slow, fast. Where slow points to the end of the array after removing duplicate elements. Fast points to the current element. Make slow in the back and fast in the front. Let slow = 0, fast = 1. Compare whether the element value at the slow position and the element value at the fast position are equal. If they are not equal, move slow back one bit and copy the element pointed by fast to the slow position. Shift fast right by 1 bit.

• code:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        
        slow, fast = 0, 1

        while (fast < len(nums)):
            if nums[slow] != nums[fast]:
                slow += 1
                nums[slow] = nums[fast]
            fast += 1
            
        return slow + 1

1.3 split double pointer

Separate double pointers: the two pointers belong to different arrays / linked lists, and the two pointers move in the two arrays / linked lists respectively.

Example 1

• subject

  The intersection of two arrays.

• requirement

  Write a function to calculate their intersection. Repeating elements are calculated only once.

• thinking

  Sort the arrays nums1 and nums2 first. Use two pointers left_ 1,left_ 2. left_ 1 points to the first element of the first array, that is, left_1 = 0，left_ 2 points to the first element of the second array, that is, left_2 = 0. If nums1[left_1] is equal to nums2[left_2], add it to the answer array (pay attention to de duplication) and set left_ 1 and left_ 2 shift right.

• code:

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()

        left_1 = 0
        left_2 = 0
        res = []
        while left_1 < len(nums1) and left_2 < len(nums2):
            if nums1[left_1] == nums2[left_2]:
                if nums1[left_1] not in res:
                    res.append(nums1[left_1])
                left_1 += 1
                left_2 += 1
            elif nums1[left_1] < nums2[left_2]:
                left_1 += 1
            elif nums1[left_1] > nums2[left_2]:
                left_2 += 1
        return res

2. Introduction to sliding window

Sliding Window: maintain a fixed or indefinite length window on a given array / string. You can slide, zoom, and maintain the optimal solution of the window.

2.1 fixed length sliding window

The window width of a fixed length sliding window is unchanged.

Example 1

• subject

  The number of subarrays of size K with an average value greater than or equal to the threshold.

• requirement

  Returns the number of subarrays with a length of k and an average value greater than or equal to threshold.

• thinking

  ans is used to maintain the number of answers. window_sum is used to maintain the sum of elements in the window.
  Both left and right point to the first element of the sequence, that is, left = 0 and right = 0. When the number of window elements is less than k, keep moving right and fill k elements into the window first. When the number of window elements is k, that is: right - left + 1 > = k, judge whether the elements and average value in the window are greater than or equal to the threshold. If yes, the number of answers + 1. Then move left to the right to reduce the window length, i.e. left += 1, so that the window size remains K. Move right to fill the window with elements. Repeat steps 3 to 5 until right reaches the end of the array.

• code:

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        left = 0
        right = 0
        window_sum = 0
        ans = 0

        while right < len(arr):
            window_sum += arr[right]
            
            if right - left + 1 >= k:
                if window_sum >= k * threshold:
                    ans += 1
                window_sum -= arr[left]
                left += 1

            right += 1

        return ans

2.2 sliding window with variable length

The window width of sliding window with variable length is variable.

Example 1

• subject

  The longest substring without duplicate characters.

• requirement

  Find the length of the longest substring that does not contain duplicate characters.

• thinking

  At first, both left and right point to 0. Add the rightmost character s[right] into the current window and record the number of characters. If the number of characters in the window is more than 1, that is, window [s[right]] > 1, keep moving left, reduce the length of the sliding window, and update the number of corresponding characters in the window until window [s[right]] < = 1. Maintain and update the longest substring length without duplicate characters. Then move right until right > = len (nums) ends. Output the longest substring length without duplicate characters.

• code:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 0
        window = dict()
        ans = 0

        while right < len(s):
            if s[right] not in window:
                window[s[right]] = 1
            else:
                window[s[right]] += 1

            while window[s[right]] > 1:
                window[s[left]] -= 1
                left += 1

            ans = max(ans, right - left + 1)
            right += 1

        return ans

Example 2

• subject

  The smallest subarray.

• requirement

  Given an array num containing only positive integers and a positive integer target. Find the "continuous sub array" with the smallest length that meets and is greater than or equal to target in the array, and return its length. If there is no eligible subarray, 0 is returned.

• thinking

  At first, both left and right point to 0. Move right to add the rightmost element to the current window and window_ In sum. If window_sum > = target, keep moving left, reduce the length of sliding window, and update the minimum value of window and until window_sum < target. Then continue to move right until right > = len (nums) ends. Output the minimum value of window and as the answer.

• code:

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        size = len(nums)
        ans = size + 1
        left = 0
        right = 0
        window_sum = 0

        while right < size:
            window_sum += nums[right]

            while window_sum >= target:
                ans = min(ans, right - left + 1)
                window_sum -= nums[left]
                left += 1

            right += 1

        return ans if ans != size + 1 else 0

Example 3

• subject

  Subarray whose product is less than K.

• requirement

  Given a positive integer array nums and integer k. Find the number of consecutive sub arrays whose product is less than k in the array.

• thinking

  At first, both left and right point to 0. Add the rightmost element to the current subarray product window_ In product. If window_ If product > = k, keep moving left, reduce the sliding window length, and update the current product value window_product window_ product < k. Record the number of cumulative answers + = 1, move right to the right until right > = len (nums) ends. Output the number of cumulative answers.

• code:

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0

        size = len(nums)
        left = 0
        right = 0
        window_product = 1
        
        count = 0
        
        while right < size:
            window_product *= nums[right]

            while window_product >= k:
                window_product /= nums[left]
                left += 1

            count += (right - left + 1)
            right += 1
            
        return count