leetcode Mini Parser

leetcode Mini Parser

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9, [, ,, ].

Example 1:

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

题目地址:leetcode Mini Parser

题意:给定一个字符串,要求把它解析成NestedInteger 类型

思路:

第3个A此题 怀疑前两个是出题的人自己测试的= = 本来发了discuss 想想还是只发blog吧~

本题的NestedInteger结构 和341. Flatten Nested List Iterator 类似

由于没有空格,所以第一个字母不是'[‘的说明只有一个数字。直接返回NestedInteger(int(s))

接下来,用一个栈来维护,对于左括号[的,当前的NestedInteger 进栈,对于右括号,当前数字放入NestedInteger 栈不为空则把栈顶的NestedInteger添加当前的NestedInteger,并且出栈。

此外,注意‘-’的情况

class Solution(object):
    def deserialize(self, s):
        """
        :type s: str
        :rtype: NestedInteger
        """
        if s[0] != '[': return NestedInteger(int(s))
        stack = []
        n = len(s)
        cur = minus = num = None
        for i in xrange(n):
            if s[i] == '[':
                if cur is not None:
                    stack.append(cur)
                cur = NestedInteger()
            elif s[i] in [']', ',']:
                if num is not None:
                    if minus: num *= -1
                    cur.add(num)
                if s[i] == ']' and stack:
                    stack[-1].add(cur)
                    cur = stack.pop()
                minus = num = None
            elif s[i] == '-':
                minus = True
            else:
                if num is None: num = 0
                num = num * 10 + ord(s[i]) - 48
        return cur

 

 

 

本题是leetcode 385 Mini Parser 的题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Mini Parser
本文地址:https://www.hrwhisper.me/leetcode-mini-parser/

您的支持将鼓励我继续创作!

Leetcode , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *