Make writing a habit together! This is the 13th day of my participation in the “Gold Digging Day New Plan · April More Text Challenge”. Click here for more details.

【 brush question diary 】385

385. Mini parser, medium

I. Title Description:

Come back early on Friday and continue to brush the daily question

At first glance at this topic, do not know what to say, it seems that feeling is not difficult to drop, to have confidence in yourself, we first carefully read

2. What ideas does this question examine? What’s your thinking?

Let’s take a closer look at what we need to do with this problem:

• They give us a string, and we need to convert it to an object that they give us

type NestedInteger struct {
}
Copy the code

• The requirement of the question is very clear, but how do we need to achieve it? Can we read the example given in the question carefully together

At a glance, we probably know that a NestedInteger object can either contain an integer itself or an integer + 1 NestedInteger child object

Take a closer look at this NestedInteger situation:

As we draw a sketch using the example given in the problem, we see that the string given in the problem is actually a layer of nested NestedInteger objects

So for this kind of nested problem, we can easily think of a recursive way, that is, the depth-first algorithm, first recurse to the deepest point, and then go up one layer at a time

We also need to understand the member methods of the NestedInteger object

So for this problem, we can use the membership method, which we’re going to use

• SetInteger, used to set an integer to an object
• Add to Add the child object NestedInteger

In this case, the main logic is to use the depth-first algorithm, iterating through the given string, recursively, when encountered ‘[‘, go to a layer, encountered ‘]’, exit this layer, encountered ‘,’ means that the current object has two elements

Through the above dismantling, the idea should be very clear, the rest is to implement our code

Three, coding

Based on the above logic and analysis, we can translate into the following code, which needs to be very careful:

• Recursively, notice ‘[‘ and ‘]’
• Notice if the object has one element or two elements, notice the comma
• Notice the negative numbers

The encoding is as follows:

func deserialize(s string) *NestedInteger {
    // Initialize the index, starting from 0
    index := 0
    // Define a recursive function
    var dfs func(a) *NestedInteger
    dfs = func(a)*NestedInteger{
        // We need to start creating a new object *NestedInteger, which contains numbers and lists, or just numbers
        nes := &NestedInteger{}
        // 1 Verifies that the current location requires recursive creation of new objects
        if s[index] == '['{
            // Offset back one bit
            index++
            // As long as the current bit does not correspond to], object creation begins
            fors[index] ! ='] '{
                nes.Add(*dfs())
                // The NestedInteger object has numbers and lists, so it needs to skip, and continue traversing
                if s[index] == ', '{
                    index++
                }
            }
            // Index +1 = index +1; // Index +1 = index +1
            index++
            return nes
        }

        // 2 In the current object, read the number
        // Make sure the number is a negative number
        fushu := (s[index] == The '-')
        if fushu {
            // If it is a negative number, then we record it and offset the index back
            index++
        }

        nums := 0
        // We know integers are contiguous, so if we encounter a comma, or [], we consider an integer to be completed
        for ; index < len(s) && unicode.IsDigit(rune(s[index])); index++ {
            nums = nums*10 +  int(s[index] - '0')}// Check whether a minus sign needs to be added
        if fushu {
            nums = -nums
        }

        nes.SetInteger(nums)
        return nes
    }

    return dfs()
}
Copy the code

Look at the above ideas and coding, as well as the annotations in the coding, I believe that it is better to understand it, the code is also more clear

Iv. Summary:

Here we can see that we only went through the s string once, so the time is O(n).

What is the space complexity here? XMD has a lot to think about

385. mini-parsers

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~