Go Java 算法迷你语法分析器
黄丫丫 人气:0迷你语法分析器
给定一个字符串 s 表示一个整数嵌套列表,实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。
列表中的每个元素只可能是整数或整数嵌套列表
- 示例 1:
输入:s = "324",
输出:324
解释:你应该返回一个 NestedInteger 对象,其中只包含整数值 324。
- 示例 2:
输入:s = "[123,[456,[789]]]",
输出:[123,[456,[789]]]
解释:返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表:
一个 integer 包含值 123
一个包含两个元素的嵌套列表:
i. 一个 integer 包含值 456
ii. 一个包含一个元素的嵌套列表
a. 一个 integer 包含值 789
提示:
- 1 <= s.length <= 5 * 104
- s 由数字、方括号 "[]"、负号 '-' 、逗号 ','组成
- 用例保证 s 是可解析的 NestedInteger
- 输入中的所有值的范围是 [-106, 106]
方法一:深度优先遍历(Java)
根据题意,一个 NestedInteger 实例只能包含下列两部分之一:1)一个整数;2)一个列表。
列表中的每个元素都是一个 NestedInteger 实例。据此,NestedInteger 是通过递归定义的,因此也可以用递归的方式来解析。
注意序列化的String,有2个特殊含义,导致不能用String.split()。否则实现起来会比较困难。
逗号: 表示分割“同层级”的元素
中括号[] : 表示1个List,可以有兄弟节点Integer。
如果用逗号分割,可能会割裂了[]的List含义。
class Solution { int index = 0; public NestedInteger deserialize(String s) { if (s.charAt(index) == '[') { index++; NestedInteger ni = new NestedInteger(); while (s.charAt(index) != ']') { ni.add(deserialize(s)); if (s.charAt(index) == ',') { index++; } } index++; return ni; } else { boolean negative = false; if (s.charAt(index) == '-') { negative = true; index++; } int num = 0; while (index < s.length() && Character.isDigit(s.charAt(index))) { num = num * 10 + s.charAt(index) - '0'; index++; } if (negative) { num *= -1; } return new NestedInteger(num); } } }
时间复杂度:O(n)
空间复杂度:O(n)
方法二:栈(Go)
我们只需关注字符串s
中的[
、]
和,
字符,其他字符均可转为数字,初始化栈时,将一个空的NestedInteger
加入其中,防止越界。
顺序遍历,3
种情况:
[
:新建列表,入栈
数字和-
:累加字符串
]
和,
:字符串加完,加入列表
]
:出栈,结果加入上级列表
func deserialize(s string) *NestedInteger { if s[0] != '[' { integer, _ := strconv.Atoi(s) nestedInteger := &NestedInteger{} nestedInteger.SetInteger(integer) return nestedInteger } stack, integer := []*NestedInteger{}, "" for _, ch := range s { switch ch { case '[': stack = append(stack, &NestedInteger{}) // 入栈 case ']': fallthrough case ',': if integer != "" { int, _ := strconv.Atoi(integer) nestedInteger := NestedInteger{} nestedInteger.SetInteger(int) stack[len(stack) - 1].Add(nestedInteger) integer = "" } if ch == ']' && len(stack) > 1 { // 出栈 stack[len(stack) - 2].Add(*stack[len(stack) - 1]) stack = stack[:len(stack) - 1] } default: integer += string(ch) } } return stack[len(stack) - 1] }
时间复杂度:O(n)
空间复杂度:O(n)
加载全部内容