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

This article mainly talks about "what are the Grokking coding modes". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what are the Grokking coding patterns?"

1. Sliding window

Sliding window mode is used to perform the desired operations on a specific window size of a given array or linked list, such as finding the longest subarray containing all 1. The sliding window starts with the first element, moves one element to the right, and adjusts the length of the window according to the problem you want to solve. In some cases, the window size remains the same, while in others, the window size increases or decreases.

Here are some ways to determine that a sliding window may be required for a given problem:

The problem input is a linear data structure, such as a linked list, array, or string

Requires you to find the longest / shortest substring, subarray, or desired value

You use sliding window mode for the following common questions:

Maximum sum subarray of size "K" (simple)

The longest substring with "K" different characters (middle)

Crossword puzzle (hard)

two。 Two pointers or iterators

Two pointers is a pattern in which two pointers traverse the data structure in series until one or both of the pointers reach a specific condition. Two pointers are often useful when searching for pairs in a sorted array or linked list; for example, when you have to compare each element of an array with other elements.

Two pointers are required, and because only pointers are used, you will have to loop through the array constantly to find the answer. Doing this back and forth with a single iterator is inefficient in terms of time and space complexity-a concept called asymptotic analysis. Although a strong or simple solution with 1 pointer will work, it will produce lines similar to O (n ²). In many cases, two pointers can help you find a solution with better space or runtime complexity.

The method for determining when to use the "two pointers" method:

It will encounter some problems when dealing with sorted arrays (or linked lists) and need to find a set of elements that meet certain constraints.

The set of elements in an array is a pair, a triple or even a subarray

Here are some problems with two pointer modes:

Squared sorted array (simple)

Triple with a total of zero (middle)

Compare strings containing backspace keys (middle)

3. Fast and slow pointer

The fast and slow pointer method, also known as the Hare&Tortoise algorithm, is a pointer algorithm that uses two pointers to move through an array (or sequence / linked list) at different speeds. This method is useful when working with circular linked lists or arrays.

By moving at different speeds (for example, in a circular linked list), the algorithm proves that the two pointers must meet. Once both pointers are in a loop, the fast pointer should capture the slow pointer.

How do you determine when to use fast and slow modes?

This problem will deal with loops in linked lists or arrays

When you need to know the location of an element or the total length of the linked list.

When should I use it on the "two pointers" method mentioned above?

In some cases, you should not use the "two pointers" method, for example, in a single chain list, you cannot move backwards. An example of when to use fast and slow modes is when you try to determine whether the link list is a palindrome.

Problems with fast and slow pointer modes:

Link list cycle (simple)

Palindromes link list (middle)

Cyclic array (hard)

4. Merge interval

Merge interval mode is an effective technique for dealing with overlapping intervals. In many issues involving intervals, you need to find overlapping intervals, or if they overlap, you need to merge intervals. The mode is as follows:

Given two intervals ("a" and "b"), they can be related to each other in six different ways:

Understanding and understanding these six situations will help you solve problems ranging from insertion intervals to optimized interval merging.

How do you determine when to use merge interval mode?

If you are required to generate lists only at mutually exclusive intervals

If you hear the term "overlap interval".

Merge interval problem mode:

Interval intersection (middle)

Maximum CPU load (hard)

5. Circular sorting

This pattern describes an interesting way to deal with problems involving arrays containing numbers in a given range. The circular sort mode iterates over the array one number at a time, swapping it with the number at its correct index if the current number to be iterated is not at the correct index. You can try to put the number in the correct index, but this will cause O (n ^ 2) to have a non-optimal complexity, so it is a circular sort mode.

How do you recognize this pattern?

They will be problems involving sorted arrays numbered in a given range

If the question requires you to find the missing / duplicated / smallest number in the sort / rotate array

Problems with circular sorting mode:

Find the missing number (simple)

Find the smallest positive missing number (middle)

6. Reverse the linked list in place

In many problems, you may be asked to reverse link the links between a set of nodes in the list. Typically, the constraint is that you need to do this in place, even if you use existing node objects and no extra memory. This is where the pattern mentioned above is useful.

This mode reverses one node at a time, with one variable (current) pointing to the beginning of the linked list, and one variable (previous) pointing to the previous node you have processed. By locking the step, you can reverse the current node by pointing it to the previous node, and then move to the next node. In addition, you will update the variable "previous" to always point to the last node you have processed.

How to determine when to use this mode:

If you are asked to backlink the list without using extra memory

The problem of in-place reversal of linked list mode:

Delete sublist (middle)

Reverse the sublist of each K element (middle)

7. Tree BFS

This pattern traverses the tree based on breadth-first search (BFS) technology and uses queues to track all nodes at a certain level before jumping to the next level. Any problem involving step-by-step traversal of the tree can be effectively solved by using this method.

The Tree BFS mode works by pushing the root node to the queue and iterating until the queue is empty. For each iteration, we delete the node at the beginning of the queue and then "access" that node. After removing each node from the queue, we also insert all its child nodes into the queue.

How to recognize Tree BFS patterns:

If you are asked to traverse a tree step by step (or step by step)

Problems with Tree BFS mode:

Binary tree-level sequential traversal (simple)

Sawtooth traversal (middle)

8. Tree DFS

The tree DFS traverses the tree based on depth-first search (DFS) technology.

You can use recursion (or iterate with the stack) to track all previous (parent) nodes during traversal.

Tree DFS mode works from the root of the tree, and if the node is not a leaf, there are three things you need to do:

Decide whether to process the current node (subscription) immediately, between the two child nodes (sequentially), or after processing the two child nodes (post-processing).

Make two recursive calls to the two children of the current node to process them.

How to recognize Tree DFS patterns:

If the system requires you to traverse a tree sequentially, book or post DFS

If the problem needs to be searched closer to the leaf of the node

Problems with Tree DFS mode:

Total number of paths (middle)

All paths to summation (middle)

9. Two piles

In many problems, we are given a set of elements so that they can be divided into two parts. To solve this problem, we are interested in knowing the smallest element in one part and the largest element in the other. This model is an effective way to solve this kind of problem.

This pattern uses two heaps; the smallest heap can find the smallest element and the maximum heap can find the largest element. This mode works by storing the first half of the number in the largest heap because you want to find the largest number in the first half. Then you want to store the second half of the number in the smallest heap because you want to find the smallest number in the second half. At any time, the median of the current list of numbers can be calculated from the top elements of the two heaps.

The method to identify two heap patterns:

Useful in situations such as "priority queue", "schedule" and so on

If the problem indicates that you need to find the minimum / maximum / median element in the collection

Sometimes it is useful for solving problems with binary tree data structures

Characteristics of the problem

Find the median of the digital stream (middle)

10. Subset

A large number of coded interview questions involve dealing with the replacement and combination of a given set of elements. The pattern subset describes an effective breadth-first search (BFS) method to deal with all these problems.

The mode is as follows:

Given a set of [1, 5, 3]

Start with an empty set: [[]]

Add the first number (1) to all existing subsets to create a new subset: [[], [1]]

Add the second number (5) to all existing subsets: [[], [1], [5], [1Jing 5]]

Add the third number (3) to all existing subsets: [[], [1], [5], [1pr 5], [3], [1pr 3], [5pr 3], [1pr 5,3]].

This is an intuitive representation of the subset pattern:

How to identify subset patterns:

You need to find problems with the combination or arrangement of a given set

Problems with subset patterns:

Repeat subset (simple)

Change the string arrangement of case (middle)

11. Modified binary search

Whenever you are asked to sort an array, link list, or matrix, and ask you to find an element, the best algorithm you can use is binary search. This pattern describes an effective way to deal with all problems involving binary search.

For ascending settings, the mode is as follows:

First, find the middle place between the beginning and the end. An easy way to find the intermediate value is: middle = (start + end) / 2. However, this is likely to cause integer overflow, so it is recommended that the intermediate value be expressed as: Middle = start + (end-start) / 2

If the key is equal to the number in the middle of the index, return to the middle

If the key is not equal to the intermediate index:

Check key

Check key > arr [middle]. If reduced, search end = middle + 1

This is a visual representation of the modified binary search pattern:

Problems with modified binary search patterns:

Order-independent binary search (simple)

Search in a sorted infinite array

twelve。 The first K elements

Any problem that requires us to find the top / minimum / most frequent "K" element in a given set belongs to this pattern.

The best data structure for tracking "K" elements is the heap. This pattern uses the heap to solve multiple problems of dealing with "K" elements in a given set of elements at once. The mode is as follows:

Insert the "K" element into the minimum or maximum heap according to the problem.

Iterate through the remaining numbers, and if you find a number that is larger than the number in the heap, delete the number and insert a larger number.

There is no need for a sorting algorithm because the heap will track elements for you.

How to identify the most important "K" element patterns:

If you are asked to find the top / minimum / frequent "K" elements in a given collection

If you are asked to sort the array to find the exact element

There are questions in front of the "K" element list:

First "K" number (simple)

The first "K" common number (middle)

13. K-way merger

K-way Merge can help you solve problems involving a set of sorted arrays.

As long as you get a "K" sorted array, you can use the heap to effectively sort and traverse all elements of all arrays. You can push the smallest elements of each array into the smallest heap to get the overall minimum. After the total minimum is obtained, the next element is pushed from the same array to the heap. Then, repeat this process to sort and traverse all elements.

The mode is as follows:

Inserts the first element of each array into the smallest heap.

After that, the smallest (top) element is taken from the heap and added to the merge list.

After the smallest element is removed from the heap, the next element of the same list is inserted into the heap.

Repeat steps 2 and 3 to populate the merged list in sort order.

How to identify the K-way merge mode:

The problem will appear as a sorted array, list, or matrix

If the question requires you to merge the sorted list, find the smallest element in the sorted list.

Problems with K-way merge mode:

Merge K sorted lists (middle)

K pair maximum sum (hard)

14. Topological sorting

Topological sorting is used to find the linear order of interdependent elements. For example, if event "B" depends on event "A", "A" comes before "B" in topological order.

This pattern defines a simple way to understand the techniques used to topologically sort a set of elements.

The mode is as follows:

Initialize a) use HashMap to store the graph in the adjacency list b) to find all sources, use HashMap to keep degrees

Build the graph and find the degrees of all vertices a) build the graph from the input and populate the degree HashMap.

Find all sources a) all vertices with degrees "0" will be used as sources and stored in the queue.

Sorta) for each source, do the following:-I) add it to the sorted list. -ii) gets all its children from the graph. -iii) minus the degree of each child by 1. -iv) if a child's degree changes to "0", it is added to the source queue. B) repeat (a) until the source queue is empty.

How to identify the topological sort mode:

This problem will deal with graphs without directed periods.

If you are asked to update all objects in sort order

If you have a class of objects that follow a particular order

Problems with topological sorting mode:

Task Planning (medium)

Minimum tree height (hard)

At this point, I believe you have a deeper understanding of "what are the Grokking coding modes?" you might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.