LeetCode题练习与总结：迷你语法分析器--385

一、题目描述

给定一个字符串 s 表示一个整数嵌套列表，实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。

列表中的每个元素只可能是整数或整数嵌套列表

示例 1：

输入：s = "324",
输出：324
解释：你应该返回一个 NestedInteger 对象，其中只包含整数值 324。

示例 2：

输入：s = "[123,[456,[789]]]",
输出：[123,[456,[789]]]
解释：返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：
1. 一个 integer 包含值 123
2. 一个包含两个元素的嵌套列表：i.  一个 integer 包含值 456ii. 一个包含一个元素的嵌套列表a. 一个 integer 包含值 789

提示：

• 1 <= s.length <= 5 * 10^4
• s 由数字、方括号 "[]"、负号 '-' 、逗号 ','组成
• 用例保证 s 是可解析的 NestedInteger
• 输入中的所有值的范围是 [-10^6, 10^6]

二、解题思路

解题思路：

• 如果字符串 s 的第一个字符不是 [，那么它是一个整数，可以直接解析并返回。
• 如果 s 的第一个字符是 [，那么它是一个嵌套列表。我们需要遍历字符串，解析出每个元素（整数或嵌套列表），并将其添加到结果 NestedInteger 对象中。

在解析嵌套列表时，我们需要注意以下几点：

• 使用一个栈来追踪嵌套的深度。每当遇到 [，将一个新 NestedInteger 对象压入栈中；每当遇到 ]，将栈顶的 NestedInteger 对象弹出。
• 当遇到 , 或 ] 时，表示一个元素的结束。如果元素不是空的，将其添加到栈顶的 NestedInteger 对象中。

三、具体代码

import java.util.*;public class Solution {public NestedInteger deserialize(String s) {if (s == null || s.isEmpty()) {return new NestedInteger();}if (s.charAt(0) != '[') { // 如果不是以'['开头，则表示是一个整数return new NestedInteger(Integer.parseInt(s));}// 如果以'['开头，则表示是一个嵌套列表Stack<NestedInteger> stack = new Stack<>();NestedInteger curr = null;int numStart = 0; // 数字开始的索引for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '[') {// 遇到 '[' 时，将一个新的 NestedInteger 压入栈中if (curr != null) {stack.push(curr);}curr = new NestedInteger();numStart = i + 1; // 数字开始的索引更新} else if (c == ',' || c == ']') {// 遇到 ',' 或 ']' 时，表示一个元素的结束if (i > numStart) { // 确保字符串不是空的String num = s.substring(numStart, i);if (!num.isEmpty()) {curr.add(new NestedInteger(Integer.parseInt(num)));}}numStart = i + 1; // 数字开始的索引更新if (c == ']') {// 遇到 ']' 时，将当前 NestedInteger 弹出并添加到上一个 NestedInteger 中if (!stack.isEmpty()) {NestedInteger pop = stack.pop();pop.add(curr);curr = pop;}}}}return curr;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

代码中的主要操作是遍历字符串 s，这个操作的时间复杂度是 O(n)，其中 n 是字符串 s 的长度。在遍历过程中，对于每个字符，我们执行了常数时间的操作，例如字符比较、字符串子串的创建和整数的解析。这些操作不会改变整体的时间复杂度，仍然是 O(n)。

因此，整体的时间复杂度是 O(n)。

2. 空间复杂度

空间复杂度主要取决于以下两个因素：

• 栈 stack：在最坏的情况下，如果嵌套列表非常深，那么栈的大小将接近字符串的长度 n。因此，栈的空间复杂度是 O(n)。

• 字符串子串：在每次遇到逗号或右括号时，我们可能创建了一个新的字符串子串。在最坏的情况下，每次都会创建一个新的子串，这些子串的总长度将接近字符串的长度 n。因此，字符串子串的空间复杂度也是 O(n)。

综上所述，整体的空间复杂度是 O(n)，因为这两个空间需求是并列的，不是累加的。

五、总结知识点

• 接口与实现：

  • NestedInteger 接口的使用，该接口定义了嵌套整数的抽象操作。

• 字符串处理：

  • 使用 charAt 方法来访问字符串中的单个字符。
  • 使用 substring 方法来提取字符串的子串。

• 异常处理：

  • 在将字符串转换为整数时，如果字符串不是一个有效的整数表示，parseInt 方法会抛出 NumberFormatException。

• 数据结构：

  • 使用 Stack 来处理嵌套结构，这是解决此类问题的一种常见方法。

• 逻辑控制：

  • 使用循环 (for 循环) 来遍历字符串。
  • 使用条件语句 (if-else) 来根据不同的字符进行不同的处理。

• 递归结构：

  • 虽然代码本身不是递归的，但处理嵌套列表的逻辑是递归的，因为每次遇到 [ 时，都会创建一个新的 NestedInteger 对象，并在遇到 ] 时将其添加到上一层的 NestedInteger 对象中。

• 对象操作：

  • 创建 NestedInteger 对象，并使用 add 方法来添加整数或嵌套列表。

• 边界条件处理：

  • 检查字符串是否为空或 null，并返回一个空的 NestedInteger 对象。
  • 确保在添加整数前字符串子串不为空。

• 索引管理：

  • 使用变量 numStart 来跟踪当前数字子串的开始位置。

• 栈的操作：

  • 使用 push 方法将对象压入栈中。
  • 使用 pop 方法从栈中弹出对象。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。