leetcode 385. Mini Parser

淩亂°似流年 2022-06-07 02:51 124阅读 0赞

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.

网上看到的答案，直接上代码吧！

代码如下：

/**
     * // This is the interface that allows for creating nested lists.
     * // You should not implement it, or speculate about its implementation
     * public interface NestedInteger {
     *     // Constructor initializes an empty nested list.
     *     public NestedInteger();
     *
     *     // Constructor initializes a single integer.
     *     public NestedInteger(int value);
     *
     *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
     *     public boolean isInteger();
     *
     *     // @return the single integer that this NestedInteger holds, if it holds a single integer
     *     // Return null if this NestedInteger holds a nested list
     *     public Integer getInteger();
     *
     *     // Set this NestedInteger to hold a single integer.
     *     public void setInteger(int value);
     *
     *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
     *     public void add(NestedInteger ni);
     *
     *     // @return the nested list that this NestedInteger holds, if it holds a nested list
     *     // Return null if this NestedInteger holds a single integer
     *     public List<NestedInteger> getList();
     * }
     */
    public class Solution 
    {  
        public NestedInteger deserialize(String s) 
        {  
            if (s.contains("[")) 
            {  
                NestedInteger ans=new NestedInteger();  
                if (s.length()>2) 
                {  
                    int begin=1;  
                    char[] cs=s.toCharArray();  
                    int count=0;  
                    for (int i = 1; i < s.length()-1; i++) 
                    {  
                        if (cs[i]==','&&count==0) 
                        {  
                            ans.add(deserialize(s.substring(begin,i)));  
                            begin=i+1;  
                        }  
                        if (cs[i]=='['||cs[i]==']') 
                        {  
                            count+=(92-cs[i]);  
                        }  
                    }  
                    ans.add(deserialize(s.substring(begin,s.length()-1)));  
                }  
                return ans;  
            }  
            return new NestedInteger(Integer.valueOf(s));  
        }  
    }

下面是C++的做法

我们可以先用递归来做，思路是，首先判断s是否为空，为空直接返回，不为空的话看首字符是否为’\[‘，不是的话说明s为一个整数，我们直接返回结果。如果首字符是’\[‘，且s长度小于等于2，说明没有内容，直接返回结果。反之如果s长度大于2，我们从i=1开始遍历，我们需要一个变量start来记录某一层的其实位置，用cnt来记录跟其实位置是否为同一深度，cnt=0表示同一深度，由于中间每段都是由逗号隔开，所以当我们判断当cnt为0，且当前字符是逗号或者已经到字符串末尾了，我们把start到当前位置之间的字符串取出来递归调用函数，把返回结果加入res中，然后start更新为i+1。如果遇到’\[‘，计数器cnt自增1，若遇到’\]’，计数器cnt自减1。

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    /**
    * // This is the interface that allows for creating nested lists.
    * // You should not implement it, or speculate about its implementation
    * class NestedInteger {
        
    *   public:
    *     // Constructor initializes an empty nested list.
    *     NestedInteger();
    *
    *     // Constructor initializes a single integer.
    *     NestedInteger(int value);
    *
    *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
    *     bool isInteger() const;
    *
    *     // Return the single integer that this NestedInteger holds, if it holds a single integer
    *     // The result is undefined if this NestedInteger holds a nested list
    *     int getInteger() const;
    *
    *     // Set this NestedInteger to hold a single integer.
    *     void setInteger(int value);
    *
    *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
    *     void add(const NestedInteger &ni);
    *
    *     // Return the nested list that this NestedInteger holds, if it holds a nested list
    *     // The result is undefined if this NestedInteger holds a single integer
    *     const vector<NestedInteger> &getList() const;
    * };
    */
    
    class Solution 
    {
    public:
        NestedInteger deserialize(string s) 
        {
            if (s.empty()) 
                return NestedInteger();
            if (s[0] != '[') 
                return NestedInteger(stoi(s));
            if (s.size() <= 2) 
                return NestedInteger();
    
            NestedInteger res;
            int start = 1, cnt = 0;
            for (int i = 1; i < s.size(); ++i) 
            {
                if (cnt == 0 && (s[i] == ',' || i == s.size() - 1)) 
                {
                    res.add(deserialize(s.substr(start, i - start)));
                    start = i + 1;
                }
                else if (s[i] == '[') 
                    ++cnt;
                else if (s[i] == ']') 
                    --cnt;
            }
            return res;
        }
    };