This is the fourth day of my participation in the August Text Challenge.More challenges in August

Zero, preface,

These days the pace of school enrollment is getting closer and closer, many friends, friends recently private letter I have a lot of problems about school enrollment. I plan to do an issue later to help you avoid pits.

In addition, there seems to be a golden nine silver ten this time things are coming, recently many on-the-job partners are discussing the recruitment of the interview questions, another job-hopping season.

The vast majority is around the interview, brush what questions, how brush? In addition to brush questions also need to see what face to block the eight-essay like interview and so on…

Anxiety, waiting, and struggling have become a common phenomenon among programmers at this point in time.

About myself, or obediently stay, now thinking is to face with everyone. Can offer some help.

One, tight feet

By the way, many friends know that I organized a brush test group some time ago, and sent you a lot of materials last week.

Brush the questions together and summarize them together

The idea is to provide as much information as possible, so that people don’t get sidestepped. Because I did take a lot of detours when I graduated.

This detours really can’t go, otherwise, it is really the next few years will not make up for back.

When I graduated, I didn’t know whether it was the lack of information on campus or the closed environment brought by the new campus. For a variety of reasons, most people do not know that each major factory has its own campus recruitment website, and even most people do not know that after applying for a resume from the official website, they can take an online written test.

The reality is that many people understand campus recruiting to refer to companies that come to schools in person to recruit students. (But not now)

Up to now, I clearly remember that many excellent students did not go to their ideal enterprises due to information asymmetry.

The above LeetCode group is not only a test group, but also a place for discussion of school enrollment. I will also provide you with help within my ability in all aspects.

Back to an interview question that a classmate came across in recent days. It is necessary to sum up some experience together.

Two, quick hand second face topic

Just two days ago in the afternoon, my roommate next door to the university was asked an algorithm problem in kuaishou’s big data interview, which is a representative problem in the solution of dynamic programming thinking mode.

A few days ago, I also summarized the topic of dynamic planning for the first step, focusing on the method of solving the problem. If you have not seen and do not understand the suggestions of dynamic planning, this article has been written for a whole week, and I think it is very clear and detailed.

Dynamic planning ultimate recovery

The problem my friend encountered was the longest echo string

The LeetCode link is: leetcode-cn.com/problems/lo…

Here’s an example:

Input: s = “babad” Output: “bab” Explanation: “ABA” is also the answer to the question.

Let’s talk more about this topic.

And talk a little bit about why we can use dynamic programming to solve the problem, and use the formula that we wrote earlier to solve the problem. Let’s see.

3. The longest substring of a text

There are many ways to solve this problem, such as horse-drawn car algorithm, center extension algorithm and so on…

But dynamic programming is the most interesting way to solve this problem. Imprint is engraved on my heart!

Dynamic programming, someone said on Zhihu a few days ago that the name is too scary, should be called state record. Try to explain in one sentence: in the process of program calculation, the program obtains the current optimal value in the process of constantly recording the process value. Man! Let’s see…

Let’s start with A string: s = [A, B, C, B, A]

This is a palindrome string, but at the same time it illustrates an obvious phenomenon:

First, S [2] is a palindrome;

If S [1] == s[3] is the same, since S [2] is a palindrome, then S [1:3] must be a palindrome string;

If S [0] == s[4] is the same, since S [1:3] is a palindrome, then S [0:4] must be a palindrome string.

That is, use the previously recorded status to determine the current status

That is to say, the outer values are the same, and the inside is confirmed to be a palindrome string, then, the string must be a palindrome string.

String s =[B, A, B, A, D];

Since palindromes are to be determined, the logic from I to J must be involved.

So, you need a two-dimensional array to hold the state values.

There is no reverse logic to determine whether a palindrome from I to j is stored in the upper right triangle of the two-dimensional array.

In addition, using the four steps we mentioned before in dynamic planning ultimate recovery, except the last step of optimization, the other three steps are as follows:

Step 1: define the dynamic array dp.

Step 2: dynamic equation dp [I] [j] [I] = s = = s [j] and dp [I + 1] [1]

As shown in the figure below, judging the current state must depend on the element in the lower left corner;

In step 3, the diagonal must be True, and the rest is initialized to False.

Note: when j – I < = 2, only need to judge s = = s [j] [I] don’t need to judge dp [I + 1] [1]. Because when j-i<=2, at most three characters, if s[I] == s[j], can deduce that it is definitely palindrome.

In addition, it should be noted that due to the nature of the rules of dynamic equations, we must fill out a form from left to right and top to bottom to record the state values:

Below, the long graph warning (suggested point open the original map) step by step.

When j-i<=2, only dp[I] == dp[j] does not need to judge dp[I +1][j-1], because when j-i<=2, there are at most three characters. If dp[I] == dp[j], it can be inferred that it is definitely a palindrome.

All steps are taken once. In the calculation process, the longest loop substring can be obtained by recording the last occurrence of True I and j in dp array.

However, in real code, max_len=j-i+1 can be given by using the I and j of the True record in the dp array, and then continuously updating the I and j of the True record in the DP array until the maximum max_len is obtained. Finally, I and max_len at max_len are used to get the longest substring.

The above picture is not easy to make, but it feels ok.

All logic from text to code is explained! Here’s the code, written in Python and very succinct:

def longestPalindrome(self, s) :
    size = len(s)
    if size == 1:
        return s
    # define the dynamic array dp and initialize it
    dp = [[False for _ in range(size)] for _ in range(size)]
    for i in range(size):
        dp[i][i] = True

    max_len = 1     # Record palindrome string length
    start = 0       # Record the starting position of palindrome string
    Dp [I][j] == s[j] and DP [I +1][j-1]
    for j in range(1, size):
        for i in range(0, j):
            dp[i][j] = (s[i] == s[j]) and (j - i <=2 or dp[i + 1][j - 1])
            if dp[i][j]:
                if j - i + 1 > max_len:
                    max_len = j - i + 1
                    start = i

    return s[start: start+max_len]
Copy the code

Starting from j, the reason for the loop I is based on the order in which the DP status form is filled!

The above!

All over. One might recall the point of optimization, HMM.. This topic is solved by dynamic programming in space is actually no way to further optimize, if there are other optimization ideas, the group or the bottom of the message discussion ha.

Four, Thanksgiving colleagues

There is still a review summary of LeetCode for dynamic programming at this stage. Remember before you brush the question together! I’m really happy to stick to it with you. It’s really not easy for incumbents!

Today’s topic is a temporary encounter, for understanding the idea of dynamic programming has a very good guiding role.

The code and documentation for this article are available at github.com/xiaozhutec/… , it is estimated that it will take half a year to completely record all aspects of the topic, including complete codes and detailed documentation (all are long diagram interpretation, and each step of logic can help clear understanding).

Need small partners can download the code to run! It’s convenient to give a star. Thank you!