LeetCode Solutions in Good Style Download - LeetCode Solutions in Good Style Source code download

LeetCode Solutions in Good Style

JAVA source code

1.0.0

Download

This document provides a comprehensive overview of LeetCode-Solutions-in-Good-Style, a resource offering beginner-friendly tutorials and video solutions for algorithm and data structure problems. It features a structured approach with clear code, detailed explanations, and focuses on building a strong understanding of fundamental concepts rather than competitive coding.

LeetCode-Solutions-in-Good-Style

Explanation: Like most of my classmates, I study and summarize at the same time. I will try to share more and bring you some useful knowledge. Thank you for your continued support.

Hello everyone, this is an entry-level tutorial on "Algorithms and Data Structures". It is suitable for students with zero foundation in algorithms and students who have changed careers. It is not suitable for preparing for algorithm competitions. The point I want to convey is: write code with clear logic, so the code I write must have gone through strict thinking. The format is very standard, without personal style, and I will not write a blank line or comment in order to reduce the number of lines of code. Here it is:

You can call me weiwei. I will try my best to answer the questions I know within my ability and time permitting. If you have any questions that cannot be answered in time, it may be because I did not see the notification on the site. You can send me an email at [email protected].

Video solution I recorded

I started recording video solutions in September 2019. At the beginning, I would record the material I wanted to talk about several times. Now write verbatim drafts when explaining knowledge points. A lot of videos have been accumulated, which is actually a small systematic course. Now they are listed here. I hope it can be helpful to everyone.

0. How can a novice algorithm user use LeetCode? 【Sharing useful information】

1. Time complexity and space complexity

This video mentioned that time complexity is an asymptotic concept and needs to be understood from a dynamic perspective. And the strict definition (limit form) of time complexity is explained so that everyone can understand the calculation rules of time complexity. It also pointed out: Time complexity is not the running time of the program; "space for time" should be used, and more attention should be paid to optimizing "time complexity".

2. Binary search

This video introduces how to write a binary search algorithm. Although there are many details about binary search, as long as we master the correct problem-solving ideas, practice more, think diligently, and make more summaries, the problem of binary search will no longer be difficulty.

The following video explains several example questions of binary search. We focus on analyzing the meaning of the question and how to use the conditions given in the question to gradually narrow the search range.

Through the analysis of question 4 of "Likou" (finding the median of two positive-order arrays), we introduced this technique to you: If the properties of the target element you are looking for are more complex, you can invert this property. , and then write logical statements that can easily reduce the problem range.

3. Issues related to sorting

"Merge sort" and "quick sort" are very important sorting algorithms. A deep understanding of them is very helpful in understanding the operating mechanism of "recursive" functions. At the same time, they are also typical applications of "divide and conquer thinking". "Reverse order pair" and "Dutch flag problem (color classification)" are also very classic algorithm problems.

Calculating "reverse-order pairs" is entirely based on the idea of "merge sort".

In the explanation of the "color classification" problem, we introduced "loop invariants" to everyone. In the process of writing code, we should always abide by the semantics of the variables used, "before program execution" and "during execution" It remains unchanged after "execution ends". Adhering to our own definition of "loop invariants" is an important way for us to write correct code.

"The first missing positive number" is a classic algorithm problem. The idea used is "in-place hashing", which can be understood as a special application of the "bucket sort" algorithm: one carrot, one pit, and one bucket. Store an element. I want to emphasize that the fact that you can do this is closely related to the value of the elements of the input array.

4. Sliding window

The "sliding window" problem is a typical problem solved by applying "loop invariants", which tests our coding and debugging abilities.

5. Stack related issues

The problems solved using "stacks" require us to use specific examples to find that solving them coincides with the "last in, first out" rule:

Mastering the following two questions is inseparable from studying specific examples and then summarizing general rules.

One of the most widely used applications of "stack" is as a data structure support for "recursion", "depth-first traversal" and "divide and conquer algorithm".

6. Combined search

The data structure "Union Search Set" is currently rarely used in interviews. If you are preparing for an algorithm interview, you can skip it.

7. tree

Many tree problems can be solved using "depth-first traversal" or "breadth-first traversal".

8. Backtracking algorithm

The "backtracking algorithm" is actually a depth-first traversal of the "tree structure" contained in the question. When doing this type of problem, it is important to draw a tree structure diagram on scratch paper.

9. Dynamic programming

10. Breadth-first traversal and topological sorting

11. Hash table

12. Bit operations related

My personal website and algorithm study notes

WeChat group and QQ group

If you need friends to work on the questions together, you can join the WeChat group and QQ group.

MyLeetBook

Here is a promotion for myself. I recently launched my own LeetBook on "LeetBook": Learning Algorithms from Zero (formerly known as "Learning Algorithms and Data Structures with "LeetCoin")", which is mainly for friends who have changed careers and have zero foundation. Explain the basic knowledge of algorithms and data structures.

illustrate:

The first two chapters of LeetBook (Time Complexity, Binary Search) are free to read. The following chapters require payment to read. The non-member price is 99 yuan and the member price is 69 yuan. The homepage directory you are currently seeing is the same as LeetBook. Only the extra part, not less;

LeetBook's course titles, examples, exercises, and supporting code repository (the repository you are currently seeing) are completely public. If you have already mastered the content (including exercises) designed in LeetBook, it is not recommended to purchase it;

The energy invested is the same as writing the solution normally, except that LeetBook will be more detailed in making charts. The paid content is: the time and energy spent in making tutorials, and the participation of "Likou" staff and experts in the production and review, the reading experience will be better. It is not ruled out that I usually write more problem solving knowledge points than LeetBook;

Intermediate and advanced users please purchase with caution;

You can consult me about the course content on the "Likou" site or my other social accounts, or you can submit an issue to this warehouse. Regardless of whether I purchase the course or not, I will try my best to answer the questions that I know (time permitting and within my ability). Thank you all for your continued support to me. Everyone is welcome to communicate with me if you have suggestions and opinions;

The knowledge I explain is in the books I have recommended to everyone, the blogs, problem solutions, and notes I have written. The published problem solutions, blogs, and notes will always be shared, and as long as I have time and energy, I will continue to do so. Do sharing and Q&A;

I am very grateful to "Likou" for giving me the opportunity to take courses and help me fulfill a small wish.

"Lekou" classification and problem solution directory (arranged according to LeetBook chapters, Chapter 16 and onwards are chapters currently not included in LeetBook)

Note: The question categories correspond to my LeetBook chapters.

Chapter 1 Time Complexity

This part introduces the concept of time complexity. You can watch [Video Explanation], which is completely free. There are no exercises for this chapter.

Chapter 2 Binary Search

Question Type 1: Find subscripts in two points

illustrate:

practise:

Question Type 2: Determine an integer with a range by two points (two points answer)

Algorithmic thinking: reduce and conquer. If the question requires us to find an integer, and this integer has a certain range, we can gradually narrow the range through binary search, and finally approach it to a number.

Question type 3: Complex discriminant function (maximization problem)

Note: This type of question is essentially "Question Type 2" (two-point answer), but it may feel a little confusing when you first learn it. Questions of this type are asked in the same way. The keywords are "continuous" and "positive integer". Please pay attention to capturing such key information in the question.

Chapter 3 Basic Sorting Algorithms

This part contains four basic sorting algorithms: selection sort, insertion sort, Hill sort, and bubble sort.

"Likou" question 912: Solution to sorted array: This summarizes some key points and learning materials for sorting problems. You can start learning algorithms from sorting problems.

Array problems can be used as a "newbie's field" in algorithms, because these problems can be completed only by mastering the basic knowledge of programming languages. It is easy to think of solutions to the following problems, even if you have not learned relevant data structure and algorithm knowledge.

Knowledge point: loop invariants

Chapter 4 Advanced Sorting Algorithms (Important)

This part needs to focus on mastering three advanced sorting algorithms: merge sort, quick sort, and heap sort.

illustrate:

Chapter 5 Non-Comparative Sorting (Optional)

This part contains three types of non-comparison sorting: counting sort, radix sort, and bucket sort. Solving these problems requires understanding the concept of in-place hashing.

Chapter 6 Sliding Window and Dual Pointers

1. Sliding window

Reference writing method of sliding window (not a template, please do not copy it as it is, it is for reference only, it is more important to understand the algorithm design idea):

Friendly reminder: Questions 3 and 76 are basic questions that you must be able to do. Once you have a thorough understanding of the above questions, you can answer the following questions more easily.

Key questions:

illustrate:

practise:

illustrate:

Question 209: The key information given in the question: All elements in the array are positive integers. There are a total of 3 methods as follows.

Method 1: Violent solution

Method 2: Sliding window (analyze the reasons why sliding windows can be used)

Method 3: Construct the prefix and array, and then use binary search

Question 438: Same as question 76;

Question 567: Same as question 76, except that the collection of qualified sentences is different.

2. Double pointers

The "double pointer" problem is actually an optimization of the naive algorithm. Many solutions that do not meet the meaning of the problem are sorted out at once. The same is true for the "sliding window" technique. It is still more important to analyze why double pointers can be used.

The binary search algorithm used to find subscripts can also be considered a double pointer solution.

Chapter 7 Linked List

A very practical technique to solve linked list problems is "drawing". The same is true for the analysis and explanation of other algorithmic problems (explaining to the interviewer).

You can write test functions for linked lists to facilitate debugging. The recommended implementation methods are: ① Create a singly linked list through an array; ② Print the current node and subsequent nodes based on the current node. These two methods can very conveniently help us debug programs related to linked lists.

Question type 1: Basic linked list pointer pointing problem

Note: Some problems require the use of "virtual head nodes" to avoid complex classification discussion logic for the first node of the linked list. We have seen this idea in arrays, called "sentinels".

Use recursive functions to avoid complex operations of changing pointer variables, making solving problems simple.

illustrate:

Question Type 2: Fast and Slow Pointer Skills

To be precise, it might be better to call it "synchronized pointer".

Using two pointer variables, they are both located at the first node of the linked list at the beginning. One always only takes one step at a time, and the other always only takes two steps at a time, one in front and one in the back, at the same time. In this way, when the fast pointer finishes walking, the slow pointer will reach the middle position of the linked list.

The common feature to solve these problems is to use two pointer variables to move synchronously. The fast and slow pointers move in the same direction, and the "difference" between their steps is constant. Based on this certainty, some problems in the linked list can be solved. Using this idea can also solve the following problems of linked lists:

illustrate:

Question type three: Design data structure

Chapter 8 Stack and Queue

1. Stack

Question Type 1: Basic problems solved using the stack

The following questions are very basic and must be mastered:

practise:

Question Type 2: Monotone Stack

A monotonic stack is an ordinary stack, which happens to comply with the "last in, first out" principle during use, and the elements in the stack are monotonic. The problems of "monotone stack" and "monotone queue" are usually very special. Just master the examples and some exercises.

Experience: subscripts are generally stored in monotonic stacks.

illustrate:

practise:

2. Queue

Question Type 1: Basic problems solved using queues

All problems solved using breadth-first traversal use queues.

Question Type 2: Monotone Queue

A monotonic queue is just an ordinary queue. This problem is currently found in the monotonic queue on "Likou". The key is to analyze clearly why the designed algorithm happens to make the queue monotonic. In addition, there are examples of using monotonic queues for optimization in the "Knapsack Problem". Interested friends can learn about it, which is competition knowledge.

Experience: Subscripts are generally stored in monotonic queues.

Chapter 9 Priority Queue

Note: It is necessary to understand the implementation of "heap" as a "priority queue". It will help to understand the coding details of remove() and replace(), so that you will be more effective when using the heap.

Application: Dynamically select the highest priority element in the current queue, focusing on understanding the meaning of "dynamic".

Chapter 10: Combined Search

And check the [video explanation] of the knowledge points in the video solution to question 990. Basic and common questions include:

Optional questions:

Chapter 11 Trees (Binary Trees and Binary Search Trees)

Chapter 12 Backtracking Algorithm

Question type 1: Basic backtracking problem

Through these questions, you can understand the idea of the backtracking algorithm. The knowledge points of the backtracking algorithm are explained in the video solution and text solution of question 46 of "Likou".

Backtracking is to use depth-first traversal to search all solutions of the tree (graph). Depth-first traversal has an obvious recursive structure.

Tips for solving the following problems: ① Draw, draw, draw; ② Understand depth-first traversal and recursion; ③ Debug more, debug more.

Question Type 2: Backtracking Problem on Strings

Key points to understand: Since the string generates new characters every time, there is no need to reset the state.

Question type three: Flood Fill

Question Type 4: Some Game Questions

illustrate:

Chapter 13 Dynamic Programming (Part 1)

Two important ideas of dynamic programming:

Two directions of thinking in dynamic programming:

Three conditions need to be met to solve the problem using dynamic programming:

Two important concepts of dynamic programming:

Question classification reference:

Note: The typical questions given below will be added (December 2, 2020).

1. Getting started

Understand the two dynamic programming methods of "top-down" memory recursion and "bottom-up" recursion.

2. Repeated sub-problems

This part requires the use of the "step counting multiplication principle" and the "categorical counting addition principle".

Question 70: This is the same question as Fibonacci numbers. Counting problems will use the classification counting principle and the step counting principle.

3. Optimal substructure

illustrate:

Question 377: Note that screening is not a backpack issue.

4. No aftereffects

practise:

The following are some classic "dynamic programming" problems. Because these issues are so important, they are included in a separate category.

5. Maximum sub-segment sum

practise:

6. Longest rising subsequence

Note: Question 300 is a very classic dynamic programming problem. The solution of $O(N log N)$ defines the state according to the characteristics of the problem itself and proves that the state array is an ordered array, which reduces the time complexity.

practise:

7. The longest common substring

8. Interval DP and partitioned DP

Interval DP:

Partitioned DP:

9. Tree DP

Chapter 14 Dynamic Programming (Part 2)

1. Backpack Problem

Nine lectures on backpacks: https://github.com/tianyicui/pack

("Game Type DP", "State Compression DP", "Digital DP", etc. will be added.)