Column website www.jiuzhang.com | | nine chapters algorithm
Topic describes
Given a nested array as a string, write a parser to deserialize it. The elements of an array are integers or an array of the same form. Note: You can assume that this string follows the following rules: String is not empty String contains no Spaces String contains only the numbers 0-9, [, -,], and comma “, “.
The sample
Example a given string s = “234” returns a NestedInteger object containing only the integer 234.
Given the string s = “[123,[456,[789]]”, return a NestedInteger object containing two elements: an integer 123 a NestedInteger List containing two elements: An integer 456 a NestedInteger List containing one element: an integer 789
Analysis of the problem
This belongs to a medium difficulty string processing problem, the main difficulty is logical thinking about the level, each case can not be missed.
Simple analysis, this problem needs to be analyzed layer by layer, to the innermost layer after the end. For this kind of level problem is obviously suitable for two solutions, one is to use Stack, one is recursive. ; The two solutions are just the difference in code writing, in fact, there is no difference in the essence of the idea (Stack can be considered to simulate recursion), so the reference program only gives a solution with Stack, recursion is similar.
Further analysis: if a “[” symbol is encountered in the string, a new layer needs to be opened. If a”] “symbol is encountered in the string, the layer ends. But at the end of the floor, because a layer to include pop up this layer, so need to be added to the top layer (play) after stack stack if you meet “, “in the string, only need to deal with the front is digital array (because the front is handled when it encountered in”] “), namely the figures added to the current layer (that is, the stack at the top). Note one special case: the case that contains only one number (as in example 1) requires extra processing (because it doesn’t have any symbols).
Reference code
www.jiuzhang.com/solutions/m…
From the perspective of the interviewer
This problem is not difficult algorithm, can do not omit the situation, the logic of each layer is clear, you can get hire.
LintCode exercises
www.lintcode.com/en/problem/…
Recommended reading:
- Do I need a cover letter to apply online?
- What are the most popular programming languages of 2017?
- Top 10 Reasons to Drop an Offer
- How to negotiate Google Offer? Listen to this Google Recruiter!
- What about the questions you have done in the interview?
- Snapchat surface by | LA headquarters interview experience
- How to learn about an IT company before an interview? Try the official tech blog!
- The 7 most creative resumes in the history of the Internet
- Using Twitter to find a job | how to look for job information
- Facebook +Onsite Onsite Software
Welcome to follow my wechat official account: Ninechapter.
Elite programmer exchange community, regular release of interview questions, interview skills, job information, etc
